法里數列

數學上，n階的法里數列是0和1之間最簡分數的數列，由小至大排列，每個分數的分母不大於n。每個法里數列從0開始，至1結束，寫作⁰⁄₁和¹⁄₁，但有些人不把這兩項包括進去。有時法里數列也稱為法里級數，嚴格來說這名字不正確，因為法里數列的項不會加起來。

例子

1至8階的法里數列如下：

F₁ = {⁰⁄₁, ¹⁄₁}

F₂ = {⁰⁄₁, ¹⁄₂, ¹⁄₁}

F₃ = {⁰⁄₁, ¹⁄₃, ¹⁄₂, ²⁄₃, ¹⁄₁}

F₄ = {⁰⁄₁, ¹⁄₄, ¹⁄₃, ¹⁄₂, ²⁄₃, ³⁄₄, ¹⁄₁}

F₅ = {⁰⁄₁, ¹⁄₅, ¹⁄₄, ¹⁄₃, ²⁄₅, ¹⁄₂, ³⁄₅, ²⁄₃, ³⁄₄, ⁴⁄₅, ¹⁄₁}

F₆ = {⁰⁄₁, ¹⁄₆, ¹⁄₅, ¹⁄₄, ¹⁄₃, ²⁄₅, ¹⁄₂, ³⁄₅, ²⁄₃, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ¹⁄₁}

F₇ = {⁰⁄₁, ¹⁄₇, ¹⁄₆, ¹⁄₅, ¹⁄₄, ²⁄₇, ¹⁄₃, ²⁄₅, ³⁄₇, ¹⁄₂, ⁴⁄₇, ³⁄₅, ²⁄₃, ⁵⁄₇, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ⁶⁄₇, ¹⁄₁}

F₈ = {⁰⁄₁, ¹⁄₈, ¹⁄₇, ¹⁄₆, ¹⁄₅, ¹⁄₄, ²⁄₇, ¹⁄₃, ³⁄₈, ²⁄₅, ³⁄₇, ¹⁄₂, ⁴⁄₇, ³⁄₅, ⁵⁄₈, ²⁄₃, ⁵⁄₇, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ⁶⁄₇, ⁷⁄₈, ¹⁄₁}

歷史

「法里數列」歷史頗為稀奇。 — Hardy & Wright (1979) 第三章

……又一次，數學關係的名字取自一個人，但記錄所載這人不是其發現者。 — Beiler (1964) 第十六章

法里數列是以英國地質學家老約翰·法里得名，他關於這數列的信刊登在1816年的《哲學雜誌》。法里猜測這數列的每一項都是相鄰兩項的中間分數；不過，以所知道的資料，他沒有證明這個性質。法里的信給柯西讀了，就給了一個證明在他的《數學習題》，把這結果歸到法里上。其實，另一位數學家 C. Haros 曾在1802年發表了相類似的結果，幾乎可以肯定法里和柯西都沒看過。所以，法里的名字給了這個數列，是歷史的一次意外。

性質

數列長度

n階的法里數列${\displaystyle F_{n}}$ 包含了較低階的法里數列的全部項，特別是它包含${\displaystyle F_{n-1}}$ 的全部項，和與n互質的每個數的相應分數。所以${\displaystyle F_{6}}$ 包含了${\displaystyle F_{5}}$ 和分數¹⁄₆及⁵⁄₆。對大於1的n，其法里數列的中間項必定是¹⁄₂。

從上，${\displaystyle F_{n}}$ 和${\displaystyle F_{n-1}}$ 的長度的關係，可以用歐拉函數${\displaystyle \varphi (n)}$ 描述：

${\displaystyle |F_{n}|=|F_{n-1}|+\varphi (n)}$ 。

從${\displaystyle |F_{1}|=2}$ 這項資料，可以推導出${\displaystyle F_{n}}$ 的長度公式：

${\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)}$ 。

${\displaystyle |F_{n}|}$ 的漸近行為是：

${\displaystyle |F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}}$ 。

數列鄰項

法里數列的相鄰分數項有下述性質：

若^a⁄_b和^c⁄_d是法里數列的鄰項，而有^a⁄_b < ^c⁄_d，則它們之差^c⁄_d − ^a⁄_b是¹⁄_bd。由於

${\displaystyle {\frac {c}{d}}-{\frac {a}{b}}={\frac {bc-ad}{bd}}}$ ，

上文就等於是說

bc − ad = 1。

例如¹⁄₃和²⁄₅在${\displaystyle F_{5}}$ 中是鄰項，它們之差為¹⁄₁₅。

這結果的逆命題也成立。若

bc − ad = 1，

其中a,b,c和d為正整數，及有a < b和c < d，則^a⁄_b和^c⁄_d在階為${\displaystyle \max(b,d)}$ 的法里數列中是鄰項。

若^p⁄_q在某法里數列的鄰項是^a⁄_b和^c⁄_d，及

^a⁄_b < ^p⁄_q < ^c⁄_d，

則^p⁄_q是^a⁄_b和^c⁄_d的中間分數。換句話說，

${\displaystyle {\frac {p}{q}}={\frac {a+c}{b+d}}}$ 。

又若^a⁄_b和^c⁄_d在某法里數列是鄰項，則當法里數列的階增加，它們間出現的第一項是

${\displaystyle {\frac {a+c}{b+d}}}$ ，

而這項第一次出現在b+d階的法里數列中。

例如在¹⁄₃和²⁄₅間出現的第一項是³⁄₈，在${\displaystyle F_{8}}$ 出現。

Stern-Brocot樹是一個資料結構，顯出如何從0 (= ⁰⁄₁)和1 (= ¹⁄₁)開始，以取中間分數來構成法里數列。

法里數列中的鄰項分數，它們的連分數表示形式也密切相關。每個分數都有兩個連分數表示，一個的尾項為1，另一個則大於1。考慮^p⁄_q，它第一次於${\displaystyle F_{q}}$ 出現。以連分數表示為

${\displaystyle [0;a_{1},a_{2},...,a_{n-1},a_{n},1]}$ ，或

${\displaystyle [0;a_{1},a_{2},...,a_{n-1},a_{n}+1]}$ ，

則^p⁄_q在${\displaystyle F_{q}}$ 中最接近的鄰項（這是兩鄰項中分母較大的）表示為連分數是

${\displaystyle [0;a_{1},a_{2},...,a_{n}]}$ ，

而另一鄰項則會表示為

${\displaystyle [0;a_{1},a_{2},...,a_{n-1}]}$ 。

例如³⁄₈有兩個連分數表示：[0;2,1,1,1]和[0;2,1,2]，而它在${\displaystyle F_{8}}$ 中的鄰項為²⁄₅，可寫成[0;2,1,1]；和¹⁄₃，可寫成[0;2,1]。

福特圓

法里數列和福特圓（英语：Ford circle）之間有個有趣關連。

對每個最簡分數^p⁄_q，有福特圓C[^p⁄_q]，以${\displaystyle {\frac {1}{2q^{2}}}}$ 為半徑，以${\displaystyle \left({\frac {p}{q}},{\frac {1}{2q^{2}}}\right)}$ 為圓心。兩個不同分數的福特圓一是分開，一是相切，但不會相交。若0 < ^p⁄_q < 1，則與相切的福特圓正好是在某一法里數列中與^p⁄_q為鄰項的分數。

例如C[²⁄₅]與C[¹⁄₂]，C[¹⁄₃]，C[³⁄₇]，C[³⁄₈]等相切。

F1--F8的福特圓圖像如下：

 

外部連結

• Farey Sequence （页面存档备份，存于互联网档案馆）