Слово Фибоначчи
Двоичная последовательность из повторения Фибоначчи
Характеристика последовательности резки с линией наклона или с золотым сечением . 1 / φ {\displaystyle 1/\varphi} φ − 1 {\displaystyle \varphi -1} φ {\displaystyle \varphi}
Кривые Фибоначчи, составленные из 10-го и 17-го слов Фибоначчи [1]

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

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

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

Определение

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

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

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

С 0 {\displaystyle S_{0}}    0
С 1 {\displaystyle S_{1}}    01
С 2 {\displaystyle S_{2}}    010
С 3 {\displaystyle S_{3}}    01001
С 4 {\displaystyle S_{4}}    01001010
С 5 {\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, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, ... (последовательность A003849 в OEIS )

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

N - я цифра слова равна , где — золотое сечение , а — функция пола (последовательность A003849 в OEIS ). Как следствие, бесконечное слово Фибоначчи можно охарактеризовать последовательностью разрезания линии наклона или . Смотрите рисунок выше. 2 + ⌊ н φ ⌋ − ⌊ ( н + 1 ) φ ⌋ {\displaystyle 2+\lfloor n\varphi \rfloor -\lfloor (n+1)\varphi \rfloor } φ {\displaystyle \varphi} ⌊   ⌋ {\displaystyle \lfloor \,\ \rfloor } 1 / φ {\displaystyle 1/\varphi} φ − 1 {\displaystyle \varphi -1}

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

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

Однако эта последовательность отличается от слова Фибоначчи лишь незначительно: нули заменены единицами, а позиции смещены на единицу.

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

N- я цифра слова — ⌊ н φ ⌋ − ⌊ ( н − 1 ) φ ⌋ − 1. {\displaystyle \lfloor n\varphi \rfloor -\lfloor (n-1)\varphi \rfloor -1.}

Обсуждение

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

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

  • Бесконечное слово Фибоначчи не является периодическим и не является в конечном счете периодическим. [2]
  • Последние две буквы слова Фибоначчи — это попеременно «01» и «10».
  • Подавление последних двух букв слова Фибоначчи или добавление дополнения к последним двум буквам создает палиндром . Пример: 01 S 4 = 0101001010 — палиндром. Таким образом, палиндромная плотность бесконечного слова Фибоначчи равна 1/φ, где φ — золотое сечение : это наибольшее возможное значение для апериодических слов. [3]
  • В бесконечном слове Фибоначчи отношение (количество букв)/(количество нулей) равно φ, как и отношение нулей к единицам. [4]
  • Бесконечное слово Фибоначчи — это сбалансированная последовательность : возьмите два фактора одинаковой длины в любом месте слова Фибоначчи. Разница между их весами Хэмминга (количеством появлений «1») никогда не превышает 1. [5]
  • Подслова 11 и 000 никогда не встречаются. [6]
  • Функция сложности бесконечного слова Фибоначчи равна n  + 1: оно содержит n  + 1 различных подслов длины n . Пример: имеется 4 различных подслова длины 3: "001", "010", "100" и "101". Будучи также непериодическим, оно имеет "минимальную сложность", и, следовательно, является словом Штурма , [7] с наклоном . Бесконечное слово Фибоначчи является стандартным словом, генерируемым директивной последовательностью (1,1,1,....). 1 / φ {\displaystyle 1/\varphi}
  • Бесконечное слово Фибоначчи является рекуррентным, то есть каждое подслово встречается бесконечно часто.
  • Если является подсловом бесконечного слова Фибоначчи, то также является его переворотом, обозначаемым . ты {\displaystyle u} ты Р {\displaystyle u^{R}}
  • Если — подслово бесконечного слова Фибоначчи, то наименьший период — число Фибоначчи. ты {\displaystyle u} ты {\displaystyle u}
  • Конкатенация двух последовательных слов Фибоначчи «почти коммутативна» и отличается только двумя последними буквами. С н + 1 = С н С н − 1 {\displaystyle S_{n+1}=S_{n}S_{n-1}} С н − 1 С н {\displaystyle S_{n-1}S_{n}}
  • Число 0,010010100..., цифры которого построены из цифр бесконечного слова Фибоначчи, является трансцендентным .
  • Буквы «1» можно найти в позициях, заданных последовательными значениями верхней последовательности Витхоффа (последовательность A001950 в OEIS ): ⌊ н φ 2 ⌋ {\displaystyle \lfloor n\varphi ^{2}\rfloor }
  • Буквы «0» можно найти в позициях, заданных последовательными значениями нижней последовательности Витхоффа (последовательность A000201 в OEIS ): ⌊ н φ ⌋ {\displaystyle \lfloor n\varphi \rfloor }
  • Распределение точек на единичной окружности , последовательно размещенных по часовой стрелке золотым углом , создает узор из двух длин на единичной окружности. Хотя вышеописанный процесс генерации слова Фибоначчи не соответствует напрямую последовательному делению сегментов окружности, этот узор имеет место, если узор начинается в точке, ближайшей к первой точке по часовой стрелке, при этом 0 соответствует длинному расстоянию, а 1 — короткому. н = Ф к {\displaystyle n=F_{k}} 2 π φ 2 {\displaystyle {\frac {2\pi }{\varphi ^{2}}}} 2 π φ к − 1 , 2 π φ к {\displaystyle {\frac {2\pi }{\varphi ^{k-1}}}, {\frac {2\pi }{\varphi ^{k}}}} С к − 1 {\displaystyle S_{k-1}}
  • Бесконечное слово Фибоначчи содержит повторения 3 последовательных идентичных подслов, но ни одного из 4. [2] Критический показатель для бесконечного слова Фибоначчи равен . [8] Это наименьший индекс (или критический показатель) среди всех слов Штурма. 2 + φ ≈ 3.618 {\displaystyle 2+\varphi \approx 3.618}
  • Бесконечное слово Фибоначчи часто упоминается как наихудший случай для алгоритмов, обнаруживающих повторения в строке.
  • Бесконечное слово Фибоначчи — это морфическое слово , порожденное в {0,1}* эндоморфизмом 0 → 01, 1 → 0. [9]
  • Элемент n слова Фибоначчи равен 1, если представление Цекендорфа (сумма определенного набора чисел Фибоначчи) числа n включает 1, и равен 0, если оно не включает 1. с н {\displaystyle s_{n}}
  • Цифры слова Фибоначчи можно получить, взяв последовательность фибоначчи-двоичных чисел по модулю 2. [10]

Приложения

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

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

Примечания

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

Ссылки

  • Адамчевский, Борис; Бюжо, Ян (2010), "8. Трансцендентность и диофантовы приближения", в Берте, Валери ; Риго, Майкл (ред.), Комбинаторика, автоматы и теория чисел , Энциклопедия математики и ее приложений, т. 135, Кембридж: Cambridge University Press , стр. 443, ISBN 978-0-521-51597-9, Збл  1271.11073.
  • Аллуш, Жан-Поль; Шаллит, Джеффри (2003), Автоматические последовательности: теория, приложения, обобщения , Cambridge University Press , ISBN 978-0-521-82332-6.
  • Берстель, Жан (1986), «Слова Фибоначчи – Обзор» (PDF) , в Розенберг, Г.; Саломаа, А. (ред.), Книга 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.
  • Dharma-wardana, MWC; MacDonald, AH; Lockwood, DJ; Baribeau, J.-M.; Houghton, DC (1987), "Рамановское рассеяние в сверхрешетках Фибоначчи", Physical Review Letters , 58 (17): 1761– 1765, Bibcode : 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, ISBN 978-90-481-6545-2, МР  2076798.
  • Лотер, М. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, т. 17 (2-е изд.), Cambridge University Press , ISBN 0-521-59924-5.
  • Лотер, М. (2011), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, т. 90, Cambridge University Press , ISBN 978-0-521-18071-9. Переиздание 2002 года в твердом переплете.
  • де Лука, Альдо (1995), «Свойство деления слова Фибоначчи», Information Processing Letters , 54 (6): 307– 312, doi :10.1016/0020-0190(95)00067-M.
  • Миньози, Ф.; Пирилло, Г. (1992), «Повторения в бесконечном слове Фибоначчи», Informatique Théorique et Application , 26 (3): 199–204 , doi : 10.1051/ita/1992260301991.
  • Рамирес, Хосе Л.; Рубиано, Густаво Н.; Де Кастро, Родриго (2014), «Обобщение фрактала слов Фибоначчи и снежинки Фибоначчи», Теоретическая информатика , 528 : 40–56 , arXiv : 1212.1368 , doi : 10.1016/j.tcs.2014.02.003, MR  3175078, S2CID  17193119.
  • Подробное и доступное описание на сайте Рона Нотта
  • Вайсштейн, Эрик В. , «Последовательность кролика», MathWorld
  • Слово Фибоначчи (первые 200 000 бит) на YouTube
Взято с "https://en.wikipedia.org/w/index.php?title=Fibonacci_word&oldid=1241888163"