- 學位論文
Fibonacci 字的對稱逆--邊緣分解
Factorization of Fibonacci Words Involving Palindrome Inverses and Borders
摘要
{摘要} 令 $A= { a,b }$. 令 $n geq 3$, $r_1, cdots ,r_{n-2} in {0,1 }$. 第 $n$ 階的 Fibonacci 字 $w_n^{r_1r_2 ldots r_{n-2}}$ 定義如下: $w_1=a$, $w_2=b$, $w_3^0=ba$, $w_3^1=ab$, $w_4^{00}=bab$, $w_4^{11}=bab$, $w_4^{01}=bba$, $w_4^{10}=abb$, 當 $5 leq k leq n$, $w_k^{r_1 cdots r_{k-2}} = left { egin{array}{ll} w_{k-1}^{r_1r_2 cdots r_{k-3}}w_{k-2}^ {r_1r_2 cdots r_{k-4}}, & r_{k-2}=0 w_{k-2}^{r_1r_2 cdots r_{k-4}}w_{k-1}^ {r_1r_2 cdots r_{k-3}}, & r_{k-2}=1. end{array} ight.$ end{center} 當 $n geq 4$ 時, 將 $w_n^{00 cdots 0}$ 以 $w_n^0$ 表示. 如果存在非空字 $u$, $v$ 使得 $w=xu=vx$, 則 $x$ 稱為非空字 $w$ 的邊緣. 令非空字 $w$ 為一個非對稱字. 如果一個非空字 $x$ 使得 $xw$ (或 $wx$) 為一個對稱字且 $x$ 為所有滿足此條件的字中最短的字, 則 $x$ 被稱為 $w$ 的左對稱逆 (或右對稱逆). 在 [12] 與 [14] 證明出 Fibonacci 字 $w_n^0$ 的最長邊緣為 $w_{n-2}^0$. 本篇中, 我們得到所有有邊的 Fibonacci 字的邊緣仍為 Fibonacci 字. 更精確的來說, 如果 $w_n^{r_1r_2 ldots r_{n-2}}$ 的指標 $r_1, ldots ,r_{n-2}$ 以 $00(10)^k$ 或 $11(01)^k$ 做為結尾, 其中 $0 leq k leq frac{1}{2}(n-4)$, 則該字的最長邊緣為 $w_{n-2}^{r_1r_2 ldots r_{n-4}}$; 如果指標 $r_1, ldots ,r_{n-2}$ 以 $00(10)^{k-1}1$ 或 $11(01)^{k-1}0$ 做為結尾, 其中 $1 leq k leq frac{1}{2}(n-3)$, 則該字的最長邊緣為 $w_{n-1}^{r_1r_2 ldots r_{n-3}}$. 左對稱逆與右對稱逆這種概念, 首先出現於 [15]. 我們將證明所有非對稱的 Fibonacci 字的左對稱逆與右對稱逆的乘積 (又稱為 LR-乘積及 RL-乘積) 仍然為 Fibonacci 字. 進一步來說, 由所有有邊緣非對稱的 $n$ 階 Fibonacci 字的 RL-乘積與 LR-乘積構成的集合恰好等於由所有 $n-1$ 與 $n-2$ 階的 Fibonacci 字構成的集合. 最後我們將介紹有邊緣非對稱的 Fibonacci 字的對稱逆-邊緣分解, 這分解式包含該字本身的對稱逆與最長邊緣.
並列摘要
Abstract Let $A= { a,b }$. In [2], the $n$-th order Fibonacci word $w_n^{r_1r_2 ldots r_{n-2}}$ over $A$, where $r_1, cdots ,r_{n-2} in {0,1 }$, was defined recursively as follows: $w_1=a$, $w_2=b$, $w_3^0=ba$, $w_3^1=ab$, $w_4^{00}=bab$, $w_4^{11}=bab$, $w_4^{01}=bba$, $w_4^{10}=abb$, $w_k^{r_1 cdots r_{k-2}} = left { egin{array}{ll} w_{k-1}^{r_1r_2 cdots r_{k-3}}w_{k-2}^ {r_1r_2 cdots r_{k-4}}, & r_{k-2}=0 w_{k-2}^{r_1r_2 cdots r_{k-4}}w_{k-1}^ {r_1r_2 cdots r_{k-3}}, & r_{k-2}=1 end{array} ight.$ , for $5 leq k leq n$. Write $w_n^0$ for $w_n^{00 cdots 0}$, $n geq 4$. A nonempty word $x$ is called a $border$ of a nonempty word $w$ if there exist nonempty words $u$, $v$ such that $w=xu=vx$. A nonempty word $x$ is said to be a $left$ (resp., $right$) $palindrome$ $inverse$ of a nonpalindrome $w$, if $xw$ (resp., $wx$) is a palindrome and $|y| geq |x|$ whenever $y$ is a nonempty word such that $yw$ (resp., $wy$) is a palindrome. Here $|u|$ denotes the length of $u$. It was proved in [12] and [14] that the longest border of Fibonacci word $w_n^0$ is $w_{n-2}^0$. In this paper, we prove that borders of bordered Fibonacci words are themselves Fibonacci words. More precisely, the longest border of $w_n^{r_1r_2 ldots r_{n-2}}$ is $w_{n-2}^{r_1r_2 ldots r_{n-4}}$ if its label $r_1, ldots ,r_{n-2}$ ends with $00(10)^k$ or $11(01)^k$ for some $k$, $0 leq k leq frac{1}{2}(n-4)$; the longest border is $w_{n-1}^{r_1r_2 ldots r_{n-3}}$ if its label ends with $00(10)^{k-1}1$ or $11(01)^{k-1}0$ for some $k$, $1 leq k leq frac{1}{2}(n-3)$. The notion of left and right palindrome inverses was introduced by Lee in [15]. We proved that the products of the left and right palindrome inverses (also called LR-product and RL-product) of any nonpalindromic Fibonacci word are still Fibonacci words. Furthermore, the set of all the RL-products and LR-products of bordered, nonpalindromic Fibonacci words of order $n$ is precisely the set of all Fibonacci words of orders $n-1$ and $n-2$. Finally we obtain a factorization theorem of bordered, nonpalindromic Fibonacci words, involving their palindrome inverses and their longest borders.