Please use this identifier to cite or link to this item:
https://ah.lib.nccu.edu.tw/handle/140.119/18846
題名: | The Chung-Feller Theorem Revisited | 作者: | 李陽明 Chen, Young-Ming |
貢獻者: | 應數系 | 關鍵詞: | Dyck paths; Catalan numbers | 日期: | 四月-2008 | 上傳時間: | 24-十二月-2008 | 摘要: | Dyck paths are the most investigated objects related to the Catalan numbers Cn (see [2], [6], [5] and [8]). An n-Dyck path with k flaws is a path from (0,0) to (2n,0) with up (1,1) and down (1,-1) steps having k down steps below the x-axis. Surprisingly, the number of n-Dyck paths with k flaws is independent of k which is the Chung–Feller theorem. In [1], the famous theorem was first proved by means of analytic method. The theorem was subsequently treated by more combinatorial methods in [7] (using cyclic permutation) and in [4] (using the Taylor expansions of generating functions). Recently, Eu et al. [3] proved a refinement of this result. In this note, our purpose is to provide a direct and elegant bijective proof of Chung–Feller theorem. We utilize a simple bijection between n-Dyck paths with k flaws and n-Dyck paths with k+1 flaws for k=0,1,…,n-1 to yield this result (Theorem 0.1). | 關聯: | Discrete Mathematics, 308(7), 1328-1329 | 資料類型: | article | DOI: | http://dx.doi.org/http://dx.doi.org/10.1016/j.disc.2007.03.068 |
Appears in Collections: | 期刊論文 |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
1328-1329.pdf | 123.93 kB | Adobe PDF2 | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.