フィボナッチ数列

${\displaystyle S_{10}}$

${\displaystyle S_{17}}$

フィボナッチ曲線は、フィボナッチの10番目と17番目の単語から作られています^{[ 1 ]}

数学、特に単語の組み合わせ論において、フィボナッチ単語とは、フィボナッチ数列が繰り返し加算によって形成されるのと同様に、繰り返し連結によって形成される特定の二進数（または任意の2文字アルファベットの記号）の列のことである。

これはシュトゥルム語の典型的な例であり、特に形態論的語の典型例である。

「フィボナッチ語」という名称は、同じ数字の1が2つ以上繰り返されない、0と1の文字列からなる形式言語Lの要素を指す場合にも用いられます。特定のフィボナッチ語の接頭辞はすべてLに属しますが、他の多くの文字列も同様です。Lは、考えられるすべての長さの要素をフィボナッチ数個持ちます。

させて${\displaystyle S_{0}}$「0」であり、${\displaystyle S_{1}}$「01」になります。${\displaystyle S_{n}=S_{n-1}S_{n-2}}$（前のシーケンスと、その前のシーケンスを連結したもの）

無限のフィボナッチ語は限界です${\displaystyle S_{\infty }}$つまり、各要素を含む（一意の）無限シーケンス${\displaystyle S_{n}}$有限の場合${\displaystyle n}$接頭辞として。

上記の定義から項目を列挙すると、次のようになります。

${\displaystyle S_{0}}$  0

${\displaystyle S_{1}}$  01

${\displaystyle S_{2}}$  010

${\displaystyle S_{3}}$  01001

${\displaystyle S_{4}}$  01001010

${\displaystyle S_{5}}$  0100101001001

...

無限のフィボナッチ数列の最初の数要素は次のとおりです。

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, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 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, ... ( OEISのシーケンスA003849 )

単語のn^番目の数字は${\displaystyle 2+\lfloor n\varphi \rfloor -\lfloor (n+1)\varphi \rfloor }$どこ${\displaystyle \varphi }$は黄金比であり、${\displaystyle \lfloor \,\ \rfloor }$は床関数（OEISのシーケンスA003849）です。結果として、無限のフィボナッチワードは、傾きの直線の切断シーケンスによって特徴付けられます。${\displaystyle 1/\varphi }$または${\displaystyle \varphi -1}$上の図を参照してください。

S _nからS _{n +1}へ変換する別の方法は、 S _nの各記号 0 をS _{n +1}の連続する記号 0、1 のペアに置き換え、S _nの各記号 1 をS _{n +1}の単一の記号 0 に置き換えることです。

あるいは、以下の手順で無限のフィボナッチ数列全体を直接生成することも考えられます。まず、カーソルを数字の0に合わせます。次に、各ステップで、カーソルが0を指している場合は、単語の末尾に「1, 0」を追加し、カーソルが1を指している場合は、単語の末尾に「0」を追加します。どちらの場合も、カーソルを右に1つ移動してステップを完了します。

同様の無限ワード（ウサギシーケンスと呼ばれることもある）は、異なる置換ルールを持つ同様の無限プロセスによって生成されます。カーソルが0を指しているときは1を追加し、カーソルが1を指しているときは0、1を追加します。結果として得られるシーケンスは、

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

しかし、この数列はフィボナッチ数列とは、0を1に置き換え、位置を1つずらすという些細な点でしか違いません。

いわゆるラビットシーケンスの閉形式表現：

単語のn^番目の数字は${\displaystyle \lfloor n\varphi \rfloor -\lfloor (n-1)\varphi \rfloor -1.}$

この単語は、同名の有名な数列（フィボナッチ数列）と関連があり、帰納的定義における整数の加算が文字列の連結に置き換えられています。これにより、 S _nの長さはF _{n +2}、つまり ( n +2) 番目_のフィボナッチ数になります。また、 S _nに含まれる 1 の数はF _{n 、 0}の数はF n ₊₁です。

• 無限のフィボナッチ語は周期的ではなく、究極的に周期的でもない。^{[ 2 ]}
• フィボナッチ数列の単語の最後の2文字は、「01」と「10」が交互に現れる。
• フィボナッチ数列の最後の 2 文字を削除するか、最後の 2 文字の補数を接頭辞として付けると、回文が生成されます。例: 01 S ₄ = 0101001010 は回文です。したがって、無限フィボナッチ数列の回文密度は 1/φ であり、φ は黄金比です。これは非周期的な単語で可能な最大の値です。^{[ 3 ]}
• 無限のフィボナッチ数列では、(文字数)/(ゼロの数)の比はφであり、ゼロとイチの比も同様である。^{[ 4 ]}
• 無限フィボナッチ語はバランスの取れた数列です。フィボナッチ語の任意の場所で同じ長さの2つの因数を取ります。それらのハミング重み（「1」の出現回数）の差は1を超えることはありません。^{[ 5 ]}
• サブワード11と000は出現しない。^{[ 6 ]}
• 無限フィボナッチ語の複雑性関数は n + 1 です。つまり、 長さnの異なるサブワードがn  + 1 個含まれています。例: 長さ 3 の異なるサブワードは 4 つあります。「001」、「010」、「100」、「101」です。また、非周期的であるため、「最小複雑性」を持ち、したがって傾きを持つシュトゥルム語です^{[ 7 ]}。${\displaystyle 1/\varphi }$無限フィボナッチ語は、指示数列(1,1,1,....)によって生成される標準語です。
• 無限フィボナッチ数列は反復的である。つまり、すべての部分語が無限回出現する。
• もし${\displaystyle u}$が無限フィボナッチ語の部分語である場合、その逆も部分語であり、次のように表されます。${\displaystyle u^{R}}$。
• もし${\displaystyle u}$は無限フィボナッチ語の部分語であり、その最小周期は${\displaystyle u}$はフィボナッチ数です。
• 連続する2つのフィボナッチ数の連結は「ほぼ可換」である。${\displaystyle S_{n+1}=S_{n}S_{n-1}}$そして${\displaystyle S_{n-1}S_{n}}$最後の2文字だけが異なる。
• 無限のフィボナッチ数列の数字で構成された数字 0.010010100... は超越数です。
• 文字「1」は、アッパー・ウィトフ数列（OEISのA001950数列）の連続する値によって示される位置に見つけることができます。${\displaystyle \lfloor n\varphi ^{2}\rfloor }$
• 文字「0」は、下位ワイトホフ数列（OEISのA000201数列）の連続する値によって示される位置にあります。${\displaystyle \lfloor n\varphi \rfloor }$
• 分布${\displaystyle n=F_{k}}$単位円上の点を黄金角で時計回りに順に並べたもの${\displaystyle {\frac {2\pi }{\varphi ^{2}}}}$2つの長さのパターンを生成します${\displaystyle {\frac {2\pi }{\varphi ^{k-1}}},{\frac {2\pi }{\varphi ^{k}}}}$単位円上。上記のフィボナッチ数列の生成過程は円弧の連続分割に直接対応するものではありませんが、このパターンは${\displaystyle S_{k-1}}$パターンが時計回りに最初の点に最も近い点から始まる場合、0は長距離に対応し、1は短距離に対応する。
• 無限フィボナッチ語には、3 つの連続する同一のサブワードの繰り返しが含まれますが、4 つのサブワードの繰り返しは含まれません。^{[ 2 ]}無限フィボナッチ語の臨界指数は ${\displaystyle 2+\varphi \approx 3.618}$^{[ 8 ]}これは、すべてのシュトゥルム語の中で最小の指数（または臨界指数）です。
• 無限に続くフィボナッチ数列は、文字列中の繰り返しを検出するアルゴリズムにとって最悪のケースとしてしばしば挙げられる。
• 無限フィボナッチ語は、{0,1}* において自己準同型写像0 → 01、1 → 0によって生成される形態語である。 ^{[ 9 ]}
• フィボナッチ数列のn番目の要素、${\displaystyle s_{n}}$nのゼッケンドルフ表現(特定のフィボナッチ数列の合計) に1 が含まれる場合は 1 、含まれない場合は 0 となります。
• フィボナッチワードの桁は、フィボナッチバイナリー数 の列を2で割った余りを取ることによって得られます。 ^{[ 10 ]}
• 無限フィボナッチ数列は、11、000、10101、および4のべき乗を避ける唯一の無限二進数である。

フィボナッチ数列に基づく構造は現在、準結晶などの非周期的な秩序を持つ物理システムをモデル化するために使用されており、この文脈ではフィボナッチという言葉はフィボナッチ準結晶とも呼ばれています。^{[ 11 ]}結晶成長技術は、フィボナッチ層状結晶を成長させ、その光散乱特性を研究するために使用されています。^{[ 12 ]}

• 数学と芸術
• トリボナッチ数列

• Adamczewski, Boris; Bugeaud, Yann (2010)、「8. 超越とディオファントス近似」、Berthé, Valérie ; Rigo, Michael (編)、『組み合わせ論、オートマタ、数論』、数学とその応用百科事典、第135巻 、ケンブリッジ：ケンブリッジ大学出版局、p.  443、ISBN 978-0-521-51597-9、Zbl 1271.11073 。
• アルーシュ、ジャン＝ポール、シャリット、ジェフリー(2003)、『自動シーケンス：理論、応用、一般化』、ケンブリッジ大学出版局、ISBN 978-0-521-82332-6。
• Berstel, Jean (1986)、「フィボナッチ数列の単語 ― 概観」（PDF）、Rozenberg, G.、Salomaa, A. (編)『The Book of L』、Springer、pp. 13–27、doi : 10.1007/978-3-642-95486-3_2、ISBN  9783642954863
• Bombieri, E. ; Taylor, JE (1986)、「どの物質分布が回折するか？初期調査」(PDF)、Le Journal de Physique、47 (C3): 19–28、doi : 10.1051/jphyscol:1986303、MR 0866320、S2CID 54194304  。
• Dharma-wardana, MWC; MacDonald, AH; Lockwood, DJ; Baribeau, J.-M.; Houghton, DC (1987)、「フィボナッチ超格子におけるラマン散乱」、Physical Review Letters、58 (17): 1761–1765、Bibcode : 1987PhRvL..58.1761D、doi : 10.1103/physrevlett.58.1761、PMID 10034529 。
• キンバーリング、クラーク（2004）「単語と数の集合の順序付け：フィボナッチ数列の場合」、ハワード、フレデリック T.（編）『フィボナッチ数の応用、第9巻：第10回フィボナッチ数とその応用に関する国際研究会議議事録』、ドルトレヒト：クルーワー・アカデミック・パブリッシャーズ、pp. 137–144、doi：10.1007/978-0-306-48517-6_14、ISBN  978-90-481-6545-2MR 2076798​ 。
• ロテール、M. (1997)、「単語の組み合わせ論」、数学とその応用百科事典、第 17巻（第2 版）、ケンブリッジ大学出版局、ISBN 0-521-59924-5。
• ロテール、M. (2011)、「単語の代数的組み合わせ論」、数学とその応用百科事典、第 90巻、ケンブリッジ大学出版局、ISBN 978-0-521-18071-92002年版ハードカバーの復刻版。
• de Luca, Aldo (1995)、「フィボナッチ数列の除算特性」、Information Processing Letters、54 (6): 307–312、doi : 10.1016/0020-0190(95)00067-M。
• ミニョーシ、F. Pirillo, G. (1992)、「フィボナッチ無限ワードの繰り返し」、Informatique Théorique et Application、26 (3): 199–204、doi : 10.1051/ita/1992260301991。
• Ramírez, José L.; Rubiano, Gustavo N.; De Castro, Rodrigo (2014)、「フィボナッチワードフラクタルとフィボナッチスノーフレークの一般化」、Theoretical Computer Science、528 : 40–56、arXiv : 1212.1368、doi : 10.1016/j.tcs.2014.02.003、MR 3175078、S2CID 17193119  。

• ロン・ノットのサイトには、詳細かつ分かりやすい説明が掲載されています。
• ワイススタイン、エリック・W.、「ラビットシーケンス」、MathWorld
• フィボナッチワード（最初の20万ビット）YouTube