フィボナッチ列のソースを表示

[[image:Fibonacci_word_cutting_sequence.png|thumb|350px|[[黄金比]]の傾き<math>\varphi</math>または<math>\varphi</math>-1をもつ直線が切り出す列の性質]]
'''フィボナッチ列'''（フィボナッチれつ、Fibonacci word）とは、[[フィボナッチ数]]の加算の代わりに[[文字列連結]]を用いて得られる[[二進法|2進]]列（または2種類の[[アルファベット]]からなる文字列）である。
フィボナッチ文字列とも呼ばれる。

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

== 定義 ==
<math>S_0</math>を"0"、<math>S_1</math>を"01"と定める。そして<math>S_n = S_{n-1}S_{n-2}</math>（1つ前の文字列と2つ前の文字列の文字列連結）とする。

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

== フィボナッチ列の一覧 ==
<math>S_0</math> &nbsp;&nbsp; 0

<math>S_1</math> &nbsp;&nbsp; 0, 1

<math>S_2</math> &nbsp;&nbsp; 0, 1, 0

<math>S_3</math> &nbsp;&nbsp; 0, 1, 0, 0, 1

<math>S_4</math> &nbsp;&nbsp; 0, 1, 0, 0, 1, 0, 1, 0

<math>S_5</math> &nbsp;&nbsp; 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'' 番目の項は次の閉じた式 ([[:en:Closed-form expression|Closed-form expression]]) によって表される。
{{Indent|<math>2+\left\lfloor {\left( {n + 1} \right)\,\varphi} \right\rfloor - \left\lfloor {\left( {n + 2} \right)\,\varphi } \right\rfloor</math>}}
ただし<math>\varphi</math>は[[黄金比]]であり、<math>\left\lfloor x \right\rfloor</math>は[[床関数]]である。 （{{OEIS|A003849}}）。

== 置換規則 ==
''S''<sub>''n''</sub> から ''S''<sub>''n''&nbsp;+&nbsp;1</sub>を求めるもう1つの方法は、''S''<sub>''n''</sub>の0を0,1に、1を0に置き換えることである。

== 議論 ==
フィボナッチ列は[[フィボナッチ数列]]の[[再帰的定義]]における加算を文字列連結に置き換えた文字列になっている。
これに従い、''S''<sub>''n''</sub>の長さは''F''<sub>''n''&nbsp;+&nbsp;2</sub>（''n''&nbsp;+&nbsp;2番目の[[フィボナッチ数]]）に等しい。
また、''S''<sub>''n''</sub>における1の数は''F''<sub>''n''</sub>に等しく、''S''<sub>''n''</sub>における0の数は''F''<sub>''n''&nbsp;+&nbsp;1</sub>に等しい。

== その他の性質 ==
* 無限フィボナッチ列は周期的でない
* フィボナッチ列の最後の2文字は"01"と"10"が交互に現れる
* フィボナッチ列の最後の2文字を取り除く、もしくは最後の2文字の逆転列を最初に付け加えると[[回文]]になる。たとえば01<math>S_4</math> = 0101001010で、これは回文である
* 無限フィボナッチ列において、(文字列の長さ)/(0の数)は<math>\varphi</math>（[[黄金比]]）であり、0と1の比もこれに等しい
* ''11''と''000''は発生しない
* 無限フィボナッチ列は循環（どの一部の文字列も無限に再び現れる）する
* フィボナッチ列は、黄金比の傾き<math>\varphi</math>または<math>\varphi-1</math>をもつ直線が切り出す列として特徴付けられる（上図）
* フィボナッチ列の各項を各桁に割り当ててできる十進数0.010010100...は[[超越数]]である
* "1"はUpper Wythoff sequence ({{OEIS|A001950}}): <math>\lfloor n\varphi^2\rfloor</math>の場所に現れる
* "0"はLower Wythoff sequence ({{OEIS|A000201}}): <math>\lfloor n\varphi\rfloor</math>の場所に現れる

== 参考文献 ==
*{{citation
 | last = Lothaire | first = M
 | isbn = 978-0521599245
 | series = Cambridge Mathematical Library
 | title = Combinatorics on Words
 | year = 1997}}.

*{{citation
 | last1 = Allouche | first1 = Jean-Paul
 | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit
 | isbn = 9780521823326
 | publisher = Cambridge University Press
 | title = Automatic Sequences: Theory, Applications, Generalizations
 | year = 2003}}.

== 外部リンク ==
* [http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibrab.html A detailed and accessible description, on Ron Knott's site]
* [http://cat.inist.fr/?aModele=afficheN&cpsidt=5478956 Repetitions in the infinite Fibonacci word, by Mignosi and Pirillo]
* Sequence {{OEIS2C|A003849}} ''The Fibonacci word'' in the [[On-Line Encyclopedia of Integer Sequences]]
* [http://mathworld.wolfram.com/RabbitSequence.html The Rabbit sequence on Mathworld]
* {{youtube|id=ZDGGEQqSXew|title=Fibonacci Word (First 200,000 bits)}}

{{DEFAULTSORT:ふいほなつちれつ}}
[[Category:整数の類]]
[[Category:数学に関する記事]]