跳到主要內容

簡易檢索 / 詳目顯示

研究生: 李珮瑄
LEE,PEI-SHIUAN
論文名稱: 一個卡特蘭等式的重新審視
A Catalan Identity revisited
指導教授: 李陽明
Chen, Young-Ming
口試委員: 李陽明
Chen, Young-Ming
陳天進
Chen, Ten-Ging
蔡炎龍
Tsai, Yen-Lung
學位類別: 碩士
Master
系所名稱: 理學院 - 應用數學系
Department of Mathematical Sciences
論文出版年: 2020
畢業學年度: 108
語文別: 英文
論文頁數: 30
中文關鍵詞: 卡特蘭等式Dyck 路徑
外文關鍵詞: Catalan identity, Dyck path
DOI URL: http://doi.org/10.6814/NCCU202000719
相關次數: 點閱:71下載:14
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 本篇論文探討卡特蘭等式(n+2)Cn+1=(4n+2)Cn 證明方式以往都以計算方式推導得出,當我參加劉映君的口試時,發現她使用組合方法來證明這個等式。當我在尋找論文的主題時,讀到李陽明老師的一篇論文"The Chung Feller theorem revisited",發現Dyck 路徑也可以作為卡特蘭等式的組合證明,因此我們完成(n+2)Cn+1=(4n+2)Cn 的組合證明。
    通過Dyck 路徑證明卡特蘭等式可以得到以下優勢:
    1.子路徑C在切換過程中不會改變。
    2.由於x1中的P的子路徑B為空,因此在交換Ad和Bu部分後,生成新的缺陷
    必連接在原始子路徑C之後。
    由於x2 中的Q 的子路徑A為空,因此在Bu交換和Ad部分後,生成新的提
    升必連接在原始子路徑C之後。
    3.在計算函數g1(g2) 的反函數的過程中,缺陷(提升)恢復模式必遵循
    "後進先出"或"先進後出"規則。


    When we first prove the Catalan identity, (n+2)Cn+1=(4n+2)Cn. We often prove it by calculation. When I participated in the oral examination of Ying-Jun Liu’s essay, I found that she used a combinatorial proof to prove this identity.When I was looking for the subject of the thesis, I read a paper by professor Young-Ming Chen, "The Chung Feller theorem revisited", which found that Dyck paths could also be used as a combinatorial proof of the Catalan identity. Therefore, we completed the combinatorial proof of (n+2)Cn+1=(4n + 2)Cn.
    Proving the Catalan identity through the Dick paths can reveal the following advantages:
    1.The subpath C does not change during the process of
    switching of the portions Ad and Bu.
    2.Since the subpath B of P in x1 is empty, a new flaw
    generated after switching of the portions Ad and Bu must
    be followed by the original subpath C.
    Since the subpath A of Q in x2 is empty, a new lift
    generated after switching of the portions Bu and Ad must
    be followed by the original subpath C.
    3.In the process of computing the preimage of a function g1
    (g2), the flaws (lifts) recovery mode follows the "Last in First out" or "First in Last out".

    致謝 ii
    中文摘要 iii
    Abstract iv
    Contents v
    List of Figures vi
    1 Introduction 1
    2 Paths Start with Up-step 3
    3 Paths Start with Down-step 14
    4 Summary 25
    Appendix A examples of Catalan identity 26
    A.1 (n+2)Cn+1=(4n+2)Cn 26
    Bibliography 30

    [1] 劉映君. 一個卡特蘭等式的組合證明, 2017.
    [2] Ronald Alter. Some remarks and results on catalan numbers. 05 2019.
    [3] Ronald Alter and K.K Kubota. Prime and prime power divisibility of catalan numbers. Journal of Combinatorial Theory, Series A, 15(3):243 – 256, 1973.
    [4] Federico Ardila. Catalan numbers. The Mathematical Intelligencer, 38(2):4–5, Jun 2016.
    [5] Young-Ming Chen. The chung–feller theorem revisited. Discrete Mathematics, 308:1328–1329, 04 2008.
    [6] Ömer Eğecioğlu. A Catalan-Hankel determinant evaluation. In Proceedings of the Fortieth Southeastern International Conference on Combinatorics, Graph Theory and Computing, volume 195, pages 49–63, 2009.
    [7] R. Johnsonbaugh. Discrete Mathematics. Pearson/Prentice Hall, 2009.
    [8] Thomas Koshy. Catalan numbers with applications. Oxford University Press, Oxford, 2009.
    [9] Tamás Lengyel. On divisibility properties of some differences of the central binomial coefficients and Catalan numbers. Integers, 13:Paper No. A10, 20, 2013.
    [10] Youngja Park and Sangwook Kim. Chung-Feller property of Schröder objects. Electron. J. Combin., 23(2):Paper 2.34, 14, 2016.
    [11] Matej Črepinšek and Luka Mernik. An efficient representation for solving Catalan number related problems. Int. J. Pure Appl. Math., 56(4):589–604, 2009.

    QR CODE
    :::