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

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

Описание посредством последовательности пересечений с прямой, имеющей наклон

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

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

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

Приложения

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

См. также

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

Примечания

Последовательность $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$ (Липницкий, Чесалин, 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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Последовательность $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$ (Липницкий, Чесалин, 2008, с. 27).

[_a536b7ea553dc163-2] Adamczewski, Bugeaud, 2010, с. 443.

[_bc15f7e28f87325c-3] Lothaire, 2011, с. 47.

[FOOTNOTEde_Luca1995-4] Luca (1995).

[_dbdbbc4129695982-5] Allouche, Shallit, 2003, с. 37.

[_bc15fae28f8737b5-6] Lothaire, 2011, с. 11.

[_f9fadc5a572c5a1a-7] Dharma-wardana, MacDonald, Lockwood, Baribeau, Houghton, 1987.