臺灣博碩士論文加值系統

令α = {a1, a2, ...} 為一個非負整數的序列(有限或是無窮), 其中a1  0 且an  1 對所
有的n  2, 令A = fa, bg 為一個字母集, 對於n  1 及r1r2 ...rn 2 Nn 其中0 · ri · ai
且1 · i · n, 利用一對相異的字母(a, b) 結合成一個n階α-字un[r1r2 ...rn], 以遞迴的方式
定義如下: u1 = b, u0 = a, u1[r1] = aa1r1bar1且un[r1r2 ...rn] = un1[r1r2 ... rn1]anrn
un2[r1r2 ... rn2]un1[r1r2 ... rn1]rn, 我們稱r1r2 ...rn 為字un[r1r2 ...rn] 的標籤, 並且
a, b 是標籤為空的α-字。關於α-字的結果在很多文章中都被廣泛的的提到, 其中有一些結果是關
於α-字的字典順序, 在本篇論文中, 我們證明一些關於α-字字典順序的結果。我們找到一個新的方
法來產生α-字, 且定義如下: 令w1 = b, w0 = a, w1[r1] = aa1r1bar1 , w2[r1r2] = w1[r1]r2a
w1[r1]a2r2 且
wn[r1r2 ... rn] =
wn1[r1r2...rn1]anrnwn2[r1r2 ...rn2]wn1[r1r2 ...rn1]rn
若n是奇數,
wn1[r1r2 ...rn1]rnwn2[r1r2 ...rn2]wn1[r1r2 ...rn1]anrn
若n是偶數,
我們證明了每一個wn[r1r2...rn] 都是α-字(見引理2.1), 我們用下列的方法, 建構一棵樹T : b
為樹T 的根, a是b唯一的子, w1[0], w1[1],...,w1[a1]為a的a1+1個子且wn+1[r1r2 ...rn0],
wn+1[r1r2 ... rn1], ... ,wn+1[r1r2 ... rnan+1] 則是wn[r1r2...rn] 的an+1 + 1個子, 這些頂
點都是由上到下排列, 我們用rn+1 標籤邊(wn[r1r2 ...rn], wn+1[r1r2 ...rnrn+1]), n  0,
α-字wn[r1r2...rn] 的新標籤r1r2...rn 代表一條從根b 到頂點wn[r1r2...rn] 的路徑, 我
們考慮在N+ 中以及A+ (a < b) 中的字典順序, 證明存在由新標籤構成的子集D, 使得
若n  1,r1r2...rn, s1s2...sn 2 D, 且r1r2 ...rn <l s1s2 ... sn 則wn[r1r2 ...rn] <l
wn[s1s2...sn], 換句話說, 若只看樹上那些新標籤屬於D 的n階α-字, 則這些α-字在樹上是由
上到下依照字典順序遞增的。

Let α = {a1, a2, ...} be a sequence (finite or infinite) of nonnegative integers
with a1  0 and an  1, for all n  2. Let A = {a, b} be an alphabet. For
n  1, and r1r2 ...rn 2 Nn, with 0 · ri · ai for 1 · i · n, there associates an
nth-order α-word un[r1r2 ...rn] derived from the pair (a, b). These α-words are defined
recursively as follows: u1 = b, u0 = a, u1[r1] = aa1r1bar1 and ui[r1r2 ¢ ¢ ¢ ri] =
ui1[r1r2 ...ri1]airiui2[r1r2 ...ri2]ui1[r1r2 ...ri1]ri , i  2. We call r1r2 ...rn the
label of the word un[r1r2...rn]. a, b are α-word with empty label. The properties of
α-words have been studied extensively. Some results on the lexicographic order for the
nth-order α-word are known. In this thesis, we prove some new results on the lexicographic
order of the nth-order α-words. We find a new method to generate the α-words
by defining w1 = b, w0 = a, w1[r1] = aa1r1bar1 , w2[r1r2] = w1[r1]r2aw1[r1]a2r2 and
for n  3,
wn[r1r2 ¢ ¢ ¢ rn] =
wn1[r1r2 ...rn1]anrnwn2[r1r2...rn2]wn1[r1r2 ...rn1]rn
if n is odd,
wn1[r1r2 ...rn1]rnwn2[r1r2... rn2]wn1[r1r2 ....rn1]anrn i
f n is even.
We show that each wn[r1r2 ...rn] is an α-word. We construct a tree T associated
with the set of α-words: b is the root (the leftmost vertex) of T, a is the only son
of b, w1[0], w1[1],...,w1[a1] are the sons of a and wn+1[r1r2 ...rn0], wn+1[r1r2 ¢ ¢ ¢ rn1],... , wn+1[r1r2 ...rnan+1] are the an+1 + 1 sons of wn[r1r2... rn], listing from top to
bottom. Label the edge (wn[r1r2...rn], wn+1[r1r2 ...rnrn+1]) by rn+1, n  0. The
new label r1r2 ¢ ¢ ¢ rn of the α-word wn[r1r2 ¢ ¢ ¢ rn] represents a path from the root b
to the vertex wn[r1r2...rn]. With the lexicographic order on N+ and A+ with a <
b, we prove that there exists a subset D of the set of all labels such that for n 
1, if r1r2 ...rn, s1s2 ... sn 2 D and r1r2 ¢ ¢ ¢ rn <l s1s2 ...sn, then wn[r1r2 ...rn] <l
wn[s1s2 ...sn]. In other words, in the above tree, the nth-order α-words whose new
labels belong to D are increasing from top to bottom in the lexicographic order.

Contents
摘要.......................................I
Abstract ..................................II
謝誌.......................................III
Contents ..................................IV
List Of Figure ............................V
List Of Tables ............................VI
1 Introduction ............................1
2 The lexicographic order of α-word .......5
3 Some Remarks ............................16
References ................................21
Appendix ..................................22

List of Figures
1 Tree T1 for α = {a1, a2, a3} . . . . . . . . . . . . . . . . 22
2 Tree T1 for α = {0, 1, 1, 1, 1} . . . . . . . . . . . . . . 23
3 Tree T2 for α = {0, 1, 1, 1, 1, 1} . . . . . . . . . . . . . 24
4 Set Dn in the tree T2 for α = {0, 1, 1, 1, 1, 1} . . . . . . 25
5 Tree T for α = {a1, a2, a3} . . . . . . . . . . . . . . . . 26
6 Tree T for α = {2, 1, 3} . . . . . . . . . . . . . . . . . . 27

List of Tables
1 w3[r] and u3[s] for α = {2, 1, 3} . . . . . . . . . . . . . . 6
2 dn,i for α = {2, 1, 3, 2, 1, 3, 4} . . . . . . . . . . . . . 9
3 α = {2, 1, 3} . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Set D3 for α = {2, 1, 3} . . . . . . . . . . . . . . . . . . .17
5 α = {0, 1, 1, 1, 1} . . . . . . . . . . . . . . . . . . . . . 19
6 Sets D5 and D5 for α = {0, 1, 1, 1, 1} . . . . . . . . . . .. 20

[1] Chun-Yu. Chen, Fibonacci 字與字典順序, 國科會補助大專學生參與專題研究計畫成果報告, 計畫編號: 93-2815-C-033 -020 -M, (2005)
[2] W.F. Chuan, Fibonacci words, The Fibonacci Quarterly 30.1 (1992) 68-76.
[3] W.F. Chuan, Symmetric Fibonacci word, The Fibonacci Quarterly 31.3 (1993)
251-255.
[4] W.F. Chuan, Embedding Fibonacci words into Fibonacci word patterns, in G.E.
Bergum, A.N. Philippou and A.F. Horadam, eds, Applications of Fibonacci
Number, Vol. 5 (Kluwer, Dordrecht, 1993) 113-122
[5] W.F. Chuan, Generating Fibonacci Word, The Fibonacci Quarterly 33.2 (1993)
104-112.
[6] W.F. Chuan, α-Word and factors of characteristic sequence, Discrete
Mathematics 177 (1997) 33-50.
[7] W.F. Chuan, A representation theorem of the suffixes of characteristic sequence,
Discrete Applied Mathematics 85 (1998) 47-57.
[8] W.F. Chuan, Characterizations of α-word, moments, and determinants, The
Fibonacci Quarterly 41.3 (2003) 194-208.
[9] W.F. Chuan, Moments of conjugacy classes of binary words, Theoretical
Computer Science 310 (2004) 273-285.
[10] W.F. Chuan, Factors of characteristic words of irrational numbers, Theoretical Computer Science 337 (2005) 169-182.
[11] M. Lothaire, Combinatorics on Words (Addison-Wesley, Reading, MA, 1983).
[12] H.J. Shyr, Free Monoids and Languages, Lecture Notes, Institute of Applied
Mathematics, National Chung-Hsing University, Taichung, Taiwan, ROC, 2001.