2009 / September Volume 4 No.3
Generalizations of Chung-Feller theorems
Published Date |
2009 / September
|
---|---|
Title | Generalizations of Chung-Feller theorems |
Author | |
Keyword | |
Download | |
Pagination | 299-332 |
Abstract | 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.
|
Received |
2009-04-17
|
Accepted |
2009-07-09
|