Слово Фибоначчи

Описание посредством Шаблон:Не переведено 5 с прямой, имеющей наклон $1/\phi$ или $\phi -1$, где $\phi$ — золотое сечение.

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

Слово Фибоначчи является хрестоматийным примером Шаблон:Не переведено 5.

Название «слово Фибоначчи» используется также для обозначения членов формального языка L, содержащего строки из нулей и единиц без рядом стоящих единиц. Любая часть конкретного слова Фибоначчи принадлежит L, но в языке много и других строк. В языке L число строк каждой возможной длины является числом Фибоначчи.

Определение

Пусть $S_0$ равно «0», а $S_1$ равно «01». Теперь $S_n=S_{n-1}{S}_{n-2}$ (конкатенация предыдущего члена и члена до него).

Бесконечное слово Фибоначчи — это предел $S_{\mathrm{\infty }}$.

Перечисление членов последовательности из определения выше даёт:

$S_0$    0

$S_1$    01

$S_2$    010

$S_3$    01001

$S_4$    01001010

$S_5$    0100101001001

…

Первые несколько элементов бесконечного слова Фибоначчи:

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, … (Шаблон:OEIS)

Выражение в замкнутой форме для конкретных цифр

Цифра с номером n слова равна $2+\lfloor n\phi \rfloor -\lfloor \left(n+1\right)\phi \rfloor$, где $\phi$ — золотое сечение, а $\lfloor x\rfloor$ — функция «floor» («пол»).

Правила подстановки

Другой способ перехода от S_n к S_n + 1 — замена каждого символа 0 в S_n парой символов 0, 1 и замена каждого 1 на 0.

Альтернативно, можно представить генерацию всего бесконечного слова Фибоначчи с помощью следующего процесса. Начинаем с символа 0, на него устанавливаем курсор. На каждом шаге, если курсор указывает на 0, добавляем 1 и 0 в конец слова, а если курсор указывает на 1, добавляем 0 в конец слова. В любом случае шаг завершается передвижением на одну позицию вправо.

Похожее бесконечное слово иногда называется золотой струной или кроличьей последовательностью, образуется аналогичным бесконечным процессом, но правило замены другое — если курсор указывает на 0, добавляем 1, а если указывает на 1, добавляем 0, 1. Результирующая последовательность начинается с

0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, …

Однако эта последовательность отличается от слова Фибоначчи тривиально — нули заменяются на единицы и вся последовательность сдвигается на единицу.

Выражение в замкнутой форме для золотой струны:

Цифра с номером n слова равна $\lfloor n\phi \rfloor -\lfloor \left(n-1\right)\phi \rfloor -1$, где $\phi$ — золотое сечение, а $\lfloor x\rfloor$ — функция «floor».

Обсуждение

Слово связано со знаменитой последовательностью с тем же именем (последовательность Фибоначчи) в том смысле, что сложение целых чисел в индуктивном определении заменяется конкатенацией строк. Это приводит к тому, что длина S_n равна F_n + 2, (n + 2)-ому числу Фибоначчи. Также число единиц в S_n равно F_n, а число нулей в S_n равно F_n + 1.

Другие свойства

• Бесконечное слово Фибоначчи не является периодическим и не является финально периодическим.
• Две последних цифры слова Фибоначчи либо «01», либо «10».
• Удаление двух последних букв слова Фибоначчи или добавление в начало дополнения двух последних букв создаёт палиндром. Пример: 01$S_4$=0101001010 является палиндромом. Палиндромическая плотность бесконечного слова Фибоначчи равна 1/φ, где φ — золотое сечение. Это наибольшее возможное значение для непериодических словШаблон:Sfn.
• В бесконечном слове Фибоначчи отношение (число цифр)/(число нулей) равно φ, так же, как и отношение числа нулей к числу единиц.
• Бесконечное слово Фибоначчи является Шаблон:Не переведено 5. Возьмём две подстроки той же самой длины где-либо в слове Фибоначчи. Разница между их весами Хэмминга (число единиц) никогда не превышает 1Шаблон:Sfn.
• Подслова 11 и 000 никогда не встречаются.
• Шаблон:Не переведено 5 бесконечного слова Фибоначчи равна n+1 — оно содержит n+1 различных подслов длины n. Пример: Имеется 4 различных подслов длины 3 : «001», «010», «100» и «101». Будучи непериодической последовательностью, слово имеет «минимальную сложность», а потому является Шаблон:Не переведено 5Шаблон:Sfnp с наклоном $1/{\varphi }^2$. Бесконечное слово Фибоначчи является Шаблон:Не переведено 5, образованным Шаблон:Не переведено 5 (1,1,1,….).
• Бесконечное слово Фибоначчи рекуррентно. То есть любое подслово встречается бесконечно часто.
• Если $u$ является подсловом бесконечного слова Фибоначчи, то подсловом является его обратное, обозначаемое $u^R$.
• Если $u$ является подсловом бесконечного слова Фибоначчи, то наименьший период $u$ является числом Фибоначчи.
• Конкатенация двух последовательностей слов Фибоначчи «почти коммутативна». $S_{n+1}=S_n{S}_{n-1}$ и $S_{n-1}{S}_n$ отличаются только в последних двух буквах.
• Как следствие, бесконечное число Фибоначчи может быть описано последовательностью сечений прямой с наклоном $\varphi$ или $\varphi -1$. См. рисунок выше.
• Число 0,010010100…, десятичные цифры которого являются цифрами бесконечного слова Фибоначчи, трансцендентно.
• Буквы «1» можно найти в позициях, задаваемых последовательными значениями верхней последовательности Витхоффа (OEIS A001950): $\lfloor n{\varphi }^2\rfloor$
• Буквы «0» можно найти в позициях, задаваемых последовательными значениями нижней последовательности Витхоффа (OEIS A000201): $\lfloor n\varphi \rfloor$
• Распределение $n=F_k$ точек на единичной окружности, размещённых последовательно по часовой стрелке на золотой угол $\frac{2\pi }{{\varphi }^2}$, образует шаблон из двух длин $\frac{2\pi }{{\varphi }^{k-1}},\frac{2\pi }{{\varphi }^k}$ на единичной окружности. Хотя описанный выше процесс образования слова Фибоначчи не соответствует напрямую последовательному делению сегментов окружности, этот шаблон равен $S_{k-1}$, если начинать с точки, ближайшей по часовой стрелке, при этом 0 соответствует длинному расстоянию, а 1 соответствует короткому расстоянию.
• Бесконечное слово Фибоначчи может содержать повторение 3 последовательных идентичных подслов, но никогда не содержит 4 таких подслова. Шаблон:Не переведено 5 для бесконечного слова Фибоначчи равен $2+\varphi =3,618$ повторенийШаблон:Sfn. Это наименьший индекс (или критический индекс) среди всех слов Штурма.
• Бесконечное слово Фибоначчи часто упоминается как Шаблон:Не переведено 5 для алгоритмов выявления повторений в строке.
• Бесконечное слово Фибоначчи является Шаблон:Не переведено 5, образованным из {0,1}* путём эндоморфизма 0 → 01, 1 → 0Шаблон:Sfn.

Приложения

Построения слов Фибоначчи используются для моделирования физических систем с непериодическим порядком, таких как квазикристаллы, и изучения свойств рассеяния света кристаллов со слоями ФибоначчиШаблон:Sfn.

См. также

• Математика и изобразительное искусство
• Шаблон:Не переведено 5

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга. Reprint of the 2002 hardback.
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• A detailed and accessible description, on Ron Knott’s site
• Шаблон:Mathworld
• Шаблон:Youtube