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

Характеристика с помощью последовательности резки с линией наклона или , с в золотой пропорции .

{\ displaystyle 1 / \ varphi}

{\ displaystyle \ varphi -1}

{\ displaystyle \ varphi}

{\ displaystyle S_ {10}}

{\ displaystyle S_ {17}}

Кривые Фибоначчи, построенные из 10-го и 17-го слов Фибоначчи

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

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

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

Определение

Пусть будет «0» и «01». Теперь (объединение предыдущей и предыдущей последовательностей). ${\ displaystyle S_ {0}}$ ${\ displaystyle S_ {1}}$ ${\ 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 )

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

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

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

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

П - ^й разряд слова , где это золотое сечение и является функцией от пола . ${\ 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 _n равна F _{n + 2} , ( n + 2) -м числу Фибоначчи. Также количество единиц в S _n равно F _n, а количество нулей в S _n равно F _{n + 1} .

Прочие свойства

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

Приложения

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

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

Примечания

использованная литература

Адамчевский, Борис; Бюжо, Ян (2010), «8. Трансцендентность и диофантово приближение», в Берте, Валери ; Риго, Майкл (ред.), Комбинаторика, автоматы и теория чисел , Энциклопедия математики и ее приложений, 135 , Кембридж: Cambridge University Press , стр. 443, ISBN 978-0-521-51597-9, Zbl 1271,11073.
Аллуш, Жан-Поль; Шаллит, Джеффри (2003), Автоматические последовательности: теория, приложения, обобщения , Cambridge University Press , ISBN 978-0-521-82332-6.
Bombieri, E .; Тейлор, JE (1986), "Какие распределения вещества преломлять Первичное исследование?" (PDF) , Le Journal де Телосложение , 47 (C3): 19-28, DOI : 10,1051 / jphyscol: 1986303 , MR 0866320.
Дхарма-вардана, MWC; MacDonald, AH; Локвуд, диджей; Baribeau, J.-M .; Houghton, DC (1987), "комбинационное рассеяние света в сверхрешетках Фибоначчи", Physical Review Letters , 58 (17): 1761-1765, DOI : 10,1103 / physrevlett.58.1761 , PMID 10034529.
Кимберлинг, Кларк (2004), «Упорядочивание слов и наборов чисел: случай Фибоначчи», в Howard, Frederic T. (ed.), Applications of Fibonacci Numbers, Volume 9: Proceedings of the Tenth International Research Conference on Fibonacci Numbers and их применение , Дордрехт:. Kluwer Academic Publishers, стр 137-144, DOI : 10.1007 / 978-0-306-48517-6_14 , MR 2076798.
Лотэр, М. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, 17 (2-е изд.), Cambridge University Press , ISBN 0-521-59924-5.
Лотэр, М. (2011), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, 90 , Cambridge University Press , ISBN 978-0-521-18071-9. Перепечатка 2002 года в твердом переплете.
де Лука, Aldo (1995), "Свойство деление слова Фибоначчи", Information Processing Letters , 54 (6): 307-312, DOI : 10,1016 / 0020-0190 (95) 00067-M.
Миньози, Ф .; Pirillo, G. (1992), "Повторения в бесконечном слове Фибоначчи" , Informatique théorique и др приложение , 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.

Languages

In other projects