フィボナッチ数列

フィボナッチ ワードは、2 進数の特定のシーケンス(または任意の 2 文字のアルファベットの記号)です。フィボナッチ数が繰り返し加算によって形成されるのと同じように、フィボナッチ ワードは繰り返し連結によって形成されます。

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

「フィボナッチ語」という名前は、2 つの 1 が繰り返されない 0 と 1 の文字列で構成される形式言語 Lのメンバーを指すためにも使用されています。特定のフィボナッチ語のプレフィックスはすべてLに属しますが、他の多くの文字列も同様に属します。L には、可能な各長さのフィボナッチ数のメンバーがあります。

を「0」、を「01」にします。これで（前のシーケンスとその前のシーケンスの連結です）。 ${\displaystyle S_{0}}$${\displaystyle S_{1}}$${\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、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、0、1、0、1、0、0、1、0、1、... ( OEISのシーケンスA003849 )

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

あるいは、次のプロセスによって無限フィボナッチ語全体を直接生成することも考えられます。カーソルが 1 桁の 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、0、1、1、0、1、0、1、1、0、1、 1、0、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であり、 S _n内の 0 の数はF _{n  +1}です。

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

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

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

• Adamczewski, Boris; Bugeaud, Yann (2010)、「8. 超越性とディオファントス近似」、Berthé, Valérie、Rigo, Michael (編)、『組合せ論、オートマトン、数論』、Encyclopedia of Mathematics and its Applications、第 135 巻、ケンブリッジ: Cambridge University Press、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。
• Kimberling, Clark (2004)、「単語と数字の集合の順序付け: フィボナッチの場合」、Howard, Frederic T. (編)、『フィボナッチ数の応用』第 9 巻: 第 10 回国際研究会議フィボナッチ数とその応用に関する議事録、ドルドレヒト: Kluwer Academic Publishers、pp. 137–144、doi :10.1007/978-0-306-48517-6_14、ISBN 978-90-481-6545-2、MR  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。
• ラミレス、ホセ L.、ルビアーノ、グスタボ N.、デ カストロ、ロドリゴ (2014)、「フィボナッチ ワード フラクタルおよびフィボナッチ スノーフレークの一般化」、理論計算機科学、528 :40–56、arXiv : 1212.1368、doi :10.1016/j.tcs.2014.02.003、MR  3175078、S2CID  17193119。

• ロン・ノットのサイトにある詳細で分かりやすい説明
• ワイスシュタイン、エリック W.、「ラビット シーケンス」、MathWorld
• フィボナッチワード（最初の 200,000 ビット）YouTube