Please use this identifier to cite or link to this item:

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 連結:
Appears in Collections:[應用數學系] 期刊論文

Files in This Item:

File Description SizeFormat
1328-1329.pdf123KbAdobe PDF985View/Open

All items in 學術集成 are protected by copyright, with all rights reserved.

社群 sharing