Массив Wythoff - Wythoff array

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

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

Значения

Массив Wythoff имеет значения

${ Displaystyle { начинают {матрица} 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}}}$ (последовательность A035513 в OEIS ).

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

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

${ Displaystyle A_ {м, 1} = left lfloor lfloor m varphi rfloor varphi right rfloor}$,

${ Displaystyle A_ {м, 2} = left lfloor lfloor m varphi rfloor varphi ^ {2} right rfloor}$, и

${ Displaystyle А_ {м, п} = А_ {м, п-2} + А_ {м, п-1}}$ за ${ displaystyle n> 2}$.

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

Характеристики

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

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

Рекомендации

• Кимберлинг, Кларк (1995), «Массив Цекендорфа равен массиву Вайтхоффа» (PDF), Ежеквартальный отчет Фибоначчи, 33 (1): 3–8.
• Моррисон, Д. Р. (1980), "Массив Столярского пар Уайтхофф", Коллекция рукописей, относящихся к последовательности Фибоначчи (PDF), Санта-Клара, Калифорния: Ассоциация Фибоначчи, стр. 134–136..
• Столярский, К. Б. (1977), «Набор обобщенных последовательностей Фибоначчи таких, что каждое натуральное число принадлежит ровно одному» (PDF), Ежеквартальный отчет Фибоначчи, 15 (3): 224.

внешняя ссылка

• Вайсштейн, Эрик В. "Массив Wythoff". MathWorld.