Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/131105
|
| Title: | 一個卡特蘭等式的重新審視
A Catalan Identity revisited |
| Authors: | 李珮瑄
LEE, PEI-SHIUAN |
| Contributors: | 李陽明
Chen, Young-Ming
李珮瑄
LEE,PEI-SHIUAN |
| Keywords: | 卡特蘭等式
Dyck 路徑
Catalan identity
Dyck path |
| Date: | 2020 |
| Issue Date: | 2020-08-03 17:57:15 (UTC+8) |
| Abstract: | 本篇論文探討卡特蘭等式(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". |
| Reference: | [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. |
| Description: | 碩士
國立政治大學
應用數學系
104751012 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0104751012 |
| Data Type: | thesis |
| DOI: | 10.6814/NCCU202000719 |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 101201.pdf | | 490Kb | Adobe PDF2 | 91 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
