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

Характеристика с помощью последовательности резки с линией наклона или , с в золотой пропорции .${\ displaystyle 1 / \ varphi}$${\ displaystyle \ varphi -1}$${\ displaystyle \ varphi}$

${\ displaystyle S_ {17}}$

Кривые Фибоначчи, построенные из 10-го и 17-го слов Фибоначчи ^[1]

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

Это парадигматический пример слова Штурма и, в частности, морфического слова .

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

Определение [ править ]

Пусть будет «0» и «01». Теперь (объединение предыдущей и предыдущей последовательностей).${\ displaystyle S_ {0}}$${\ displaystyle S_ {1}}$${\ Displaystyle S_ {n} = S_ {n-1} S_ {n-2}}$

Бесконечное слово Фибоначчи - это предел , то есть (уникальная) бесконечная последовательность, которая содержит каждое , конечно , в качестве префикса.${\ displaystyle S _ {\ infty}}$${\ displaystyle S_ {n}}$${\ displaystyle n}$

Перечисление элементов из приведенного выше определения дает:

${\ displaystyle S_ {0}}$    0

${\ displaystyle S_ {1}}$    01

${\ displaystyle S_ {2}}$    010

${\ displaystyle S_ {3}}$    01001

${\ displaystyle S_ {4}}$    01001010

${\ displaystyle 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, .. . (последовательность A003849 в OEIS )

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

П - ^я цифры слова , где это золотое сечение и является функцией от пола (последовательность A003849 в OEIS ). Как следствие, бесконечное слово Фибоначчи может быть охарактеризовано отрезанной последовательностью линии наклона или . См. Рисунок выше.${\ displaystyle 2+ \ left \ lfloor {{n} \, \ varphi} \ right \ rfloor - \ left \ lfloor {\ left ({n + 1} \ right) \, \ varphi} \ right \ rfloor}$${\ displaystyle \ varphi}$${\displaystyle \left\lfloor x\right\rfloor }$${\displaystyle 1/\phi }$${\displaystyle \phi -1}$

Правила замены [ править ]

Другой способ перехода от S _n к S _{n  + 1} - заменить каждый символ 0 в S _n парой последовательных символов 0, 1 в S _{n  + 1} и заменить каждый символ 1 в S _n одним символом 0 в S _{n  + 1} .

В качестве альтернативы, можно представить себе прямое создание всего бесконечного слова Фибоначчи с помощью следующего процесса: начните с курсора, указывающего на единственную цифру 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, ...

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

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

П - ^й разряд слова , где это золотое сечение и является функцией от пола .${\displaystyle \left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1}$${\displaystyle \varphi }$${\displaystyle \left\lfloor x\right\rfloor }$

Обсуждение [ править ]

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

Другие свойства [ править ]

• Бесконечное слово Фибоначчи не является периодическим и в конечном итоге не периодическим.
• Последние две буквы слова Фибоначчи - это попеременно «01» и «10».
• Подавление последних двух букв слова Фибоначчи или добавление дополнения к последним двум буквам создает палиндром . Пример: 01 = 0101001010 - палиндром. Таким образом, палиндромная плотность бесконечного слова Фибоначчи равна 1 / φ, где φ - золотое сечение : это наибольшее возможное значение для апериодических слов. ^[2]${\displaystyle S_{4}}$
• В бесконечном слове Фибоначчи отношение (количество букв) / (количество нулей) равно φ, как и отношение нулей к единицам.
• Бесконечное слово Фибоначчи представляет собой сбалансированную последовательность : возьмите два множителя одинаковой длины в любом месте слова Фибоначчи. Разница между их весами Хэмминга (количество вхождений «1») никогда не превышает 1. ^[3]
• Подслова 11 и 000 никогда не встречаются.
• Функция сложности бесконечного слова Фибоначчи равна n +1: оно содержит n +1 различных подслов длины n . Пример: есть 4 различных подслова длины 3: «001», «010», «100» и «101». Будучи также непериодическим, то тогда «минимальной сложностью», и , следовательно, штурмово слово , ^[4] с наклоном . Бесконечное слово Фибоначчи - это стандартное слово, генерируемое последовательностью директив (1,1,1, ....).${\displaystyle 1/\phi ^{2}}$
• Бесконечное слово Фибоначчи повторяется; то есть каждое подслово встречается бесконечно часто.
• Если - подслово бесконечного слова Фибоначчи, то обозначено и его разворот .${\displaystyle u}$${\displaystyle u^{R}}$
• Если - подслово бесконечного слова Фибоначчи, то наименьший период - это число Фибоначчи.${\displaystyle u}$${\displaystyle u}$
• Соединение двух последовательных слов Фибоначчи «почти коммутативно». и отличаются только двумя последними буквами.${\displaystyle S_{n+1}=S_{n}S_{n-1}}$${\displaystyle S_{n-1}S_{n}}$
• Число 0,010010100 ..., десятичные дроби которого состоят из цифр бесконечного слова Фибоначчи, трансцендентно .
• Буквы «1» можно найти в позициях, заданных последовательными значениями последовательности Верхнего Витоффа (последовательность A001950 в OEIS ):${\displaystyle \lfloor n\phi ^{2}\rfloor }$
• Буквы «0» можно найти в позициях, заданных последовательными значениями последовательности Lower Wythoff (последовательность A000201 в OEIS ):${\displaystyle \lfloor n\phi \rfloor }$
• Распределение точек на единичной окружности, расположенных последовательно по часовой стрелке под золотым углом , дает образец двух длин на единичной окружности. Хотя описанный выше процесс генерации слова Фибоначчи не соответствует непосредственно последовательному делению сегментов круга, этот образец состоит в том, если образец начинается в точке, ближайшей к первой точке по часовой стрелке, при этом 0 соответствует большому расстоянию, а 1 - короткое расстояние.${\displaystyle n=F_{k}}$${\displaystyle {\frac {2\pi }{\phi ^{2}}}}$${\displaystyle {\frac {2\pi }{\phi ^{k-1}}},{\frac {2\pi }{\phi ^{k}}}}$${\displaystyle S_{k-1}}$
• Бесконечное слово Фибоначчи содержит повторения 3 последовательных идентичных подслов, но ни одного из 4. Критический показатель для бесконечного слова Фибоначчи равен . ^[5] Это наименьший индекс (или критический показатель) среди всех слов Штурма.${\displaystyle 2+\phi \approx 3.618}$
• Бесконечное слово Фибоначчи часто называют наихудшим случаем для алгоритмов, обнаруживающих повторения в строке.
• Бесконечное слово Фибоначчи - это морфическое слово , порожденное в {0,1} * эндоморфизмом 0 → 01, 1 → 0. ^[6]
• П - й элемент слова Фибоначчи, является 1 , если представление Цекендорф (сумма определенного набора чисел Фибоначчи) из п включает в себя 1, и 0 , если она не включает в себя 1.${\displaystyle s_{n}}$

Приложения [ править ]

Конструкции на основе Фибоначчи в настоящее время используются для моделирования физических систем с апериодическим порядком, таких как квазикристаллы , и в этом контексте слово Фибоначчи также называется квазикристаллом Фибоначчи . ^[7] Для выращивания слоистых кристаллов Фибоначчи и изучения их светорассеивающих свойств использовались методы выращивания кристаллов. ^[8]

См. Также [ править ]

• Математика и искусство
• Слово трибоначчи

Заметки [ править ]

Ссылки [ править ]

• Адамчевский, Борис; Бюжо, Ян (2010), «8. Трансцендентность и диофантово приближение», в Берте, Валери ; Риго, Майкл (ред.), Комбинаторика, автоматы и теория чисел , Энциклопедия математики и ее приложений, 135 , Кембридж: Cambridge University Press , стр. 443, ISBN 978-0-521-51597-9, Zbl  1271,11073.
• Аллуш, Жан-Поль; Шаллит, Джеффри (2003), Автоматические последовательности: теория, приложения, обобщения , Cambridge University Press , ISBN 978-0-521-82332-6.
• Bombieri, E .; Тейлор, JE (1986), "Какие распределения вещества преломлять Первичное исследование?", Ле Журналь де Physique , 47 (C3): 19-28, DOI : 10.1051 / jphyscol: 1986303 , MR  0866320.
• Дхарма-вардана, MWC; MacDonald, AH; Локвуд, диджей; Baribeau, J.-M .; Houghton, DC (1987), "комбинационное рассеяние света в сверхрешетках Фибоначчи", Physical Review Letters , 58 : 1761-1765, DOI : 10,1103 / physrevlett.58.1761 , PMID  10034529.
• Лотэр, М. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, 17 (2-е изд.), Cambridge University Press , ISBN 0-521-59924-5 CS1 maint: discouraged parameter (link).
• Лотэр, М. (2011), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, 90 , Cambridge University Press , ISBN 978-0-521-18071-9. Перепечатка 2002 года в твердом переплете.
• де Лука, Aldo (1995), "Свойство деление слова Фибоначчи", Information Processing Letters , 54 (6): 307-312, DOI : 10,1016 / 0020-0190 (95) 00067-M.
• Миньози, Ф .; Пирилло, Г. (1992), "Повторения в бесконечном слове Фибоначчи" , Informatique théorique et application , 26 (3): 199–204.
• Рамирес, Хосе Л .; Рубиано, Густаво Н .; Де Кастро, Родриго (2014), "Обобщение слова фрактал Фибоначчи и Снежинка Фибоначчи", Теоретическая информатика , 528 : 40-56, DOI : 10.1016 / j.tcs.2014.02.003 , MR  3175078.

Внешние ссылки [ править ]

• Подробное и доступное описание на сайте Рона Нотта.
• Вайсштейн, Эрик В. , «Последовательность кроликов» , MathWorld
• Слово Фибоначчи (первые 200 000 бит) на YouTube