Слово Фибоначчи — это некоторая последовательность двоичных цифр (или символов из любого двухбуквенного алфавита). Слово Фибоначчи формируется путём повторения конкатенации тем же образом, что и числа Фибоначчи образуются путём повторяемых сложений.
Слово Фибоначчи является хрестоматийным примером слова Штурма.
Название «слово Фибоначчи» используется также для обозначения членов формального языка L, содержащего строки из нулей и единиц без рядом стоящих единиц. Любая часть конкретного слова Фибоначчи принадлежит L, но в языке много и других строк. В языке L число строк каждой возможной длины является числом Фибоначчи.
Определение Пусть равно «0», а равно «01». Теперь (конкатенация предыдущего члена и члена до него).
Бесконечное слово Фибоначчи — это предел .
Перечисление членов последовательности из определения выше даёт:
0
01
010
01001
01001010
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, … ()
Формула для n-го элемента Элемент с номером равен:где — золотое сечение, а — функция округления в меньшую сторону («пол»).
Правила подстановки Другой способ перехода от к — замена каждого 0 в парой: 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, … Чтобы получить из этой последовательности слово Фибоначчи, достаточно обрезать первый символ и инвертировать оставшиеся (1 заменить на 0, а 0 — на 1).
Аналитическое выражение для -го элемента золотой струны:
Обсуждение Слово связано со знаменитой последовательностью с тем же именем (последовательность Фибоначчи) в том смысле, что сложение целых чисел в индуктивном определении заменяется конкатенацией строк. Это приводит к тому, что длина равна — -ому числу Фибоначчи. Также число единиц в равно , а число нулей в равно .
Другие свойства Бесконечное слово Фибоначчи не является периодическиой последовательностью и не становится ей начиная с какого-либо из элементов (не является финально периодическойПоследовательность называется финально периодической с параметрами , если выполняется условие для , где и целые, , . Наименьшее такое число называется периодом последовательности. Последовательность называется -периодической, если ().). Две последних цифры слова Фибоначчи либо «01», либо «10». Удаление двух последних элементов слова Фибоначчи или добавление в начало дополнения двух последних элементов создаёт палиндром. Пример: 01=0101001010 является палиндромом. Палиндромическая плотность бесконечного слова Фибоначчи равна . Это наибольшее возможное значение для непериодических слов. В бесконечном слове Фибоначчи отношение общего числа цифр к числу нулей равно , так же, как и отношение числа нулей к числу единиц. Бесконечное слово Фибоначчи является . Это означает, что при произвольном выборе двух подстрок одной и той же длины в слове Фибоначчи, разница их весов Хэмминга (то есть числа единиц) никогда не превышает . Подслова «11» и «000» никогда не встречаются. бесконечного слова Фибоначчи равна — оно содержит различных подслов длины . Пример: Имеется 4 различных подслов длины : «001», «010», «100» и «101». Будучи непериодической последовательностью, слово имеет «минимальную сложность», а потому является словом Штурма с наклоном . Бесконечное слово Фибоначчи является стандартным словом, образованным директивной последовательностью (1,1,1,….). Бесконечное слово Фибоначчи рекуррентно. То есть любое подслово встречается бесконечно часто. Если является подсловом бесконечного слова Фибоначчи, то также является и его обратное, обозначаемое . Если является подсловом бесконечного слова Фибоначчи, то наименьший период является числом Фибоначчи. Конкатенация двух последовательностей слов Фибоначчи «почти коммутативна». и отличаются только в последних двух буквах. Как следствие, бесконечное число Фибоначчи может быть описано последовательностью сечений прямой с наклоном или . См. рисунок выше. Число 0,010010100…, десятичные цифры которого являются цифрами бесконечного слова Фибоначчи, трансцендентно. Элементы «1» можно найти в позициях, задаваемых последовательными значениями верхней последовательности Витхоффа (OEIS A001950): . Элементы «0» можно найти в позициях, задаваемых последовательными значениями нижней последовательности Витхоффа (OEIS A000201): . Распределение точек на единичной окружности, размещаемых последовательно по часовой стрелке с шагом величиной в золотой угол , образует на окружности последовательность сегментов двух длин: и . Если начать рассмотрение этих сегментов со второй точки по часовой стрелке, принимая короткие сегменты за 1, а длинные — за 0, то полученная последовательность цифр будет тождественна . Бесконечное слово Фибоначчи может содержать повторение 3 последовательных идентичных подслов, но никогда не содержит 4 таких подслова. для бесконечного слова Фибоначчи равен повторений. Это наименьший индекс (или критический индекс) среди всех слов Штурма. Бесконечное слово Фибоначчи часто упоминается как для алгоритмов выявления повторений в строке. Бесконечное слово Фибоначчи является , образованным из {0,1}* путём эндоморфизма 0 → 01, 1 → 0. Элемнт под номером слова Фибоначчи равен «1», если представление Цекендорфа числа содержит 1, и равен «0» — если не содержит. Элементы слова Фибоначчи могут быть получены как остаток от деления на чисел Фибоначчи.
Приложения Построения слов Фибоначчи используются для моделирования физических систем с непериодическим порядком, таких как квазикристаллы, и изучения свойств рассеяния света кристаллов со слоями Фибоначчи.
См. также Математика и изобразительное искусство
Примечания
Литература
. Reprint of the 2002 hardback.
.
Ссылки Детальное объяснение популярным языком на сайте Рона Кнотта (Ron Knott).
Категория:Числа Фибоначчи Категория:Бинарные последовательности