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

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