Interested Article - Слово Фибоначчи

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

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

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

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

Определение

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

Бесконечное слово Фибоначчи — это предел $S_{\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+\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor$ , где $\varphi$ — золотое сечение , а $\left\lfloor x\right\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 слова равна $\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1$ , где $\varphi$ — золотое сечение , а $\left\lfloor x\right\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/φ, где φ — золотое сечение . Это наибольшее возможное значение для непериодических слов .
В бесконечном слове Фибоначчи отношение (число цифр)/(число нулей) равно φ, так же, как и отношение числа нулей к числу единиц.
Бесконечное слово Фибоначчи является . Возьмём две подстроки той же самой длины где-либо в слове Фибоначчи. Разница между их (число единиц) никогда не превышает 1 .
Подслова 11 и 000 никогда не встречаются.
бесконечного слова Фибоначчи равна n +1 — оно содержит n +1 различных подслов длины n . Пример: Имеется 4 различных подслов длины 3 : «001», «010», «100» и «101». Будучи непериодической последовательностью, слово имеет «минимальную сложность», а потому является с наклоном $1/\phi ^{2}$ . Бесконечное слово Фибоначчи является , образованным (1,1,1,….).
Бесконечное слово Фибоначчи рекуррентно. То есть любое подслово встречается бесконечно часто.
Если $u$ является подсловом бесконечного слова Фибоначчи, то подсловом является его обратное, обозначаемое $u^{R}$ .
Если $u$ является подсловом бесконечного слова Фибоначчи, то наименьший период $u$ является числом Фибоначчи.
Конкатенация двух последовательностей слов Фибоначчи «почти коммутативна». $S_{n+1}=S_{n}S_{n-1}$ и $S_{n-1}S_{n}$ отличаются только в последних двух буквах.
Как следствие, бесконечное число Фибоначчи может быть описано последовательностью сечений прямой с наклоном $\phi$ или $\phi -1$ . См. рисунок выше.
Число 0,010010100…, десятичные цифры которого являются цифрами бесконечного слова Фибоначчи, трансцендентно .
Буквы «1» можно найти в позициях, задаваемых последовательными значениями верхней последовательности Витхоффа ( OEIS A001950): $\lfloor n\phi ^{2}\rfloor$
Буквы «0» можно найти в позициях, задаваемых последовательными значениями нижней последовательности Витхоффа (OEIS A000201): $\lfloor n\phi \rfloor$
Распределение $n=F_{k}$ точек на единичной окружности , размещённых последовательно по часовой стрелке на золотой угол ${\frac {2\pi }{\phi ^{2}}}$ , образует шаблон из двух длин ${\frac {2\pi }{\phi ^{k-1}}},{\frac {2\pi }{\phi ^{k}}}$ на единичной окружности. Хотя описанный выше процесс образования слова Фибоначчи не соответствует напрямую последовательному делению сегментов окружности, этот шаблон равен $S_{k-1}$ , если начинать с точки, ближайшей по часовой стрелке, при этом 0 соответствует длинному расстоянию, а 1 соответствует короткому расстоянию.
Бесконечное слово Фибоначчи может содержать повторение 3 последовательных идентичных подслов, но никогда не содержит 4 таких подслова. для бесконечного слова Фибоначчи равен $2+\phi =3,618$ повторений . Это наименьший индекс (или критический индекс) среди всех слов Штурма.
Бесконечное слово Фибоначчи часто упоминается как для алгоритмов выявления повторений в строке.
Бесконечное слово Фибоначчи является , образованным из {0,1}* путём эндоморфизма 0 → 01, 1 → 0 .

Приложения

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

См. также

Математика и изобразительное искусство

Примечания

Последовательность $v=(v_{0},v_{1},\ldots )$ называется финально периодической с параметрами $(T,\tau )$ , если выполняется условие $v_{k+T}=v_{k}$ для $k\geqslant \tau$ , где $T$ и $\tau$ целые, $T>0$ , $\tau >0$ . Наименьшее такое число $T$ называется периодом последовательности. Последовательность называется $T$ -периодической, если $\tau =0$ ( , с. 27).
, с. 443.
, с. 47.
.
, с. 37.
, с. 11.
.

Литература

Jean-Paul Allouche, Jeffrey Shallit. Automatic Sequences: Theory, Applications, Generalizations. — Cambridge University Press , 2003. — ISBN 978-0-521-82332-6 .
Dharma-wardana M. W. C., MacDonald A. H., Lockwood D. J., Baribeau J.-M., Houghton D. C. Raman scattering in Fibonacci superlattices // Physical Review Letters . — 1987. — Т. 58 . — С. 1761–1765 . — doi : .
Lothaire M. Combinatorics on Words. — 2nd. — Cambridge University Press , 1997. — Т. 17. — (Encyclopedia of Mathematics and Its Applications). — ISBN 0-521-59924-5 .
Lothaire M. Algebraic Combinatorics on Words. — Cambridge University Press , 2011. — Т. 90. — (Encyclopedia of Mathematics and Its Applications). . Reprint of the 2002 hardback.
Aldo de Luca. A division property of the Fibonacci word // . — 1995. — Т. 54 , вып. 6 . — С. 307–312 . — doi : .
Mignosi F., Pirillo G. // Informatique théorique et application. — 1992. — Т. 26 , вып. 3 . — С. 199–204 .
Boris Adamczewski, Yann Bugeaud. Chapter 8. Transcendence and diophantine approximation // Combinatorics, automata, and number theory / Valérie Berthé, Michael Rigo. — Cambridge: Cambridge University Press , 2010. — Т. 135. — С. 443. — (Encyclopedia of Mathematics and its Applications). — ISBN 978-0-521-51597-9 .
Липницкий В. А., Чесалин Н. В. . — Минск: БГУ, 2008.