The Chung-Feller Theorem Revisited

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).