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

 В математике таблица Витхоффа —  бесконечная целочисленнаяматрица, полученная из последовательности Фибоначчи и названная в честьголландского математика . Была определена математиком Моррисоном в 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\} .

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


 Вдохновленный аналогичным массивом, ранее определенным Столярским(1977), Моррисон определил массив Витхоффа следующим образом. Пустьφ=1+52 обозначает золотое сечение; тогда i-явыигрышная позиция в игре Витхоффа задается парой целых положительныхчисел (iφ,iφ2), где числав каждой паре определяют две комплементарные , в которой каждоенатуральное число встречается ровно в одной из двух последовательностей.Моррисон определяет первые два числа m-й строка матрицы как паруВитхоффа, задаваемую уравнением m=iφ, остальныечисла в строке задаются рекуррентным соотношением Фибоначчи. То естьэлемент матрицы Am,n определяется как

Am,1=mφφ,
Am,2=mφφ2,
Am,n=Am,n2+Am,n1, n>2.
 Представление Цекендорфа натурального числа — представление его в видесуммы различных чисел Фибоначчи, никакие два из которых не являютсяпоследовательными членами последовательности Фибоначчи. Как описываетКимберлинг (1995 г.), числа в каждой строке матрицы имеют представленияЦекендорфа, отличающиеся друг от друга сдвигом, а числа в каждом столбцематрицы имеют представления Цекендорфа с одним и тем же наименьшимчислом Фибоначчи. В частности, элемент Am,n можно определить какm-е наименьшее число, чьё представление Цекендорфа начинается с n-гочисла Фибоначчи.

Свойства


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