Русская Википедия:Таблица Витхоффа
В математике таблица Витхоффа — бесконечная целочисленная матрица, полученная из последовательности Фибоначчи и названная в честь голландского математика Шаблон:Не переведено 4. Была определена математиком Моррисоном в 1980 году на основе пар Витхоффа, координат выигрышных позиций в игре Витхоффа; может также быть определена с помощью чисел Фибоначчи и теоремы Цекендорфа или непосредственно через золотое сечение и рекуррентное соотношение, определяющее числа Фибоначчи. Каждое положительное целое число встречается в таблице ровно один раз, и путём сдвига строк таблицы можно получить любую целочисленную последовательность, определяемую рекуррентным соотношением Фибоначчи.
Значения
Массив Витхоффа имеет следующие значения
- <math>\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}</math> Шаблон:OEIS.
Эквивалентные определения
Вдохновленный аналогичным массивом, ранее определенным Столярским (1977), Моррисон определил массив Витхоффа следующим образом. Пусть <math>\varphi=\frac{1+\sqrt{5}}{2}</math> обозначает золотое сечение; тогда <math>i</math>-я выигрышная позиция в игре Витхоффа задается парой целых положительных чисел <math>(\lfloor i\varphi\rfloor, \lfloor i\varphi^2\rfloor)</math>, где числа в каждой паре определяют две комплементарные последовательности Битти, в которой каждое натуральное число встречается ровно в одной из двух последовательностей. Моррисон определяет первые два числа <math>m</math>-й строка матрицы как пару Витхоффа, задаваемую уравнением <math>m=\lfloor i\varphi\rfloor</math>, остальные числа в строке задаются рекуррентным соотношением Фибоначчи. То есть элемент матрицы <math>A_{m,n}</math> определяется как
- <math>A_{m,1} = \left\lfloor \lfloor m\varphi \rfloor \varphi \right\rfloor</math>,
- <math>A_{m,2} = \left\lfloor \lfloor m\varphi \rfloor \varphi^2 \right\rfloor</math>,
- <math>A_{m,n} = A_{m,n-2}+A_{m,n-1}</math>, <math>n > 2</math>.
Представление Цекендорфа натурального числа — представление его в виде суммы различных чисел Фибоначчи, никакие два из которых не являются последовательными членами последовательности Фибоначчи. Как описывает Кимберлинг (1995 г.), числа в каждой строке матрицы имеют представления Цекендорфа, отличающиеся друг от друга сдвигом, а числа в каждом столбце матрицы имеют представления Цекендорфа с одним и тем же наименьшим числом Фибоначчи. В частности, элемент <math>A_{m,n}</math> можно определить как <math>m</math>-е наименьшее число, чьё представление Цекендорфа начинается с <math>n</math>-го числа Фибоначчи.
Свойства
Каждая пара Витхоффа встречается в таблице Витхоффа ровно один раз, в виде последовательной пары чисел в одной строке, с нечетным индексом для первого элемента пары и четным для второго. Поскольку каждое натуральное число встречается ровно в одной паре Витхоффа, каждое натуральное число встречается ровно один раз и в таблице Витхоффа (Моррисон, 1980).
Таблица Витхоффа содержит любую последовательность натуральных чисел, удовлетворяющих рекуррентному соотношению Фибоначчи, с точностью до сдвига не более, чем на конечное число позиций. В частности, сама последовательность Фибоначчи представлена первой строкой таблицы, а последовательность Люка, начиная с третьего её члена, представлена второй строкой таблицы (Моррисон, 1980).
Ссылки
Внешние ссылки
