簡易檢索 / 詳目顯示
| 研究生： |
施耀振 |
|---|---|
| 論文名稱： |
A Bijective Proof of Complete Binary Trees |
| 指導教授： | 李陽明 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年： | 1990 |
| 畢業學年度： | 78 |
| 語文別： | 中文 |
| 論文頁數： | 29 |
| 相關次數： | 點閱：134 下載：0 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在此，將介紹一個從Tnc 映至Sn的bijection， 其中Tnc = {tc: tc 是一有2n-1 個點的complete binary tree ，其中有一點被圈選} & Sn={x: x是一有n個黑點，n-1個白點的string }。並藉此求得k1＊k 2＊... ＊kn在” ＊”不可結合( nonassociative )之下的二元運算( binary operation )方法數。這個解與Catalan number 一致。
第一章 緒論，第一節Introduction: (1) 介紹原始問題. (2)轉換問題成complete binary trees 的形式，(3) 確立本文目標。第二節是Background。
第二草是正文，第一節探討n-strings (有n個黑點n-1個白點的strings )的基本性質。第二節利用演算法2.2.1，求出n-strings 一個很特殊的點，再運用這點對n-strings 做濃縮(把○●●變成●)。第三節介紹要找的biJection，乃利用
(1) Preorder、Traversal 為 complete binary trees 的點排序，並在外點(external vertex)塗點，再給予適當的搬動，
(2) 把○●●濃縮成●之後，再把●適當的代換成 。最後附上如何運用recurrence relation 及generating function 解原始問題。
謝詞 . . . . . . . . . . . . . . . . . . . . . i
摘要. . . . . . . . . . . . . . . . . . . . . . ii
目錄. . . . . . . . . . . . . . . . . . . . . .iii
第一章 緒論. . . . . . . . . . . . . . . . . . . . . . 1
§1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . 1
§1.2 Background . . . . . . . . . . . . . . . . . . . . . 3
第二章A Bijective Proof of Complete Binary Trees . . . . . . . . . . . . . . . . . . . . .5
§2.1 N-strings . . . . . . . . . . . . . . . . . . . . . 5
§2.2 The Root of N-stings . . . . . . . . . . . . . . . . . . . . . 10
§2.3 The Bijective Proof . . . . . . . . . . . . . . . . . . . . . 17
附錄. . . . . . . . . . . . . . . . . . . . .27
參考文獻. . . . . . . . . . . . . . . . . . . . . . 29
[1] J. A. Bondy & U. S. R. Murty, Graph Theory With Application. London. Macmillan, 1976.
[2] Gary Chartrant & Linda Lesniak. Graphs & Digraphs. 2nd ed ., Wadsworth Inc., Belmont. 1986.
[3] Marshall Hall. JR., Combinatorial Theory, 2nd ed., New York, Wiley. 1986.
[4] Richard Johnsonbaugh, Discrete Mathematics, New York,Macmillan; London. Collier Macmillan. 1984.
[5] I. Niven. Formal Power Series, Amer. Math. Monthly 76 (1969), pp.871-889.
[6] Dennis Staton & Dennis White, Constructive Combinatorics. New York. Springer-Verlag, 1986, p.60.
[7] Alan Tucker. Applied Combinatorics, New York, Wiley, 1980.
[8] "Introduction to the Theory of Combinatorial Species", 由中央研究院數學研究所 葉永南 先生提供.
(限達賢圖書館四樓資訊教室A單機使用)