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

S_{10}

S_{17}

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

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

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

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

Определение

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

Бесконечное слово Фибоначчи — это предел $S_{\infty }$ , то есть (уникальная) бесконечная последовательность, содержащая каждый $S_{n}$ , для конечного $n$ , в качестве префикса.

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

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

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

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

Правила замены

способ перехода от Sn _и к Sn _{— +1} каждый символ 0 в Sn _{заменить} парой последовательных символов 0, 1 в + _{Другой 1} заменить каждый символ 1 в Sn _Sn одним символом 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, ...

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

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

Затем ^й цифра слова $\lfloor n\varphi \rfloor -\lfloor (n-1)\varphi \rfloor -1.$

Обсуждение

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

Другие объекты недвижимости

Бесконечное слово Фибоначчи не является периодическим и не является предельно периодическим. ^[2]
Последние две буквы слова Фибоначчи — это попеременно «01» и «10».
Подавление последних двух букв слова Фибоначчи или добавление префикса к последним двум буквам создает палиндром . Пример: 01 S ₄ = 0101001010 — палиндром. Таким образом, палиндромная плотность бесконечного слова Фибоначчи равна 1/φ, где φ — золотое сечение : это максимально возможное значение для апериодических слов. ^[3]
В бесконечном слове Фибоначчи соотношение (количество букв)/(количество нулей) равно φ, как и отношение нулей к единицам. ^[4]
Бесконечное слово Фибоначчи представляет собой сбалансированную последовательность : возьмите два фактора одинаковой длины в любом месте слова Фибоначчи. Разница между их весами Хэмминга (количество вхождений «1») никогда не превышает 1. ^[5]
Подслова 11 и 000 никогда не встречаются. ^[6]
Функция сложности бесконечного слова Фибоначчи равна n + 1: оно содержит n + 1 различных подслов длины n . Пример: существует 4 различных подслова длиной 3: «001», «010», «100» и «101». Будучи также непериодическим, оно тогда имеет «минимальную сложность» и, следовательно, слово Штурма , ^[7] с уклоном $1/\varphi$ . Бесконечное слово Фибоначчи — это стандартное слово, порожденное последовательностью директив (1,1,1,....).
Бесконечное слово Фибоначчи повторяется; то есть каждое подслово встречается бесконечно часто.
Если $u$ является подсловом бесконечного слова Фибоначчи, то и его обращение, обозначаемое $u^{R}$ .
Если $u$ является подсловом бесконечного слова Фибоначчи, то наименьший период $u$ является числом Фибоначчи.
Объединение двух последовательных слов Фибоначчи «почти коммутативно». $S_{n+1}=S_{n}S_{n-1}$ и $S_{n-1}S_{n}$ отличаются только двумя последними буквами.
Число 0,010010100..., цифры которого построены из цифр бесконечного слова Фибоначчи, является трансцендентным .
Буквы «1» можно найти в позициях, заданных последовательными значениями последовательности Аппер-Витхоффа (последовательность A001950 в OEIS ): $\lfloor n\varphi ^{2}\rfloor$
Буквы «0» можно найти в позициях, заданных последовательными значениями последовательности Лоуэра Витхоффа (последовательность A000201 в OEIS ): $\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 - короткому расстоянию.
Бесконечное слово Фибоначчи содержит повторения трех последовательных одинаковых подслов, но ни одного из четырех. ^[2] Критический показатель бесконечного слова Фибоначчи равен $2+\varphi \approx 3.618$ . ^[8] Это наименьший индекс (или критический показатель) среди всех слов Штурма.
Бесконечное слово Фибоначчи часто называют наихудшим случаем для алгоритмов, обнаруживающих повторения в строке.
Бесконечное слово Фибоначчи — это морфное слово , порожденное в {0,1}* эндоморфизмом 0 → 01, 1 → 0. ^[9]
N - й элемент слова Фибоначчи, $s_{n}$ , равно 1, если представление Цекендорфа (сумма определенного набора чисел Фибоначчи) числа n включает 1, и 0, если оно не включает 1.
Цифры слова Фибоначчи можно получить, взяв последовательность фиббинарных чисел по модулю 2. ^[10]

Приложения

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

См. также

Примечания

^ Рамирес, Рубиано и Де Кастро (2014) .
^ Jump up to: ^а ^б Берстель (1986) , с. 13.
^ Адамчевски и Бюжо (2010) .
^ Слоан, Нью-Джерси (редактор), «Последовательность A003849» , Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS
^ Лотарь (2011) , с. 47.
^ О встречающихся подсловах см. Berstel (1986) , стр. 14 и 18 (с использованием букв a и b вместо цифр 0 и 1).
^ Люка (1995) .
^ Аллуш и Шалит (2003) , с. 37.
^ Лотарь (2011) , с. 11.
^ Кимберлинг (2004) .
^ Бомбьери и Тейлор (1986) .
^ Дхарма-вардана и др. (1987) .

Ссылки

Адамчевский, Борис; Бюжо, Янн (2010), «8. Трансцендентность и диофантова аппроксимация», в Берте, Валери ; Риго, Майкл (ред.), Комбинаторика, автоматы и теория чисел , Энциклопедия математики и ее приложений, том. 135, Кембридж: Издательство Кембриджского университета , стр. 135. 443, ISBN 978-0-521-51597-9 , Збл 1271.11073 .
Аллуш, Жан-Поль; Шалит, Джеффри (2003), Автоматические последовательности: теория, приложения, обобщения , издательство Кембриджского университета , ISBN 978-0-521-82332-6 .
Берстель, Жан (1986), «Слова Фибоначчи – обзор» (PDF) , Розенберг, Г.; Саломаа, А. (ред.), The Book of L , Springer, стр. 13–27, doi : 10.1007/978-3-642-95486-3_2 , ISBN 9783642954863
Бомбьери, Э .; Тейлор, Дж. Э. (1986), «Какие распределения вещества дифрагируют? Первоначальное исследование» (PDF) , Le Journal de Physique , 47 (C3): 19–28, doi : 10.1051/jphyscol:1986303 , MR 0866320 , S2CID 54194304 .
Дхарма-вардана, MWC; Макдональд, АХ; Локвуд, диджей; Барибо, Ж.-М.; Хоутон, округ Колумбия (1987), «Комбинационное рассеяние света в сверхрешетках Фибоначчи», Physical Review Letters , 58 (17): 1761–1765, Бибкод : 1987PhRvL..58.1761D , doi : 10.1103/physrevlett.58.1761 , PMID 10034529 .
Кимберлинг, Кларк (2004), «Упорядочение слов и наборов чисел: случай Фибоначчи», в книге Ховарда, Фредерика Т. (редактор), «Применение чисел Фибоначчи», том 9: Материалы Десятой международной исследовательской конференции по числам Фибоначчи и Их приложения , Дордрехт: Kluwer Academic Publishers, стр. 137–144, doi : 10.1007/978-0-306-48517-6_14 , MR 2076798 .
Лотер, М. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, том. 17 (2-е изд.), Издательство Кембриджского университета , ISBN 0-521-59924-5 .
Лотер, М. (2011), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, том. 90, Издательство Кембриджского университета , ISBN 978-0-521-18071-9 . Переиздание 2002 года в твердом переплете.
де Лука, Альдо (1995), «Свойство деления слова Фибоначчи», Information Processing Letters , 54 (6): 307–312, doi : 10.1016/0020-0190(95)00067-M .
Миньози, Ф.; Пирилло, Г. (1992), «Повторения в бесконечном слове Фибоначчи» , Theoretical Computer Science and Application , 26 (3): 199–204, doi : 10.1051/ita/1992260301991 .
Рамирес, Хосе Л.; Рубиано, Густаво Н.; Де Кастро, Родриго (2014), «Обобщение словесного фрактала Фибоначчи и снежинки Фибоначчи», Theoretical Computer Science , 528 : 40–56, arXiv : 1212.1368 , doi : 10.1016/j.tcs.2014.02.003 , MR 3175078 , S2CID 17193119 .

Внешние ссылки

[FOOTNOTERamírezRubianoDe_Castro2014-1] Рамирес, Рубиано и Де Кастро (2014) .

[FOOTNOTEBerstel198613-2] Jump up to: ^а ^б Берстель (1986) , с. 13.

[FOOTNOTEAdamczewskiBugeaud2010-3] Адамчевски и Бюжо (2010) .

[4] Слоан, Нью-Джерси (редактор), «Последовательность A003849» , Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS

[FOOTNOTELothaire201147-5] Лотарь (2011) , с. 47.

[6] О встречающихся подсловах см. Berstel (1986) , стр. 14 и 18 (с использованием букв a и b вместо цифр 0 и 1).

[FOOTNOTEde_Luca1995-7] Люка (1995) .

[FOOTNOTEAlloucheShallit200337-8] Аллуш и Шалит (2003) , с. 37.

[FOOTNOTELothaire201111-9] Лотарь (2011) , с. 11.

[FOOTNOTEKimberling2004-10] Кимберлинг (2004) .

[FOOTNOTEBombieriTaylor1986-11] Бомбьери и Тейлор (1986) .

[FOOTNOTEDharma-wardanaMacDonaldLockwoodBaribeau1987-12] Дхарма-вардана и др. (1987) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]