フィビニリ数
Numbers whose binary representation does not contain two consecutive ones

数学において、フィビニ数（fibbinary number）とは、 2進数表現において連続する2つの数を含まない数のことである。つまり、異なる2の累乗の和であり、連続しない数である。[1] [2]

2進数とフィボナッチ数の関係

フィボナッチ数は、2進数とフィボナッチ数列の特定の性質を組み合わせたものであることから、マーク・ルブランによってその名前が付けられました。[1]

  • 2のべき乗より小さいフィボナッチ数の数はフィボナッチ数です。例えば、32より小さいフィボナッチ数は0、1、2、4、5、8、9、10、16、17、18、20、21の13個です。[1]
  • フィボナッチ数列を定義するために2進法で使用される、連続する2つの1がないという条件は、連続しないフィボナッチ数列の合計として任意の数を表すゼッケンドルフ表現で使用される条件と同じです。[1]
  • フィボナッチ数列の19番目の2進数（0を0番目として数える）は、そのゼッケンドルフ表現で表し、得られた2進数列を数値の2進表現として再解釈することで計算できます。[1]たとえば、19のゼッケンドルフ表現は101001（1は19 = 13 + 5 + 1の展開で使用されるフィボナッチ数列の位置を示します）です。2進数として解釈された2進数列101001は41 = 32 + 8 + 1を表し、19番目のフィボナッチ数は41です。 n {\displaystyle n} n {\displaystyle n}
  • フィボナッチ数列の番目の値が0か1の場合にのみ、番目のフィボナッチ数列（ここでも0を0番目として数える）は偶数か奇数である。 [3] n {\displaystyle n} n {\displaystyle n}

プロパティ

連続する2つの数が存在しないという性質は正規言語を定義するので、フィビ二進数の2進表現は有限オートマトンによって認識することができ、これはフィビ二進数が2オートマトン集合を形成することを意味する。[4]

フィビニリ数には、4の異なるべき乗の和であるモーザー・ド・ブリュイン数列が含まれる。フィビニリ数がゼッケンドルフ表現を2進数として再解釈することで形成されるのと同様に、モーザー・ド・ブリュイン数列は2進数表現を4進数として再解釈することで形成される。[5]

ある数がフィビ二進数であるためには、二項係数が奇数でなければならない。[1]同様に、第二種中心スターリング数が奇数であるためには、フィビ二進数が必要である。[6] n {\displaystyle n} ( 3 n n ) {\displaystyle {\tbinom {3n}{n}}} n {\displaystyle n} { 2 n n } {\displaystyle \textstyle \left\{{2n \atop n}\right\}}

あらゆるフィビニリ数は、またはのいずれかの形式をとる。ここでは別のフィビニリ数である。[3] [7] 同様に、指数がフィビニリ数である べき級数は、関数方程式[2] に従う。 f i {\displaystyle f_{i}} 2 f j {\displaystyle 2f_{j}} 4 f j + 1 {\displaystyle 4f_{j}+1} f j {\displaystyle f_{j}} B ( x ) = 1 + x + x 2 + x 4 + x 5 + x 8 + ⋯ , {\displaystyle B(x)=1+x+x^{2}+x^{4}+x^{5}+x^{8}+\cdots ,} B ( x ) = x B ( x 4 ) + B ( x 2 ) . {\displaystyle B(x)=xB(x^{4})+B(x^{2}).}

Madritsch & Wagner (2010)は、すべての部分がフィビニリである整数分割の数についての漸近公式を提供している。[7]

次元の超立方体グラフ が0から までの整数でインデックス付けされ、そのインデックスがハミング距離1のバイナリ表現を持つ2つの頂点が隣接する場合、フィボナッチ数でインデックス付けされた頂点のサブセットは、その誘導サブグラフとしてフィボナッチキューブを形成します。[8] Q d {\displaystyle Q_{d}} d {\displaystyle d} 2 d − 1 {\displaystyle 2^{d}-1}

すべての数にはフィビ二進数の倍数があります。例えば、15はフィビ二進数ではありませんが、11を掛けると165（10100101 2）となり、これはフィビ二進数です。[9]

参考文献

  1. ^ abcdef Sloane, N. J. A. (編)、「シーケンス A003714 (Fibbinary numbers)」、オンライン整数シーケンス百科事典、 OEIS Foundation
  2. ^ ab Arndt, Jörg (2011), Matters Computational: Ideas, Algorithms, Source Code (PDF) , Springer, pp. 62, 755– 756。
  3. ^ ab 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
  4. ^ Allouche, J.-P.; Shallit, J .; Skordev, G. (2005)、「自己生成集合、欠落ブロックを含む整数、および置換」、離散数学、292 ( 1–3 ): 1– 15、doi : 10.1016/j.disc.2004.12.004、MR  2131083
  5. ^ Sloane, N. J. A. (編), 「シーケンス A000695 (Moser–de Bruijn シーケンス)」,オンライン整数シーケンス百科事典, OEIS Foundation
  6. ^ Chan, O-Yeat; Manna, Dante (2010)、「第二種のスターリング数の合同性」(PDF)、実験数学の宝石、現代数学、第517巻、プロビデンス、ロードアイランド州：アメリカ数学会、pp.  97– 111、doi :10.1090/conm/517/10135、ISBN 978-0-8218-4869-2, MR 2731094, 2022年1月22日に オリジナル（PDF）からアーカイブ、 2021年10月2日取得
  7. ^ ab マドリッチュ、マンフレッド; Wagner、Stephan (2010)、「整数分割の中心極限定理」、Monatshefte für Mathematik、161 (1): 85–114、doi :10.1007/s00605-009-0126-y、MR  2670233、S2CID  15008932
  8. ^ Klavžar, Sandi (2013)、「フィボナッチキューブの構造：概観」、Journal of Combinatorial Optimization、25 (4): 505– 522、doi :10.1007/s10878-011-9433-z、MR  3044155、S2CID  5557314
  9. ^ Sloane, N. J. A. (編)、「数列 A300867 (k * n がフィビ二進数となるような最小の正の k)」、オンライン整数数列百科事典、 OEIS Foundation
Retrieved from "https://en.wikipedia.org/w/index.php?title=Fibbinary_number&oldid=1306133105"