Массив Витхоффа

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

Массив Витхоффа был впервые определен Моррисоном (1980) с использованием пар Витхоффа — координат выигрышных позиций в игре Витхоффа . Его также можно определить с помощью чисел Фибоначчи и теоремы Цекендорфа или непосредственно из золотого сечения и рекуррентного соотношения, определяющего числа Фибоначчи.

Ценности

Массив Витхоффа имеет значения

${\begin{matrix}1&2&3&5&8&13&21&\cdots \\4&7&11&18&29&47&76&\cdots \\6&10&16&26&42&68&110&\cdots \\9&15&24&39&63&102&165&\cdots \\12&20&32&52&84&136&220&\cdots \\14&23&37&60&97&157&254&\cdots \\17&28&45&73&118&191&309&\cdots \\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\ddots \\\end{matrix}}$ (последовательность A035513 в OEIS ).

Эквивалентные определения

Вдохновленный аналогичной решеткой Столарского, ранее определенной Столарским (1977) , Моррисон (1980) определил решетку Витхоффа следующим образом. Позволять $\varphi ={\frac {1+{\sqrt {5}}}{2}}$ обозначаем золотое сечение ; тогда $i$выигрышная позиция в игре Витхоффа определяется парой натуральных чисел $(\lfloor i\varphi \rfloor ,\lfloor i\varphi ^{2}\rfloor )$, где числа в левой и правой частях пары определяют две дополнительные последовательности Битти , которые вместе включают каждое положительное целое число ровно один раз. Моррисон определяет первые два числа подряд $m$ массива будет парой Витгофа, заданной уравнением $i=\lfloor m\varphi \rfloor$, и где остальные числа в каждой строке определяются рекуррентным соотношением Фибоначчи. То есть, если $A_{m,n}$ обозначает запись в строке $m$ и столбец $n$ массива, то

$A_{m,1}=\left\lfloor \lfloor m\varphi \rfloor \varphi \right\rfloor$,

$A_{m,2}=\left\lfloor \lfloor m\varphi \rfloor \varphi ^{2}\right\rfloor$, и

$A_{m,n}=A_{m,n-2}+A_{m,n-1}$ для $n>2$.

Представление Цекендорфа любого положительного целого числа представляет собой сумму различных чисел Фибоначчи, никакие два из которых не являются последовательными в последовательности Фибоначчи. Как описывает Кимберлинг (1995) , числа в каждой строке массива имеют представление Цекендорфа, которые отличаются друг от друга операцией сдвига, а числа в каждом столбце имеют представления Цекендорфа, которые используют одно и то же наименьшее число Фибоначчи. В частности, запись $A_{m,n}$ массива является $m$наименьшее число, представление Цекендорфа которого начинается с $(n+1)$число Фибоначчи.

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

Каждая пара Витхоффа встречается в массиве Витхоффа ровно один раз как последовательная пара чисел в одной строке с нечетным индексом для первого числа и четным индексом для второго. Поскольку каждое положительное целое число встречается ровно в одной паре Витхоффа, каждое положительное целое число встречается в массиве ровно один раз ( Моррисон 1980 ).

Каждая последовательность натуральных чисел, удовлетворяющая рекуррентности Фибоначчи, встречается в массиве Витхоффа со сдвигом не более чем на конечное число позиций. В частности, сама последовательность Фибоначчи является первой строкой, а последовательность чисел Люка появляется в сдвинутой форме во второй строке ( Моррисон 1980 ).

Ссылки

• Кимберлинг, Кларк (1995), «Массив Зекендорфа равен массиву Витхоффа» (PDF) , Fibonacci Quarterly , 33 (1): 3–8 .
• Моррисон, Д.Р. (1980), «Массив Столарского пар Витхоффа», Сборник рукописей, связанных с последовательностью Фибоначчи (PDF) , Санта-Клара, Калифорния: Ассоциация Фибоначчи, стр. 134–136 .
• Столарский, КБ (1977), «Набор обобщенных последовательностей Фибоначчи, таких, что каждое натуральное число принадлежит ровно одному» (PDF) , Fibonacci Quarterly , 15 (3): 224 .

Внешние ссылки

• Вайсштейн, Эрик В. «Массив Витхоффа» . Математический мир .