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

Значения

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

${\displaystyle {\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}}}$ последовательность в OEIS .

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

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

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

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

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

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

Свойства

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

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

Ссылки

• Kimberling, Clark (1995), (PDF) , , 33 (1): 3—8 .
• Morrison, D. R. (1980), "A Stolarsky array of Wythoff pairs", (PDF) , Santa Clara, Calif: The Fibonacci Association, pp. 134—136 от 4 марта 2016 на Wayback Machine .
• Stolarsky, K. B. (1977), (PDF) , , 15 (3): 224 .

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

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