Слово Фибоначчи (Vlkfk SnQkugccn)
Слово Фибоначчи — это некоторая последовательность двоичных цифр (или символов из любого двухбуквенного алфавита). Слово Фибоначчи формируется путём повторения конкатенации тем же образом, что и числа Фибоначчи образуются путём повторяемых сложений.
Слово Фибоначчи является хрестоматийным примером слова Штурма[англ.].
Название «слово Фибоначчи» используется также для обозначения членов формального языка 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, … (последовательность A003849 в OEIS)
Выражение в замкнутой форме для конкретных цифр
[править | править код]Цифра с номером n слова равна , где — золотое сечение, а — функция «floor» («пол»).
Правила подстановки
[править | править код]Другой способ перехода от Sn к Sn + 1 — замена каждого символа 0 в Sn парой символов 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 слова равна , где — золотое сечение, а — функция «floor».
Обсуждение
[править | править код]Слово связано со знаменитой последовательностью с тем же именем (последовательность Фибоначчи) в том смысле, что сложение целых чисел в индуктивном определении заменяется конкатенацией строк. Это приводит к тому, что длина Sn равна Fn + 2, (n + 2)-ому числу Фибоначчи. Также число единиц в Sn равно Fn, а число нулей в Sn равно Fn + 1.
Другие свойства
[править | править код]- Бесконечное слово Фибоначчи не является периодическим и не является финально периодическим[1].
- Две последних цифры слова Фибоначчи либо «01», либо «10».
- Удаление двух последних букв слова Фибоначчи или добавление в начало дополнения двух последних букв создаёт палиндром. Пример: 01=0101001010 является палиндромом. Палиндромическая плотность бесконечного слова Фибоначчи равна 1/φ, где φ — золотое сечение. Это наибольшее возможное значение для непериодических слов[2].
- В бесконечном слове Фибоначчи отношение (число цифр)/(число нулей) равно φ, так же, как и отношение числа нулей к числу единиц.
- Бесконечное слово Фибоначчи является сбалансированной последовательностью[англ.]. Возьмём две подстроки той же самой длины где-либо в слове Фибоначчи. Разница между их весами Хэмминга (число единиц) никогда не превышает 1[3].
- Подслова 11 и 000 никогда не встречаются.
- Функция сложности[англ.] бесконечного слова Фибоначчи равна n+1 — оно содержит n+1 различных подслов длины n. Пример: Имеется 4 различных подслов длины 3 : «001», «010», «100» и «101». Будучи непериодической последовательностью, слово имеет «минимальную сложность», а потому является словом Штурма[англ.][4] с наклоном . Бесконечное слово Фибоначчи является стандартным словом[англ.], образованным директивной последовательностью[англ.] (1,1,1,….).
- Бесконечное слово Фибоначчи рекуррентно. То есть любое подслово встречается бесконечно часто.
- Если является подсловом бесконечного слова Фибоначчи, то подсловом является его обратное, обозначаемое .
- Если является подсловом бесконечного слова Фибоначчи, то наименьший период является числом Фибоначчи.
- Конкатенация двух последовательностей слов Фибоначчи «почти коммутативна». и отличаются только в последних двух буквах.
- Как следствие, бесконечное число Фибоначчи может быть описано последовательностью сечений прямой с наклоном или . См. рисунок выше.
- Число 0,010010100…, десятичные цифры которого являются цифрами бесконечного слова Фибоначчи, трансцендентно.
- Буквы «1» можно найти в позициях, задаваемых последовательными значениями верхней последовательности Витхоффа (OEIS A001950):
- Буквы «0» можно найти в позициях, задаваемых последовательными значениями нижней последовательности Витхоффа (OEIS A000201):
- Распределение точек на единичной окружности, размещённых последовательно по часовой стрелке на золотой угол , образует шаблон из двух длин на единичной окружности. Хотя описанный выше процесс образования слова Фибоначчи не соответствует напрямую последовательному делению сегментов окружности, этот шаблон равен , если начинать с точки, ближайшей по часовой стрелке, при этом 0 соответствует длинному расстоянию, а 1 соответствует короткому расстоянию.
- Бесконечное слово Фибоначчи может содержать повторение 3 последовательных идентичных подслов, но никогда не содержит 4 таких подслова. Критический индекс[англ.] для бесконечного слова Фибоначчи равен повторений[5]. Это наименьший индекс (или критический индекс) среди всех слов Штурма.
- Бесконечное слово Фибоначчи часто упоминается как худший случай[англ.] для алгоритмов выявления повторений в строке.
- Бесконечное слово Фибоначчи является морфическим словом[англ.], образованным из {0,1}* путём эндоморфизма 0 → 01, 1 → 0[6].
Приложения
[править | править код]Построения слов Фибоначчи используются для моделирования физических систем с непериодическим порядком, таких как квазикристаллы, и изучения свойств рассеяния света кристаллов со слоями Фибоначчи[7].
См. также
[править | править код]Примечания
[править | править код]- ↑ Последовательность называется финально периодической с параметрами , если выполняется условие для , где и целые, , . Наименьшее такое число называется периодом последовательности. Последовательность называется -периодической, если (Липницкий, Чесалин, 2008, с. 27).
- ↑ Adamczewski, Bugeaud, 2010, с. 443.
- ↑ Lothaire, 2011, с. 47.
- ↑ de Luca, 1995.
- ↑ Allouche, Shallit, 2003, с. 37.
- ↑ Lothaire, 2011, с. 11.
- ↑ Dharma-wardana, MacDonald, Lockwood, Baribeau, Houghton, 1987.
Литература
[править | править код]- 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:10.1103/physrevlett.58.1761.
- 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 // Information Processing Letters. — 1995. — Т. 54, вып. 6. — С. 307–312. — doi:10.1016/0020-0190(95)00067-M.
- Mignosi F., Pirillo G. Repetitions in the Fibonacci infinite word // 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.
Ссылки
[править | править код]- A detailed and accessible description, on Ron Knott’s site
- Weisstein, Eric W. Rabbit Sequence (англ.) на сайте Wolfram MathWorld.
- Видео на YouTube
Для улучшения этой статьи желательно:
|