導入
フィボナッチ ワードは、任意の 2 文字のアルファベットから抽出された文字または記号の特定のシーケンスです。フィボナッチワードは連結演算に相当し、フィボナッチ数は加算に相当します。
意味
アルファベット {0;1} から、 S 1 = “1” およびS 2 = “0” とします。次に、フィボナッチ ワードS n = S n − 1 S n − 2 (前の 2 つの項の連結)。
無限のフィボナッチワードが限界です
フィボナッチ ワードは、加算を連結に置き換えることにより、フィボナッチ数列との類似によって命名されました。
連続するフィボナッチ ワードは次のとおりです。
- S11
- S20
- S301
- S4010
- S5 01001
- S6 01001010
- S 7 0100101001001
- S 8 010010100100101001010
- …
したがって、無限フィボナッチ ワードは次のように始まります: 010010100100101001010010010100100101001010010010100101… この無限シーケンスは OEIS シーケンス A003849 です。
文献には、「0」と「1」を反転したフィボナッチワードと同じ「ラビットシーケンス」という用語も見つかります。したがって、ウサギの残りの部分は 101101011… で始まります。
フィボナッチワードフラクタル
ウィキメディア コモンズには、フィボナッチの単語 フラクタルに関連する無料のメディアがあります。 |
フィボナッチ ワードのフラクタルは、OEDR ルール (奇数偶数描画ルール) をフィボナッチ ワードに適用することによって反復的に構築されます。
この曲線の特性が研究されています。
プロパティ
分析式
フィボナッチワードのn番目の文字は、
置換規則または射
フィボナッチ ワードは射 (または置換) によって定義できます。
フィボナッチ ワードS nから開始して、次のようにワードS n + 1を取得します。
- 文字「1」を「0」に置き換えます
- 文字「0」を「01」に置き換えます
次のように書くこともできます。
S n + 1 = σ( S n ) σは次のように定義される射です。
- σ(1) = 0および
- σ(0) = 01
また、無限フィボナッチ ワードは射σの不動点であるとも言えます。
フィボナッチワードとフィボナッチ数列
フィボナッチワードとフィボナッチ数列は密接に関連しています。各フィボナッチ ワードは前の 2 つのワードを連結したもので、「1」、次に「0」から始まり、フィボナッチ ワードの長さS n はフィボナッチ数F nに相当します。
|と書きます。 Sn | = Fn
| Sn | 長さ.= F n |
|---|---|
| 1 | 1 |
| 0 | 1 |
| 01 | 2 |
| 010 | 3 |
| 01001 | 5 |
| 01001010 | 8 |
| 0100101001001 | 13 |
| 010010100100101001010 | 21 |
同様に、次のことがわかります。
- 「0」の数はF n − 1に相当します。
- 「1」の数はF n − 2に相当します。
さまざまな特性
- 無限フィボナッチワードは周期的ではありません。また、最終的には周期的でもありません。
- フィボナッチ単語の最後の 2 文字は「01」と「10」が交互に続きます。
- フィボナッチ単語の最後の 2 文字を削除すると、回文が得られます。
- フィボナッチ単語の最後の 2 文字の 2 進補数をこの単語の先頭に並べることで、回文が得られます。したがって、01 S 6 = 0101001010 は回文です。
- 無限フィボナッチ ワードでは、比率 (文字の数/「0」の数) は、黄金比φに近づく傾向があります。比率（「0」の数/「1」の数）も同様です。
- フィボナッチ ワードは「バランスが取れている」: フィボナッチ ワード内の任意の場所に同じ長さの 2 つの因数が取られ、一方の「0」の数と他方の「0」の数の差が値を超えることはありません。 1. 注: シュトルミアンのすべての単語はバランスが取れています。
- フィボナッチ ワードには因数 (「サブワード」) 「11」も「000」も見つかりません。
- 無限フィボナッチ ワードでは、長さ k の個別の因子 (サブワード) の数は k+1 です。したがって、無限フィボナッチ ワードはスターミアン ワードです。したがって、長さ 3 の個別の因数は、「001」、「010」、「100」、「101」の 4 つになります。非周期的であるため、この単語は「最小限の複雑さ」と呼ばれます。
- 無限フィボナッチ ワードの各因子は無限回出現します。
- 単語が無限フィボナッチ単語の因数である場合、その逆も同様です。
- 2 つの連続するフィボナッチ ワードの連結は「ほぼ可換」です。したがって、 S n + 1 = S n S n − 1とS n − 1 S n は最後の 2 文字のみが異なります。例: S 8 = S 7 S 6 = (0100101001001)(01001010)およびS 6 S 7 = (01001010)(0100101001001) 。
- フィボナッチ無限ワードは、黄金比φを使用した傾き1/ φ2のスターミアン ワードです。
- したがって、無限フィボナッチ ワードは、傾きφまたはφ − 1 ( φ = 黄金比) の線と整数座標の線との交点のシーケンスによって特徴付けることもできます。上の図を参照してください。
- 数値 0.010010100… は、小数点以下の桁が無限のフィボナッチ語から構築され、超越的です。
- 文字「1」は、Upper Wythoff シーケンス (OEIS スイート A001950) の連続する値によって指定される位置にあります。 $$ {\lfloor n\phi^2\rfloor} $$
- 文字「0」は、Lower Wythoff シーケンス (OEIS スイート A000201) の連続する値によって指定される位置にあります。 $$ {\lfloor n\phi\rfloor} $$
- フィボナッチ ワードでは、「010」などの 3 つのサブワード (立方体) の繰り返しは許可されますが、4 つのサブワードの繰り返しは許可されません。フィボナッチ ワードが最大2 + φ = 3.618回の繰り返しを許容することを示します。これは、スターミアン語の中で最も弱い指数 (または「臨界指数」) です。
- 複雑性理論では、文字列内の繰り返しを見つけるアルゴリズムの「最悪のケース」としてフィボナッチ ワードがよく引用されます。