■ファレイ数列とスターン数列(その4)

 既約分数をすべて作り上げる方法がスターン・ブロコット木である.それはまず[0/1,1/1]からはじめ,漸次,隣接する2項p/qとr/sの間に中間分数

  (p+r)/(q+s)

を挿入する操作を可能な限り続けることによって得られる.

===================================

[0/1,1/0](長さ2)

→[0/1,1/1,1/0](1個挿入,長さ3)

→[0/1,1/2,1/1,2/1,1/0](2個挿入,長さ5)

→[0/1,1/3,1/2,2/3,1/1,3/2,2/1,3/1,1/0](4個挿入,長さ9)

→[0/1,1/4,1/3,2/5,1/2,3/5,2/3,3/4,1/1,4/3,3/2,5/3,2/1,5/2,3/1,4/1,1/0](8個挿入,長さ17)

→[0/1,1/5,1/4,2/7,1/3,3/8,2/5,3/7,1/2,4/7,3/5,5/8,2/3,5/7,3/4,4/5,1/1,5/4,4/3,7/5,3/2,8/5,5/3,7/4,2/1,7/3,5/2,8/3,3/1,7/2,4/1,5/1,1/0](16個挿入,長さ33)

が得られる.(長さは2^n+1)

 この数列に現れるに中間分数

  p/q<(p+r)/(q+s)<r/s

において,p,q,r,sのすべてが奇数であれば偶数/偶数となるが,常に既約で,しかもすべての分数がちょうど1回だけ現れるという不思議さがある.また,

  qr−ps=1が成り立つ.

 ファレイ数列でも

  qr−ps=1

は成り立つが,スターン・ブロコット数列から不必要な枝を取り除いた部分木となっているのである.スターン・ブロコット数列のほうがファレイ数列よりももっとおもしろい性質をもっている!

===================================