1. NCCU Academic Hub
  2. 學術產出
  3. 理學院
  4. 期刊論文
  5. Item

學術產出-期刊論文

文章檢視/開啟

書目匯出

Google ScholarTM

政大圖書館

引文資訊

題名 The Chung-Feller Theorem Revisited
作者 李陽明
Chen, Young-Ming
貢獻者 應數系
關鍵詞 Dyck paths; Catalan numbers
日期 2008-04
上傳時間 24-十二月-2008 13:39:20 (UTC+8)
摘要 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
dc.contributor 應數系-
dc.creator (作者) 李陽明zh_TW
dc.creator (作者) Chen, Young-Ming-
dc.date (日期) 2008-04en_US
dc.date.accessioned 24-十二月-2008 13:39:20 (UTC+8)-
dc.date.available 24-十二月-2008 13:39:20 (UTC+8)-
dc.date.issued (上傳時間) 24-十二月-2008 13:39:20 (UTC+8)-
dc.identifier.uri (URI) https://nccur.lib.nccu.edu.tw/handle/140.119/18846-
dc.description.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 enen_US
dc.language en-USen_US
dc.language.iso en_US-
dc.relation (關聯) Discrete Mathematics, 308(7), 1328-1329en_US
dc.subject (關鍵詞) Dyck paths; Catalan numbers-
dc.title (題名) The Chung-Feller Theorem Revisiteden_US
dc.type (資料類型) articleen
dc.identifier.doi (DOI) 10.1016/j.disc.2007.03.068en_US
dc.doi.uri (DOI) http://dx.doi.org/http://dx.doi.org/10.1016/j.disc.2007.03.068en_US