Article View/Open
Publication Export
Related Publications in TAIR
- > Simple Record
- > Full Record
| Field |
Value |
| Title: | The Chung-Feller Theorem Revisited |
| Authors: | 李陽明
Chen, Young-Ming |
| Contributors: | 應數系 |
| Keywords: | Dyck paths; Catalan numbers |
| Date: | 2008-04 |
| Issue Date: | 2008-12-24 13:39:20 (UTC+8) |
| Abstract: | 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). |
| Relation: | Discrete Mathematics, 308(7), 1328-1329 |
| Data Type: | article |
| DOI: | http://dx.doi.org/http://dx.doi.org/10.1016/j.disc.2007.03.068 |
| DCField |
Value |
Language |
| dc.contributor (Contributor) | 應數系 | - |
| dc.creator (Authors) | 李陽明 | zh_TW |
| dc.creator (Authors) | Chen, Young-Ming | - |
| dc.date (Date) | 2008-04 | en_US |
| dc.date.accessioned | 2008-12-24 13:39:20 (UTC+8) | - |
| dc.date.available | 2008-12-24 13:39:20 (UTC+8) | - |
| dc.date.issued (Issue Date) | 2008-12-24 13:39:20 (UTC+8) | - |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/18846 | - |
| dc.description.abstract (Abstract) | 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). | - |
| dc.format | application/ | en_US |
| dc.language (Language) | en | en_US |
| dc.language (Language) | en-US | en_US |
| dc.language.iso | en_US | - |
| dc.relation (Relation) | Discrete Mathematics, 308(7), 1328-1329 | en_US |
| dc.subject (Keywords) | Dyck paths; Catalan numbers | - |
| dc.title (Title) | The Chung-Feller Theorem Revisited | en_US |
| dc.type (Data Type) | article | en |
| dc.identifier.doi (DOI) | 10.1016/j.disc.2007.03.068 | en_US |
| dc.doi.uri | http://dx.doi.org/http://dx.doi.org/10.1016/j.disc.2007.03.068 | en_US |
(1009)