マスジョイ
PR
数列
数学的帰納法
更新:2024/12/05

ファレイ数列の定義・証明・具体例・性質・例題について

はるか
はるか
ファレイ数列って、分数の並びだけど、結構奥が深い。
ふゅか
ふゅか
既約分数を並べただけで、いろんな性質が見えてくるのが面白いわ♪
目次

1. ファレイ数列とは

ファレイ数列 Fn F_n は、分母が n n 以下の既約分数を大小の順に並べたものです。ファレイ数列 Fn F_n は、以下の条件を満たすすべての分数 ab \frac{a}{b} の集合です。
  1. 0≤a≤b≤n 0 \leq a \leq b \leq n
  2. gcd⁡(a,b)=1 \gcd(a, b) = 1 （すなわち、a a と b b が互いに素である）
それぞれのファレイ数列 F1 F_1 から F5 F_5 を次のように書くことができます。

F1={01,11} F_1 = \left\{ \frac{0}{1}, \frac{1}{1} \right\}

F2={01,12,11} F_2 = \left\{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1} \right\}

F3={01,13,12,23,11} F_3 = \left\{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1} \right\}

F4={01,14,13,12,23,34,11} F_4 = \left\{ \frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1} \right\}

F5={01,15,14,13,25,12,35,23,34,45,11} F_5 = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right\}

2. ファレイ数列の性質

ファレイ数列（Farey sequence）は、多くの興味深い性質を持っています。以下に、ファレイ数列の主要な性質をいくつか紹介します。

2.1. 連続する分数の挿入

ファレイ数列Fn+1 F_{n+1} をFn F_n から構築するとき、連続する分数 ab \frac{a}{b} と cd \frac{c}{d} の間に新しい分数 a+cb+d \frac{a+c}{b+d} が必要箇所に挿入する。
ふゅか
ふゅか
ファレイ数列の面白いところは、次の数列を作るときに、分数をうまく挿入していくところよね！
はるか
はるか
FnF_nからFn+1F_{n+1}を作れる。

例: ファレイ数列 F2 F_2 から F3 F_3 を構築する。

ファレイ数列 F2 F_2 : F2 F_2 は、分母が最大2までのすべての既約分数からなる数列です。したがって、 F2={01,12,11} F_2 = \left\{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1} \right\}

ファレイ数列 F3 F_3 の構築: F2 F_2 の連続する分数 ab \frac{a}{b} と cd \frac{c}{d} の間に、新しい分数 a+cb+d \frac{a+c}{b+d} を挿入します。ここでは、以下のステップに従います。

  • 01 \frac{0}{1} と 12 \frac{1}{2} の間に、0+11+2=13 \frac{0+1}{1+2} = \frac{1}{3} を挿入します。
  • 12 \frac{1}{2} と 11 \frac{1}{1} の間に、1+12+1=23 \frac{1+1}{2+1} = \frac{2}{3} を挿入します。

これにより、次のファレイ数列 F3 F_3 が得られます。 F3={01,13,12,23,11} F_3 = \left\{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1} \right\}

このようにして、ファレイ数列 Fn F_n から Fn+1 F_{n+1} を構築できます。

2.2. 隣接する分母の和

ファレイ数列FnF_nの隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} の間には、次の関係が成立します。gi+gi+1≥n+1g_i+g_{i+1}\geq n+1となる。

隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} の間にgi+gi+1≥n+1g_i + g_{i+1} \geq n + 1が成立することを数学的帰納法で証明します。

まず、 n=1 n = 1 の場合を考えます。このとき、ファレイ数列 F1 F_1 は次のようになります。

F1={01,11} F_1 = \left\{ \frac{0}{1}, \frac{1}{1} \right\}

隣接する分数は 01 \frac{0}{1} と 11 \frac{1}{1} です。このとき、分母の和は

g1+g2=1+1=2 g_1 + g_2 = 1 + 1 = 2

です。 g1+g2≥n+1=2 g_1 + g_2 \geq n + 1 = 2 なので、n=1n=1のときに成り立ちます。

次に、n=kn=kのとき 、Fk F_k の任意の隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} に対して

gi+gi+1≥k+1 g_i + g_{i+1} \geq k + 1

が成立すると仮定します。

n=k+1n=k+1のとき次のファレイ数列 Fk+1 F_{k+1} でも同じ関係が成り立つことを示します。Fk+1 F_{k+1} は Fk F_k を基本とし、隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} の間に新しい分数

fi+fi+1gi+gi+1 \frac{f_i + f_{i+1}}{g_i + g_{i+1}}

が該当箇所に挿入されたものである。

ファレイ数列である条件を満たすために、Fn+1 F_{n+1} における新たな隣接する分数について、2つの場合に分けることができる。

1. 新しい分数 fi+fi+1gi+gi+1 \frac{f_i + f_{i+1}}{g_i + g_{i+1}} と figi \frac{f_i}{g_i} の間

この場合、分母の和は、帰納法の仮定より gi+gi+1≥k+1 g_i + g_{i+1} \geq k + 1 なので

(gi+gi+1)+gi≥k+1+gi≥k+2 (g_i + g_{i+1}) + g_i \geq k + 1+ g_{i} \geq k + 2

2. 新しい分数 fi+fi+1gi+gi+1 \frac{f_i + f_{i+1}}{g_i + g_{i+1}} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} の間
この場合、分母の和は

(gi+gi+1)+gi+1≥k+1+gi+1≥k+2 (g_i + g_{i+1}) + g_{i+1} \geq k + 1+ g_{i+1} \geq k + 2

より、この場合も成り立ちます。

したがって、n=k+1n=k+1のとき、

gi+gi+1≥k+2 g_i + g_{i+1} \geq k + 2

となる。

数学的帰納法により、すべての n n に対してファレイ数列 Fn F_n の隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} の間に

gi+gi+1≥n+1 g_i + g_{i+1} \geq n + 1

が成り立つことが証明されました。

2.3. 隣接する分数の差

ファレイ数列FnF_nの隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} の間には、次の関係が成立します。 fi+1gi–figi+1=1 f_{i+1}g_i – f_ig_{i+1}= 1

ファレイ数列 Fn F_n の隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} の間に、次の関係 fi+1gi–figi+1=1 f_{i+1}g_i – f_ig_{i+1}= 1 が成立することを数学的帰納法で示します。

まず、n=1 n = 1 の場合を考えます。ファレイ数列 F1 F_1 は 01 \frac{0}{1} と 11 \frac{1}{1} の2つの分数からなります。これらの分数について、次の計算を行います。

fi+1gi–figi+1=1×1–0×1=1 f_{i+1}g_i – f_ig_{i+1} = 1 \times 1 – 0 \times 1 = 1

n=1 n = 1 のとき、関係が成り立つ。

次に、n=kn = k について、ファレイ数列 Fk F_k の任意の隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} について、 fi+1gi–figi+1=1 f_{i+1}g_i – f_ig_{i+1} = 1 が成立すると仮定します。

ファレイ数列 Fk+1 F_{k+1} は Fk F_k の各隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} の間に、新しい分数 fi+fi+1gi+gi+1 \frac{f_i + f_{i+1}}{g_i + g_{i+1}} を必要箇所に挿入して得られます。つまり、Fk+1 F_{k+1} には次のような隣接する分数があります。

  • figi \frac{f_i}{g_i} と fi+fi+1gi+gi+1 \frac{f_i + f_{i+1}}{g_i + g_{i+1}}
  • fi+fi+1gi+gi+1 \frac{f_i + f_{i+1}}{g_i + g_{i+1}} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}}

それぞれのペアについて、式を確認します。

1. figi \frac{f_i}{g_i} と fi+fi+1gi+gi+1 \frac{f_i + f_{i+1}}{g_i + g_{i+1}} について、

(fi+fi+1)gi–fi(gi+gi+1)(f_i + f_{i+1})g_i – f_i(g_i + g_{i+1})

=figi+fi+1gi–figi–figi+1= f_ig_i + f_{i+1}g_i – f_ig_i – f_ig_{i+1}

=fi+1gi–figi+1=1= f_{i+1}g_i – f_ig_{i+1} = 1

2. fi+fi+1gi+gi+1 \frac{f_i + f_{i+1}}{g_i + g_{i+1}} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} について、

fi+1(gi+gi+1)–(fi+fi+1)gi+1f_{i+1} (g_i + g_{i+1}) – (f_i + f_{i+1}) g_{i+1}

=fi+1gi+fi+1gi+1−figi+1−fi+1gi+1= f_{i+1}g_i +f_{i+1}g_{i+1}- f_ig_{i+1}-f_{i+1}g_{i+1}

=fi+1gi–figi+1=1= f_{i+1}g_i – f_ig_{i+1} = 1

これにより、ファレイ数列 Fk+1 F_{k+1} においても隣接する分数に関して関係式 fi+1gi–figi+1=1 f_{i+1}g_i – f_ig_{i+1} = 1 が成り立つことが確認されました。

したがって、数学的帰納法により、任意の n n に対して、ファレイ数列 Fn F_n の隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} の間に fi+1gi–figi+1=1 f_{i+1}g_i – f_ig_{i+1} = 1 が成り立つことが示されました。

はるか
はるか
隣り合う分数の性質も重要。特に、分母の和とか、差の関係がポイント。
ふゅか
ふゅか
うん、隣り合う分数を見てると、単に並んでるだけじゃなくて、規則的な関係が見えてくるのね！
はるか
はるか
そう。gi+gi+1≥n+1g_i + g_{i+1} \geq n + 1とか、fi+1gi–figi+1 f_{i+1}g_i – f_ig_{i+1} が必ず1になるとか。

2.4. 分数の総数

ファレイ数列 Fn F_n に含まれる分数の総数は、次の式で与えられます。 ∣Fn∣=1+∑k=1nϕ(k) |F_n| = 1 + \sum_{k=1}^{n} \phi(k) ここで、ϕ(k) \phi(k) はオイラーのトーシェント関数で、k k と互いに素である1以上k k 以下の整数の個数を表します。
ふゅか
ふゅか
最後に、ファレイ数列に含まれる分数の総数についても考えたわよね。
はるか
はるか
オイラーのトーシェント関数を使って、総数が求められる

3. ファレイ数列の例題

ふゅか
ふゅか
ファレイ数列の性質が実際に成り立っているのか確認できる計算問題を解いてみよう！
はるか
はるか
今回はファレイ数列F5F_5の場合について考える。

3.1. 例題1（隣接する分数の和）

ファレイ数列 F5 F_5 に含まれる隣接するすべての分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} に関して、次のことを確認しなさい。

gi+gi+1≥6 g_i + g_{i+1} \geq 6

ここで、gi g_i と gi+1 g_{i+1} はそれぞれ分母の値です。すべての隣接するペアについて計算を行い、この不等式が成立することを確認しなさい。

まず、ファレイ数列 F5 F_5 の全ての分数を列挙します。

ファレイ数列 F5 F_5 は以下のような分数の列から成ります。

F5={01,15,14,13,25,12,35,23,34,45,11} F_5 = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right\}

隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} について、gi+gi+1≥6 g_i + g_{i+1} \geq 6 を確認します。

  • 01 \frac{0}{1} と 15 \frac{1}{5} : g1=1,g2=5 g_1 = 1, g_2 = 5 なので 1+5=6≥6 1 + 5 = 6 \geq 6
  • 15 \frac{1}{5} と 14 \frac{1}{4} : g1=5,g2=4 g_1 = 5, g_2 = 4 なので 5+4=9≥6 5 + 4 = 9 \geq 6
  • 14 \frac{1}{4} と 13 \frac{1}{3} : g1=4,g2=3 g_1 = 4, g_2 = 3 なので 4+3=7≥6 4 + 3 = 7 \geq 6
  • 13 \frac{1}{3} と 25 \frac{2}{5} : g1=3,g2=5 g_1 = 3, g_2 = 5 なので 3+5=8≥6 3 + 5 = 8 \geq 6
  • 25 \frac{2}{5} と 12 \frac{1}{2} : g1=5,g2=2 g_1 = 5, g_2 = 2 なので 5+2=7≥6 5 + 2 = 7 \geq 6
  • 12 \frac{1}{2} と 35 \frac{3}{5} : g1=2,g2=5 g_1 = 2, g_2 = 5 なので 2+5=7≥6 2 + 5 = 7 \geq 6
  • 35 \frac{3}{5} と 23 \frac{2}{3} : g1=5,g2=3 g_1 = 5, g_2 = 3 なので 5+3=8≥6 5 + 3 = 8 \geq 6
  • 23 \frac{2}{3} と 34 \frac{3}{4} : g1=3,g2=4 g_1 = 3, g_2 = 4 なので 3+4=7≥6 3 + 4 = 7 \geq 6
  • 34 \frac{3}{4} と 45 \frac{4}{5} : g1=4,g2=5 g_1 = 4, g_2 = 5 なので 4+5=9≥6 4 + 5 = 9 \geq 6
  • 45 \frac{4}{5} と 11 \frac{1}{1} : g1=5,g2=1 g_1 = 5, g_2 = 1 なので 5+1=6≥6 5 + 1 = 6 \geq 6

全ての隣接する分数に対して、gi+gi+1≥6 g_i + g_{i+1} \geq 6 が成り立つことが確認できました。

ふゅか
ふゅか
隣接する分数のペアを調べると、ちゃんと gi+gi+1≥6 g_i + g_{i+1} \geq 6 が成り立っているわね！

3.2. 例題2（隣接する分数の差）

ファレイ数列 F5 F_5 に含まれる隣接するすべての分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} に関して、次の関係を確認しなさい。

fi+1gi–figi+1=1 f_{i+1}g_i – f_ig_{i+1} = 1

ここで、すべての隣接するペアについて計算を行い、この等式が成立することを確認しなさい。

はるか
はるか
fi+1gi–figi+1f_{i+1}g_i – f_ig_{i+1} もすべて1になっていることを確認する。

まず、ファレイ数列 F5 F_5 の全ての分数を列挙します。

ファレイ数列 F5 F_5 は以下のような分数の列から成ります。

F5={01,15,14,13,25,12,35,23,34,45,11} F_5 = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right\}

隣接する分数 figi \frac{f_i}{g_i} と fi+1gi+1 \frac{f_{i+1}}{g_{i+1}} について、fi+1gi–figi+1=1 f_{i+1}g_i – f_ig_{i+1} = 1 を確認します。

  • 01 \frac{0}{1} と 15 \frac{1}{5} : 1×1–0×5=1–0=1 1 \times 1 – 0 \times 5 = 1 – 0 = 1
  • 15 \frac{1}{5} と 14 \frac{1}{4} : 1×5–1×4=5–4=1 1 \times 5 – 1 \times 4 = 5 – 4 = 1
  • 14 \frac{1}{4} と 13 \frac{1}{3} : 1×4–1×3=4–3=1 1 \times 4 – 1 \times 3 = 4 – 3 = 1
  • 13 \frac{1}{3} と 25 \frac{2}{5} : 2×3–1×5=6–5=1 2 \times 3 – 1 \times 5 = 6 – 5 = 1
  • 25 \frac{2}{5} と 12 \frac{1}{2} : 1×5–2×2=5–4=1 1 \times 5 – 2 \times 2 = 5 – 4 = 1
  • 12 \frac{1}{2} と 35 \frac{3}{5} : 3×2–1×5=6–5=1 3 \times 2 – 1 \times 5 = 6 – 5 = 1
  • 35 \frac{3}{5} と 23 \frac{2}{3} : 2×5–3×3=10–9=1 2 \times 5 – 3 \times 3 = 10 – 9 = 1
  • 23 \frac{2}{3} と 34 \frac{3}{4} : 3×3–2×4=9–8=1 3 \times 3 – 2 \times 4 = 9 – 8 = 1
  • 34 \frac{3}{4} と 45 \frac{4}{5} : 4×4–3×5=16–15=1 4 \times 4 – 3 \times 5 = 16 – 15 = 1
  • 45 \frac{4}{5} と 11 \frac{1}{1} : 1×5–4×1=5–4=1 1 \times 5 – 4 \times 1 = 5 – 4 = 1

全ての隣接する分数に対して、fi+1gi–figi+1=1 f_{i+1}g_i – f_ig_{i+1} = 1 が成り立つことが確認できました。

3.3. 例題3（分数の総数）

ファレイ数列 F5 F_5 に含まれる分数の総数 ∣F5∣ |F_5| を求めなさい。

∣F5∣=1+∑k=15ϕ(k) |F_5| = 1 + \sum_{k=1}^{5} \phi(k)

ここで、ϕ(k) \phi(k) はオイラーのトーシェント関数です。各 k k に対して ϕ(k) \phi(k) の値を計算し、最終的な ∣F5∣ |F_5| の値を求めなさい。

ϕ(1)=1,ϕ(2)=1,ϕ(3)=2,ϕ(4)=2,ϕ(5)=4 \phi(1) = 1, \quad \phi(2) = 1, \quad \phi(3) = 2, \quad \phi(4) = 2, \quad \phi(5) = 4

∣F5∣=1+(1+1+2+2+4)=11 |F_5| = 1 + (1 + 1 + 2 + 2 + 4) = 11

実際にF5F_5を列挙してみると、

F5={01,15,14,13,25,12,35,23,34,45,11} F_5 = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right\}

はるか
はるか
ちゃんと計算と数えた数が一致する。
ホームに戻る