フィボナッチ列

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
黄金比の傾き\varphiまたは\varphi-1をもつ直線が切り出す列の性質

フィボナッチ列(フィボナッチれつ、Fibonacci word)とは、フィボナッチ数の加算の代わりに文字列連結を用いて得られる2進列(または2種類のアルファベットからなる文字列)である。 フィボナッチ文字列とも呼ばれる。

“フィボナッチ列”は、1が2回以上連続しないL-systemのひとつとして言及されてきた。

定義[編集]

S_0を"0"、S_1を"01"と定める。そしてS_n = S_{n-1}S_{n-2}(1つ前の文字列と2つ前の文字列の文字列連結)とする。

無限フィボナッチ列は極限S_{\infty}である。

フィボナッチ列の一覧[編集]

S_0    0

S_1    0, 1

S_2    0, 1, 0

S_3    0, 1, 0, 0, 1

S_4    0, 1, 0, 0, 1, 0, 1, 0

S_5    0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1

...

無限フィボナッチ列の最初の一部:

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, ...

各項の閉じた式[編集]

n 番目の項は次の閉じた式 (Closed-form expression) によって表される。

2+\left\lfloor {\left( {n + 1} \right)\,\varphi} \right\rfloor - \left\lfloor {\left( {n + 2} \right)\,\varphi } \right\rfloor

ただし\varphi黄金比であり、\left\lfloor x \right\rfloor床関数である。 (オンライン整数列大辞典の数列 A003849)。

置換規則[編集]

Sn から Sn + 1を求めるもう1つの方法は、Snの0を0,1に、1を0に置き換えることである。

議論[編集]

フィボナッチ列はフィボナッチ数列再帰的定義における加算を文字列連結に置き換えた文字列になっている。 これに従い、SnFn + 2n + 2番目のフィボナッチ数)に等しい。 また、Snにおける1の数はFnに等しく、Snにおける0の数はFn + 1に等しい。

その他の性質[編集]

  • 無限フィボナッチ列は周期的でない
  • フィボナッチ列の最後の2文字は"01"と"10"が交互に現れる
  • フィボナッチ列の最後の2文字を取り除く、もしくは最後の2文字の逆転列を最初に付け加えると回文になる。たとえば01S_4 = 0101001010で、これは回文である
  • 無限フィボナッチ列において、(文字列の長さ)/(0の数)は\phi黄金比)であり、0と1の比もこれに等しい
  • 11000は発生しない
  • 無限フィボナッチ列は循環(どの一部の文字列も無限に再び現れる)する
  • フィボナッチ列は、黄金比の傾き\phiまたは\phi-1をもつ直線が切り出す列として特徴付けられる(上図)
  • フィボナッチ列の各項を各桁に割り当ててできる十進数0.010010100...は超越数である
  • "1"はUpper Wythoff sequence (オンライン整数列大辞典の数列 A001950): \lfloor n\phi^2\rfloorの場所に現れる
  • "0"はLower Wythoff sequence (オンライン整数列大辞典の数列 A000201): \lfloor n\phi\rfloorの場所に現れる

参考文献[編集]

  • Lothaire, M (1997), Combinatorics on Words, Cambridge Mathematical Library, ISBN 978-0521599245 .

外部リンク[編集]