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

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

Значения

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

последовательность A035513 в OEIS.

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

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

,
,
, .

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

Свойства

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

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

Ссылки

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.