2009 / September

Generalizations of Chung-Feller theorems

Jun Ma, Yeong-Nan Yeh

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

Download PDF

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

2009-04-17

2009-07-09