Слово Фибоначчи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Лемма: fixup)
Строка 57: Строка 57:
 
Также можно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.
 
Также можно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.
  
 +
<!--
 +
==Теорема==
 +
===Вспомогательные леммы и опредления===
 +
Начнем обобщение идеи строк Фибоначчи следующим образом. Вместо отдельных символов <tex>a</tex> и <tex>b</tex> будем оперировать двумя произвольными строками <tex>x,y \in \Sigma^*</tex>:
 +
*<tex>h(x) = xy</tex>
 +
*<tex>h(y) = x</tex>
 +
Таким образом "старый" морфизм будет частным случаем "нового" морфизма при <tex>x = a</tex> и <tex>y = b</tex>.
 +
 +
По аналогии можно вычислить <tex>h^*(y) = \{y, x, xy, xyx, \dots\}</tex>, и ,наконец, определить n-ую обобщенную строку Фибоначчи как:
 +
{{Определение
 +
|definition=Обобщенная строка Фибоначчи имеет вид <tex>f_n(x,y) = h^n(y)</tex>
 +
}}
 +
 +
Первые несколько обобщенных строк имеют вид:
 +
*<tex>f_0(x,y) = y</tex>
 +
*<tex>f_1(x,y) = x</tex>
 +
*<tex>f_2(x,y)= xy</tex>
 +
*<tex>f_3(x,y)= xyx</tex>
 +
*<tex>f_4(x,y) = xyxxy</tex>
 +
А также в общем случае:
 +
*<tex>f_n(x,y) = f_{n-1}(x,y)f_{n-2}(x,y)</tex>
 +
 +
{{Определение
 +
|definition=Определим  '''бесконечную обобщенную строку Фибоначчи <tex>f_{\infty}(x,y)</tex>''' как строку, содержащую все строки <tex>f_n(x,y), n \geq 0</tex> в качестве префиксов
 +
}}
 +
 +
Поскольку <tex>h^n(y) = h^{n-k}(h^k(y))</tex>, то <tex>f_n(x,y) = h^k(f_{n-k}(x,y)) = f_{n-k}(h^k(x),h^k(y))</tex>, и, так как <tex>h^k(x) = h^{k+1}(y)</tex>, финально получаем:
 +
*<tex>f_n = f_{n-k}(f_{k+1},f_k)</tex>.
 +
'''Например''':
 +
<tex>f_7 = f_5(f_3, f_2) = (xyx)(xy)(xyx)(xyx)(xy)(xyx)(xy)(xyx)</tex>
 +
 +
Это равенство походит также и для <tex>f_{\infty}: f_{\infty} = f_{\infty}(f_{n+1},f_{n}) = f_{n+1}f_n f_{n+1} f_{n+1} f_n f_{n+1} f_n f_{n+1} \dots</tex>
 +
 +
 +
Так же имеют место быть 2 простые леммы.
 +
{{Лемма
 +
|about = 1
 +
|statement=Для любого целого <tex>n \geq 2</tex> выполняется равенство <tex>f^2_n = f_{n+1}f_{n-2}</tex>
 +
}}
 +
{{Лемма
 +
|about = 2
 +
|statement= Для любого целого <tex>n \geq 3</tex> строка <tex>f_n</tex> имеет грани <tex>f_i</tex> для <tex>i = n-2, n-4,\dots,2-(n\,\,mod \,\,2)</tex>
 +
}}
 +
 +
 +
 +
 +
 +
 +
 +
{{Теорема
 +
|statement=Все строки Фибоначчи <tex>f_n</tex> при <tex>n \geq 7</tex> содержат кубы, но ни одна строка Фибоначчи не содержит кратных подстрок четвертого порядка
 +
|proof=
 +
}}
 +
 +
-->
 
== См. также ==
 
== См. также ==
 
[[Слово Туэ-Морса]]
 
[[Слово Туэ-Морса]]

Версия 21:25, 16 июня 2012

Определение

Определение:
Морфизмом называется отображение [math]h : \Sigma^* \rightarrow \Sigma^*[/math], которое каждой букве [math]\lambda[/math] из алфавита [math]\Sigma[/math] ставит в соответствие строку [math]h(\lambda)[/math] из множества [math]\Sigma^{+}[/math],

затем данное отображение распространяется на [math]\Sigma^*[/math] следующим образом:

[math]h(s) = \left\{ \begin{array}{ll} h(s[1])h(s[2])...h(s[n]), & s \in \Sigma^+ \\ \varepsilon, & s \in \Sigma^0 \\ \end{array} \right. [/math]


Любой морфизм [math]h[/math] можно применять к исходной строке [math]s[/math] любое число раз, тем самым генерируя последовательность итераций [math]h^{*}(s)[/math] по следующему правилу:

    [math]h^{*}(s) = \{h^0(s), h^1(s),...\}[/math].

где [math]h^0(s) = s[/math] и для любого целого [math]k \geq 1 :[/math] [math] h^k(s) = h(h^{k-1}(s))[/math].

Например:

  • [math]\Sigma = \{a,b\}, h(a) = a, h(b) = ab[/math].
  • [math]h^*(a) = \{a,a,...\}[/math]
  • [math]h^*(b) = \{b, ab, a^2b,..., a^kb...\}[/math]


Определение:
Строками Фибоначчи являются строки над алфавитом [math]\Sigma = \{a, b\}[/math], полученные последовательным применением морфизма [math]h[/math]:
  • [math]h(a) = ab[/math]
  • [math]h(b) = a[/math]
к строке [math]s = b[/math], т.е. [math]h^*(b)[/math].


Первые несколько строк Фибоначчи:

  • [math]f_0 = b[/math]
  • [math]f_1 = a[/math]
  • [math]f_2 = ab[/math]
  • [math]f_3 = aba[/math]
  • [math]f_4 = abaab[/math]
  • [math]f_5 = abaababa[/math]

Лемма

Лемма:
Строки Фибоначчи удовлетворяют рекуррентному соотношению [math]f_n = f_{n-1}f_{n-2}, n \geq 2[/math].
Доказательство:
[math]\triangleright[/math]

Доказательство нетрудно получить методом математической индукции.

База: При [math]n = 2[/math] равенство очевидно.

Переход: Пусть [math]n \gt 2[/math] и [math]f_n = f_{n-1}f_{n-2}[/math]. [math]f_{n+1} = h(f_n) = h(f_{n-1}f_{n-2})[/math]. Так как отображение h — линейно (т.е. [math]h(xy) = h(x)h(y)[/math]), то можно продолжить равенство:

[math]f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}[/math].
[math]\triangleleft[/math]

Также можно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.

См. также

Слово Туэ-Морса

Источники

  • Билл Смит. Методы и алгоритмы вычислений на строках. Пер. с англ. — М.:ООО"И.Д.Вильямс", 2006. — 496 с.: ил. — Парал. тит. англ. ISBN 5-8459-1081-1 (рус.)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Слово_Фибоначчи&oldid=25475»