Фиббинарное число

Числа, двоичное представление которых не содержит двух последовательных единиц

В математике фиббинарные числа — это числа, двоичное представление которых не содержит двух последовательных единиц. То есть, они являются суммами различных и непоследовательных степеней двойки . ^{[1] [2]}

Связь с двоичными числами и числами Фибоначчи

Фиббиноридные числа получили свое название от Марка Лебрена, поскольку они сочетают в себе определенные свойства двоичных чисел и чисел Фибоначчи : ^[1]

• Число фиббинарных чисел, меньших любой заданной степени двойки, является числом Фибоначчи. Например, существует 13 фиббинарных чисел, меньших 32, это числа 0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20 и 21. ^[1]
• Условие отсутствия двух последовательных единиц, используемое в двоичной системе для определения фиббиноидов, является тем же условием, которое используется в представлении Цекендорфа любого числа как суммы непоследовательных чисел Фибоначчи. ^[1]
• Фиббиноридное число (считая 0 нулевым числом) можно вычислить, выразив его в представлении Цекендорфа и переинтерпретировав полученную двоичную последовательность как двоичное представление числа. ^[1] Например, представление Цекендорфа числа 19 — это 101001 (где единицы обозначают позиции чисел Фибоначчи, используемых в расширении 19 = 13 + 5 + 1 ), двоичная последовательность 101001, интерпретируемая как двоичное число, представляет собой 41 = 32 + 8 + 1 , а 19-е фиббиноридное число — это 41. ${\displaystyle n}$ ${\displaystyle n}$
• Фиббиноридное число (снова считая 0 нулевым) является четным или нечетным тогда и только тогда, когда значение th в слове Фибоначчи равно 0 или 1 соответственно. ^[3] ${\displaystyle n}$ ${\displaystyle n}$

Характеристики

Поскольку свойство отсутствия двух последовательных единиц определяет регулярный язык , двоичные представления фиббинарных чисел могут быть распознаны конечным автоматом , что означает, что фиббинарные числа образуют 2-автоматный набор . ^[4]

Фиббинарное число включает последовательность Мозера–де Брейна , суммы различных степеней числа четыре. Так же, как фиббинарное число может быть образовано путем переинтерпретации представлений Цекендорфа как двоичных, последовательность Мозера–де Брейна может быть образована путем переинтерпретации двоичных представлений как четверичных. ^[5]

Число является фиббинарным тогда и только тогда, когда биномиальный коэффициент нечетен. ^[1] Соответственно, является фиббинарным тогда и только тогда, когда центральное число Стирлинга второго рода нечетно. ^[6] ${\displaystyle n}$ ${\displaystyle {\tbinom {3n}{n}}}$ ${\displaystyle n}$ ${\displaystyle \textstyle \left\{{2n \atop n}\right\}}$

Каждое фиббибинарное число принимает одну из двух форм или , где — другое фиббибинарное число. ^{[3] [7]} Соответственно, степенной ряд , показатели степеней которого являются фиббибинарными числами, подчиняется функциональному уравнению ^[2] ${\displaystyle f_{i}}$ ${\displaystyle 2f_{j}}$ ${\displaystyle 4f_{j}+1}$ ${\displaystyle f_{j}}$ $${\displaystyle B(x)=1+x+x^{2}+x^{4}+x^{5}+x^{8}+\cdots ,}$$ $${\displaystyle B(x)=xB(x^{4})+B(x^{2}).}$$

Мадритч и Вагнер (2010) предлагают асимптотические формулы для числа целочисленных разбиений, в которых все части являются фибинарными. ^[7]

Если граф гиперкуба размерности индексирован целыми числами от 0 до , так что две вершины являются смежными, когда их индексы имеют двоичные представления с расстоянием Хэмминга один, то подмножество вершин, индексированных фиббинарными числами, образует куб Фибоначчи в качестве его индуцированного подграфа . ^[8] ${\displaystyle Q_{d}}$ ${\displaystyle d}$ ${\displaystyle 2^{d}-1}$

Каждое число имеет фиббибинарное кратное. Например, 15 не является фиббибинарным, но умножение его на 11 дает 165 (10100101 ₂ ), что является таковым. ^[9]

Ссылки

1. Sloane, N. J. A. (ред.), "Последовательность A003714 (Фиббинарные числа)", Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
2. Arndt, Jörg (2011), Matters Computational: Ideas, Algorithms, Source Code (PDF) , Springer, стр. 62, 755–756.
3. Kimberling, Clark (2004), «Упорядочение слов и наборов чисел: случай Фибоначчи», в Howard, Frederic T. (ред.), Applications of Fibonacci Numbers, Volume 9: Proceedings of The Tenth International Research Conference on Fibonacci Numbers and Their Applications , Dordrecht: Kluwer Academic Publishers, стр. 137–144, doi :10.1007/978-0-306-48517-6_14, ISBN 978-90-481-6545-2, МР  2076798
4. Allouche, J.-P.; Shallit, J .; Skordev, G. (2005), «Самогенерирующиеся множества, целые числа с отсутствующими блоками и подстановки», Discrete Mathematics , 292 (1–3): 1–15, doi : 10.1016/j.disc.2004.12.004 , MR  2131083
5. Слоан, Н. Дж. А. (ред.), «Последовательность A000695 (последовательность Мозера–де Брейна)», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
6. Чан, О-Йет; Манна, Данте (2010), «Сравнения для чисел Стирлинга второго рода» (PDF) , Gems in Experimental Mathematics , Contemporary Mathematics, т. 517, Провиденс, Род-Айленд: Американское математическое общество, стр. 97–111, doi :10.1090/conm/517/10135, ISBN 978-0-8218-4869-2, г-н  2731094
7. Мадрич, Манфред; Вагнер, Стефан (2010), «Центральная предельная теорема для целочисленных разбиений», Monatshefte für Mathematik , 161 (1): 85–114, doi : 10.1007/s00605-009-0126-y, MR  2670233, S2CID  15008932
8. Клавжар, Санди (2013), «Структура кубов Фибоначчи: обзор», Журнал комбинаторной оптимизации , 25 (4): 505–522, doi :10.1007/s10878-011-9433-z, MR  3044155, S2CID  5557314
9. Слоан, Н. Дж. А. (ред.), «Последовательность A300867 (наименьшее положительное k, такое что k * n является фиббинарным числом)», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS