Изменения

Перейти к: навигация, поиск

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

1051 байт убрано, 23:35, 8 июня 2016
Нет описания правки
==Обобщенная строка Фибоначчи. Связь с задачей о построении <tex>(\alpha, r)</tex>-исключений==Начнем обобщение идеи строк Фибоначчи следующим образом. Вместо отдельных символов <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, \dotsldots\}</tex>, и, наконец, определить <tex>n</tex>-ую обобщенную строку Фибоначчи как:
{{Определение
|definition=Обобщенная строка Фибоначчи (англ. ''generalized Fibostring'') имеет вид <tex>f_n(x,y) = h^n(y)</tex>
|definition=Определим '''бесконечную обобщенную строку Фибоначчи <tex>f_{\infty}(x,y)</tex>''' (англ. ''generalized infinite Fibostring'') как строку, содержащую все строки <tex>f_n(x,y), n \geqslant 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>
{{Лемма
|about = 2
|statement=Для любого целого <tex>n \geqslant 2</tex> выполняется равенство <tex>f^2_n f_n = f_{n+1-k}(f_{n-2k+1},f_k)</tex>|proof= <tex>f_{h^n+1}f_(y) = h^{n-2k}(h^k(y))</tex> <tex>f_n(x,y) =f_{n}h^k(f_{n-1k}(x,y)) = f_{n-2k}(h^k(x),h^k(y)) =f_{n-k}f_(h^{nk+1}(y),h^k(y))</tex>
}}
{{Лемма'''Например''':|about = 3|statement= Для любого целого <tex>n \geqslant 3</tex> строка <tex>f_n</tex> имеет [[Основные_определенияf_7 = f_5(f_3,_связанные_со_строками#border|бордеры]] <tex>f_i</tex> для <tex>i f_2) = n-2, n-4,\dots,2-(n\,\,mod \,\,2xyx)(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} \ldots</tex>
{{Утверждение
|about=1|statement=Бесконечная строка Фибоначчи В <tex>f_{\infty}f_n(x,y)</tex> является решением {{Acronym | задачи построения (2,4)-исключения| Требуется построить бесконечную строковую последовательность на алфавите размером 2, свободную от кратных подстрок порядка 4, но содержащую кратные не может содержаться подстроки порядков <tex>x^3</tex> или <tex>y^2 и 3 }} </tex>
}}
{{Утверждение|about=2|statement = Для любого <tex>n<!-- /tex><tex>f_nf_{n+1} \neq f_{n+1}f_n</tex>|proof = Докажем это утверждение методом математической индукции.-->
<!--==Теорема=====Вспомогательные леммы и определения===Начнем обобщение идеи строк Фибоначчи следующим образом1) База. Вместо отдельных символов <tex>a</tex> и <tex>b</tex> будем оперировать двумя произвольными строками <tex>x,y f_0f_1 \in \Sigma^*</tex>:*<tex>h(x) = xy</tex>*<tex>h(y) = x</tex>Таким образом "старый" морфизм будет частным случаем "нового" морфизма при <tex>x = a</tex> и <tex>y = bneq f_1f_0</tex>.
По аналогии можно вычислить 2) Переход. <tex>h^*(y) f_nf_{n+1}= \f_nf_nf_{y, x, xy, xyx, \dots\n-1}</tex>, и ,наконец, определить =f_nf_{n-ую обобщенную строку Фибоначчи как:1}f_{n-2}f_{Определение|definition=Обобщенная строка Фибоначчи имеет вид <tex>f_n(x,y) = h^n(y)-1}</tex>}}
Первые несколько обобщенных строк имеют вид:*<tex>f_0(x,y) f_{n+1}f_n= 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_nf_{n-1}f_n(x,y) = f_nf_{n-1}f_{n-1}(x,y)f_{n-2}(x,y)</tex>
{{Определение|definition=Определим '''бесконечную обобщенную строку Фибоначчи Но то, что <tex>f_{n-2}f_{n-1} \inftyneq f_{n-1}(x,y)</tex>''' как строку, содержащую все строки <tex>f_n(x,y), f_{n \geqslant 0-2} </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 = 13
|statement=Для любого целого <tex>n \geqslant 2</tex> выполняется равенство <tex>f^2_n = f_{n+1}f_{n-2}</tex>
|proof= <tex>f_{n+1}f_{n-2}=f_{n}f_{n-1}f_{n-2}=f_{n}f_{n}</tex>
}}
{{Лемма
|about = 24|statement= Для любого целого <tex>n \geqslant 3</tex> строка <tex>f_n</tex> имеет грани [[Основные_определения,_связанные_со_строками#border|бордеры]] <tex>f_i</tex> для <tex>i = n-2, n-4,\dotsldots,2-(n\,\,mod \,\,2)</tex>
}}
==Обратный морфизм=={{Определение|definition= Обратный морфизм <tex>h^{-1}</tex> определяется как отображение <tex>ab \rightarrow a</tex>, <tex> a \rightarrow a </tex> (если после <tex>a</tex> следует <tex>b</tex>) или <tex> a \rightarrow b</tex> (в противном случае) }}Обратный морфизм позволяет из строки <tex>f_n</tex> получить строку <tex>f_{n-1}</tex>== Связь с задачей о построении исключений=={{Утверждение|about=3|statement= Для любого целого <tex>n \geqslant 7</tex> <tex>f_n</tex> содержит куб некоторой подстроки|proof = Строка <tex>f_7 = xyxxyxyxxyxxyxyxxyxyx</tex> содержит подстроку <tex>xyxxyxxyx = (xyx)^3 </tex> и является префиксом <tex>f_n</tex> для <tex>n \geqslant 7</tex> }}
{{Теорема
|about=1|statement=Все строки Фибоначчи Никакая строка <tex>f_n</tex> при не содержит подстроки кратности <tex>4</tex>n }}{{Утверждение|about= 4|statement=Бесконечная строка Фибоначчи <tex>f_{\geqslant 7infty}</tex> содержат кубыявляется решением {{Acronym | задачи построения (2, но ни одна строка Фибоначчи не содержит 4)-исключения| Требуется построить бесконечную строковую последовательность на алфавите размером 2, свободную от кратных подстрок четвертого порядка4, но содержащую кратные подстроки порядков 2 и 3 }}|proof= Это следует из утверждения и теоремы выше
}}
-->
== См. также ==
* [[Слово Туэ-Морса]]
AMaltsev
129
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/55015»

Навигация