フィボナッチ列

黄金比の傾き φ {\displaystyle \varphi } または φ {\displaystyle \varphi } -1をもつ直線が切り出す列の性質

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

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

定義

S 0 {\displaystyle S_{0}} を"0"、 S 1 {\displaystyle S_{1}} を"01"と定める。そして S n = S n − 1 S n − 2 {\displaystyle S_{n}=S_{n-1}S_{n-2}} （1つ前の文字列と2つ前の文字列の文字列連結）とする。

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

フィボナッチ列の一覧

S 0 {\displaystyle S_{0}}    0

S 1 {\displaystyle S_{1}}    0, 1

S 2 {\displaystyle S_{2}}    0, 1, 0

S 3 {\displaystyle S_{3}}    0, 1, 0, 0, 1

S 4 {\displaystyle S_{4}}    0, 1, 0, 0, 1, 0, 1, 0

S 5 {\displaystyle 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 + ⌊ ( n + 1 ) φ ⌋ − ⌊ ( n + 2 ) φ ⌋ {\displaystyle 2+\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor -\left\lfloor {\left({n+2}\right)\,\varphi }\right\rfloor }

ただし φ {\displaystyle \varphi } は黄金比であり、 ⌊ x ⌋ {\displaystyle \left\lfloor x\right\rfloor } は床関数である。 （オンライン整数列大辞典の数列 A003849）。

置換規則

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

議論

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

その他の性質

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

参考文献

  • Lothaire, M (1997), Combinatorics on Words, Cambridge Mathematical Library, ISBN 978-0521599245 .
  • Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, ISBN 9780521823326 .

外部リンク

  • A detailed and accessible description, on Ron Knott's site
  • Repetitions in the infinite Fibonacci word, by Mignosi and Pirillo
  • Sequence A003849 The Fibonacci word in the On-Line Encyclopedia of Integer Sequences
  • The Rabbit sequence on Mathworld
  • Fibonacci Word (First 200,000 bits) - YouTube