跳到主要內容

臺灣博碩士論文加值系統

(44.222.64.76) 您好!臺灣時間:2024/06/15 06:39
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳友明
研究生(外文):Yu-Ming Chen
論文名稱:受方向限制的格子路徑總數之計算
論文名稱(外文):Enumerating the Constrained Lattice Paths
指導教授:許舜斌
指導教授(外文):Shun-Pin Hsu
口試委員:張鈺欽許嘉宏
口試日期:2014-07-30
學位類別:碩士
校院名稱:國立中興大學
系所名稱:電機工程學系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:中文
論文頁數:46
中文關鍵詞:
外文關鍵詞:no
相關次數:
  • 被引用被引用:0
  • 點閱點閱:215
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
計算受方向限制的格子路徑數目總數在組合數學是一個經典題目,而且這仍然是學術界持續關注的研究領域。雖然格子路徑的結構是容易理解的,但是大部分的定理仍未得到證實,甚至未知。查明格子路徑數目的共同點是所有這些數列可以用二項式係數來表示,本篇論文將利用組合與代數,從遞迴的描述推導出公式。

本文第一章介紹研究動機與格子路徑的基本架構,並回顧相關的文獻 在相關文獻中 學者提出了以 Catalan numbers Motzkin numbers。來提出在格子路徑增加了 3 種固定的方向的問題的一個簡單且正確的公式。

第二章介紹組合數學中常發生的問題:Catalan numbers,並且從分析組合數學來提出 Catalan numbers 的證明 接著 提出一些 Catalan numbers 的應用,例如: Ballot Problem。

第三章主要探討在格子路徑增加了固定的方向,本研究增加了 3種固定的方向 將問題分成 4 大類 並在後兩類的問題中使用,「映射」關係來進行討論與證明。

第四章將延伸在格子路徑增加了固定的方向的問題,增加了禁止移動到 y l l 0, 1, 2以下的地方的限制,本研究將分析 l 負整數的情況。在完成分析後,本文提出一個公式來解決問題並證明公式。

最後,第五章對研究成果作個結論,並提出未來改進之方向。


Enumerating the total number of constrained lattice paths is a well- established subject in combinatorics and constitutes a crucial research topic in academia. Although the architecture of lattice paths is easily understood, most proposed theorems have not yet been confirmed. The number of lattice paths is identified to enable all of the obtained series to be used to represent binomial coefficients. This study entailed employing combination and algebraic methods to derive a formula from the description of occurring recursions.

Section 1 introduces the research motivation as well as the basic structure of lattice paths and presents a literature review. In relevant literature, the issue of Catalan and Motzkin numbers has been raised. Various studies have proposed increasing the lattice paths in three types of fixed direction and correcting a simple formula.

Section 2 describes the mathematical problems that often occur in combination: the occurrence of Catalan numbers and the difficulty in proving them based on a combination of mathematical analyses. In addition, various applications for Catalan numbers are proposed; for example, the can be employed to solve the Ballot problem.

Section 3 presents an approach to increasing the fixed direction of lattice paths; in addition to the three types of fixed direction, the problem was divided into four categories, and the use of “bijection” the relationship to the latter two issues in discussions and proof.

Section 4 details an extension of the problem of increasing the fixed direction of lattice paths, increasing the restriction of the ban on moving to where y l l 0, 1, 2 or less, this study analyzed l  negative integers. Based on the analysis, this paper proposes a formula to solve the problem and prove the formula.

Finally, Section 5 provides the conclusion and recommendations for future research.


摘要 I
Abstract III
目錄 V
圖目錄 VII
表目錄 IX
第一章 緒論 1
1.1研究動機 1
1.2文獻回顧 1
1.3 論文架構 2
第二章 相關理論與問題描述 3
2.1前言 3
2.2 Catalan Numbers 的基本性質 3
2.3 Catalan Numbers 的應用與證明 4
第三章 Directed Lattice Paths 15
3.1前言 15
3.2 Motzkin Numbers 17
3.3 Number of directed animals of size n 21
第四章 Constrained Lattice Paths 30
4.1前言 30
4.2問題架構與符號定義 31
4.3推導與證明公式 31
第五章 結論與未來展望 44
5.1結論 44
5.2 未來展望 44
Reference 45


[1] R. Donaghey, and L. W. Shapiro, “Motzkin numbers,” Journal of Combinatorial Theory, Series A, vol. 23, no. 3, pp. 291-301, November, 1977.
[2]D. Dhar, M. K. Phani, and M. Barma, “Enumeration of directed site animal on two-dimensional lattice,” Journal of Physics A, vol. 15, no. 6, pp. 279-284, 1982.
[3] D. Gouyou-Beauchamps, and G. Viennot, “Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem,” Advances in Applied Mathematics, vol. 9, no. 3, pp. 334-357, September, 1988.
[4] M. Bousquet-Mélou*, “New enumerative results on two-dimensional directed animals,” Discrete Mathematics, vol. 180, no. 1-3, pp. 73-106, February, 1998.
[5] E. Barcucci, A. D. Lungo, E. Pergola, and R. Pinzani, “Directed animals, forests and permutations,” Discrete Mathematics, vol. 204, no. 1-3, pp. 41-71, June, 1999.
[6] P. Barry, “Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences,” Mathematics Subject Classification, 2010.
[7] D. E. Davenport, L. W. Shapiro, and L. C. Woodson, “The Double Riordan Group,” The Electronic Journal of Combinatorics, vol. 18, no. 2, 2011.
[8] N.J.A.Sloane."EncyclopediaofIntegerSequences," http://www.research.att.com/˜njas/sequences.
[9] P. Hilton, and J. Pedersen, “Catalan Numbers, Their Generalization, and Their Uses,” The Mathematical Intelligencer, vol. 13, no. 2, 1991.
[10] M. Renault, “Four Proofs of the Ballot Theorem,” MATHEMATICS MAGAZINE, vol. 80, no. 5, DECEMBER, 2007.
[11]林晉宏, “一般性 Catalan 數的組合意義及其應用,” 數學傳播, vol. 35, no. 1, pp. 36-50, 民國 100 年.
[12]許介彥, “Catalan Numbers 簡介,” 科學教育月刊, vol. 247, 中華民國九十一年三月.
[13] W. Chu, “A new combinatorial interpretation for generalized Catalan number,” Discrete Mathematics, vol. 65, no. 1, pp. 91-94, May, 1987.
[14] R. P. Stanley, Enumerative Combinatorics, Cambridge Cambridge University Press, 2011.
[15] B. E. Sagan, “Proper partitions of a polygon and k-Catalan numbers,” Ars Combinatoria, vol. 88, pp. 109-124, July, 2008.
[16] S. Johnson, “ANALYTIC COMBINATORICS OF PLANAR LATTICE PATHS,” master of Science, University of Newcastle, 2012.
[17] E. Deutsch, and B. E. Sagan, “Congruences for Catalan and Motzkin numbers and related sequences,” Journal of Number Theory 117, pp. 191-215, 2006.
[18] P. Blasiak, “Motzkin Numbers, Central Trinomial Coefficients and Hybrid Polynomials,” Journal of Integer Sequences, vol. 11, 2008.
[19] G. E. Andrews, and R. J. Baxter, “Lattice Gas Generalization of the Hard Hexagon Model. III. q-Trinomial Coefficients,” Journal of Statistical Physics, vol. 47, no. 3-4, pp. 297-330, May, 1987.
[20] D. Romik, “Some formulas for the central trinomial and Motzkin numbers,” Journal of Integer Sequences, vol. 6, 2003.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top