Таблица Витхоффа

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

Значения

Массив Витхоффа имеет следующие значения

$\begin{array}{cccccccc}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 \\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& \ddots \\ \end{array}$ последовательность A035513 в OEIS.

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

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

$A_{m,1}=\lfloor \lfloor m\phi \rfloor \phi \rfloor$,

$A_{m,2}=\lfloor \lfloor m\phi \rfloor {\phi }^2\rfloor$,

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

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

Свойства

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

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

Ссылки

• Kimberling, Clark (1995), The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly Т. 33 (1): 3–8, <http://www.fq.math.ca/Scanned/33-1/kimberling.pdf> .
• Morrison, D. R. (1980), A Stolarsky array of Wythoff pairs, A Collection of Manuscripts Related to the Fibonacci Sequence, Santa Clara, Calif: The Fibonacci Association, с. 134–136, <http://www.math.ucsb.edu/~drm/papers/stolarsky.pdf>  Архивная копия от 4 марта 2016 на Wayback Machine.
• Stolarsky, K. B. (1977), A set of generalized Fibonacci sequences such that each natural number belongs to exactly one, Fibonacci Quarterly Т. 15 (3): 224, <http://www.fq.math.ca/Scanned/15-3/stolarsky.pdf> .

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

• Weisstein, Eric W. Wythoff Array (англ.) на сайте Wolfram MathWorld.