法里數列

维基百科,自由的百科全书
跳转至: 导航搜索

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

例子[编辑]

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

F1 = {01, 11}
F2 = {01, 12, 11}
F3 = {01, 13, 12, 23, 11}
F4 = {01, 14, 13, 12, 23, 34, 11}
F5 = {01, 15, 14, 13, 25, 12, 35, 23, 34, 45, 11}
F6 = {01, 16, 15, 14, 13, 25, 12, 35, 23, 34, 45, 56, 11}
F7 = {01, 17, 16, 15, 14, 27, 13, 25, 37, 12, 47, 35, 23, 57, 34, 45, 56, 67, 11}
F8 = {01, 18, 17, 16, 15, 14, 27, 13, 38, 25, 37, 12, 47, 35, 58, 23, 57, 34, 45, 56, 67, 78, 11}

歷史[编辑]

「法里數列」歷史頗為稀奇。 — Hardy & Wright (1979) 第三章
……又一次,數學關係的名字取自一個人,但記錄所載這人不是其發現者。 — Beiler (1964) 第十六章

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

性質[编辑]

數列長度[编辑]

n階的法里數列F_n包含了較低階的法里數列的全部項,特別是它包含F_{n - 1}的全部項,和與n互質的每個數的相應分數。所以F_6包含了F_5和分數1656。對大於1的n,其法里數列的中間項必定是12

從上,F_nF_{n - 1}的長度的關係,可以用歐拉函數\varphi(n)描述:

|F_n| = |F_{n-1}| + \varphi(n)

|F_1| = 2這項資料,可以推導出F_n的長度公式:

|F_n| = 1 + \sum_{m=1}^n \varphi(m)

|F_n|的漸近行為是:

|F_n| \sim \frac {3n^2}{\pi^2}

數列鄰項[编辑]

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

abcd是法里數列的鄰項,而有ab < cd,則它們之差cd − ab1bd。由於

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

上文就等於是說

bc − ad = 1。

例如1325F_5中是鄰項,它們之差為115

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

bc − ad = 1,

其中a,b,cd為正整數,及有a < bc < d,則abcd在階為\max(b,d)的法里數列中是鄰項。

pq在某法里數列的鄰項是abcd,及

ab < pq < cd

pqabcd中間分數。換句話說,

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

又若abcd在某法里數列是鄰項,則當法里數列的階增加,它們間出現的第一項是

\frac{a+c}{b+d}

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

例如在1325間出現的第一項是38,在F_8出現。

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

法里數列中的鄰項分數,它們的連分數表示形式也密切相關。每個分數都有兩個連分數表示,一個的尾項為1,另一個則大於1。考慮pq,它第一次於F_q出現。以連分數表示為

[0;a_1, a_2, ..., a_{n-1}, a_n, 1],或
[0;a_1, a_2, ..., a_{n-1}, a_n + 1]

pqF_q中最接近的鄰項(這是兩鄰項中分母較大的)表示為連分數是

[0;a_1, a_2, ..., a_n]

而另一鄰項則會表示為

[0;a_1, a_2, ..., a_{n-1}]

例如38有兩個連分數表示:[0;2,1,1,1]和[0;2,1,2],而它在F_8中的鄰項為25,可寫成[0;2,1,1];和13,可寫成[0;2,1]。

福特圓[编辑]

法里數列和福特圓之間有個有趣關連。

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

例如C[25]與C[12],C[13],C[37],C[38]等相切。

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

Ford-Circles.gif

外部連結[编辑]