Слово Фибоначчи - Fibonacci word

Характеризация последовательность резки с линией уклона ${\displaystyle 1/\varphi }$ или же ${\displaystyle \varphi -1}$, с ${\displaystyle \varphi }$ в Золотое сечение.

${\displaystyle S_{10}}$

${\displaystyle S_{17}}$

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

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

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

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

Определение

Позволять ${\displaystyle S_{0}}$ быть "0" и ${\displaystyle S_{1}}$ быть «01». Сейчас же ${\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 )

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

Потом^th цифра слова ${\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 }$ это функция пола (последовательность A003849 в OEIS ). Как следствие, бесконечное слово Фибоначчи может быть охарактеризовано отсекающей последовательностью линии наклона ${\displaystyle 1/\phi }$ или же ${\displaystyle \phi -1}$. См. Рисунок выше.

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

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

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

Потом^th цифра слова ${\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_п быть F_п + 2, (п + 2) -е число Фибоначчи. Также количество единиц в S_п является F_п и количество нулей в S_п является F_п + 1.

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

• Бесконечное слово Фибоначчи не является периодическим и в конечном итоге не периодическим.
• Последние две буквы слова Фибоначчи - это попеременно «01» и «10».
• Подавление последних двух букв слова Фибоначчи или добавление дополнения к последним двум буквам создает палиндром. Пример: 01${\displaystyle S_{4}}$ = 0101001010 - палиндром. В палиндромная плотность бесконечного слова Фибоначчи, таким образом, 1 / φ, где φ - Золотое сечение: это максимально возможное значение для апериодических слов.^[2]
• В бесконечном слове Фибоначчи отношение (количество букв) / (количество нулей) равно φ, как и отношение нулей к единицам.
• Бесконечное слово Фибоначчи - это сбалансированная последовательность: Возьми два факторы одинаковой длины в любом месте слова Фибоначчи. Разница между их Веса Хэмминга (количество вхождений «1») никогда не превышает 1.^[3]
• Подслова 11 и 000 никогда не происходит.
• В функция сложности бесконечного слова Фибоначчи п+1: он содержит п+1 различных подслова длины п. Пример: существует 4 различных подслова длины 3: «001», «010», «100» и «101». Кроме того, будучи непериодическим, он имеет "минимальную сложность", и, следовательно, Штурмское слово,^[4] с уклоном ${\displaystyle 1/\phi ^{2}}$. Бесконечное слово Фибоначчи - это стандартное слово генерируется директивная последовательность (1,1,1,....).
• Бесконечное слово Фибоначчи повторяется; то есть каждое подслово встречается бесконечно часто.
• Если ${\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 }$
• Распределение ${\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}}$ если шаблон начинается в точке, ближайшей к первой точке по часовой стрелке, при этом 0 соответствует большому расстоянию, а 1 - короткому расстоянию.
• Бесконечное слово Фибоначчи содержит повторения трех последовательных идентичных подслов, но ни одного из четырех. критический показатель для бесконечного слова Фибоначчи ${\displaystyle 2+\phi \approx 3.618}$.^[5] Это наименьший индекс (или критический показатель) среди всех слов Штурма.
• Бесконечное слово Фибоначчи часто называют худший случай для алгоритмов обнаружения повторов в строке.
• Бесконечное слово Фибоначчи - это морфическое слово, порожденная в {0,1} * эндоморфизмом 0 → 01, 1 → 0.^[6]
• В п-й элемент слова Фибоначчи, ${\displaystyle s_{n}}$, равно 1, если Представительство Zeckendorf (сумма определенного набора чисел Фибоначчи) п включает 1 и 0, если не включает 1.

Приложения

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

Смотрите также

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

Примечания

1. Рамирес, Хосе Л .; Рубиано, Густаво Н .; Де Кастро, Родриго (2014). "Обобщение фрактала слова Фибоначчи и снежинки Фибоначчи ", Теоретическая информатика Том 528, 3 апреля 2014 г., страницы 40-56.
2. Адамчевский, Борис; Bugeaud, Yann (2010), «8. Трансцендентность и диофантово приближение», в Берте, Валери; Риго, Майкл (ред.), Комбинаторика, автоматы и теория чисел, Энциклопедия математики и ее приложений, 135, Кембридж: Издательство Кембриджского университета, п. 443, г. ISBN  978-0-521-51597-9, Zbl  1271.11073
3. Лотар (2011), п. 47.
4. де Лука (1995).
5. Аллуш и Шаллит (2003), п. 37.
6. Лотар (2011), п. 11.
7. Дхарма-вардана и др. (1987).

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

• Аллуш, Жан-Поль; Шаллит, Джеффри (2003), Автоматические последовательности: теория, приложения, обобщения, Издательство Кембриджского университета, ISBN  978-0-521-82332-6.
• Дхарма-вардана, М. В. Ч .; MacDonald, A.H .; Локвуд, Д. Дж .; Baribeau, J.-M .; Houghton, D. C. (1987), "Рамановское рассеяние в сверхрешетках Фибоначчи", Письма с физическими проверками, 58: 1761–1765, Дои:10.1103 / Physrevlett.58.1761, PMID  10034529.
• Лотэр, М. (1997), Комбинаторика слов, Энциклопедия математики и ее приложений, 17 (2-е изд.), Издательство Кембриджского университета, ISBN  0-521-59924-5.
• Лотэр, М. (2011), Алгебраическая комбинаторика слов, Энциклопедия математики и ее приложений, 90, Издательство Кембриджского университета, ISBN  978-0-521-18071-9. Перепечатка 2002 года в твердом переплете.
• де Лука, Альдо (1995), "Свойство деления слова Фибоначчи", Письма об обработке информации, 54 (6): 307–312, Дои:10.1016 / 0020-0190 (95) 00067-М.
• Mignosi, F .; Пирилло, Г. (1992), «Повторения в бесконечном слове Фибоначчи», Теория информатики и приложение, 26 (3): 199–204.

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

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