Generalizations of Chung-Feller theorems
by Jun Ma   Yeong-Nan Yeh  

Vol. 4 No. 3 (2009) P.299~P.332


In this paper, we develop a method to find Chung-Feller extensions for three kinds of different rooted lattice paths and prove Chung-Feller theorems for such lattice paths. In particular, we compute a generating function $S(z)$ of a sequence formed by rooted lattice paths. We give combinatorial interpretations to the function of Chung-Feller type $\frac {S(z) - yS(yz)}{1-y}$ for the generating function $S(z)$. Using our method, we first prove Chung-Feller theorems of up-down type for three kinds of rooted lattice paths. Our results are generalizations of the classical Chung-Feller theorem of up-down type for Dyck paths. We also find Motzkin paths have Chung-Feller properties of up-down type. Then we prove Chung-Feller theorems of left-right type for two among three kinds of rooted lattice paths. Chung-Feller theorem of left-right type for Motzkin paths is a special case of our theorems. We also show that Dyck paths have Chung-Feller phenomenons of left-right type. By the main theorems in this paper, many new Chung-Feller theorems for rooted lattice paths are derived.

Chung-Feller Theorem, Dyck path, Motzkin path, Rooted lattice path



Received: 2009-04-17
Revised :
Accepted: 2009-07-09

Download Full Content