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

В математике фиббинарными числами называют числа, двоичное представление которых не содержит двух последовательных чисел. То есть они представляют собой суммы различных и непоследовательных степеней двойки .

с двоичными числами и

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

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

Свойства

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

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

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

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

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

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

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