Chung-Feller Property in View of Generating Functions

Abstract

The classical Chung-Feller Theorem offers an elegant perspective for enumerating the Catalan number $c_n= \frac{1}{n+1}\binom{2n}{n}$. One of the various proofs is by the uniform-partition method. The method shows that the set of the free Dyck $n$-paths, which have $\binom{2n}{n}$ in total, is uniformly partitioned into $n+1$ blocks, and the ordinary Dyck $n$-paths form one of these blocks; therefore the cardinality of each block is $\frac{1}{n+1}\binom{2n}{n}$. In this article, we study the Chung-Feller property: a sup-structure set can be uniformly partitioned such that one of the partition blocks is (isomorphic to) a well-known structure set. The previous works about the uniform-partition method used bijections, but here we apply generating functions as a new approach. By claiming a functional equation involving the generating functions of sup- and sub-structure sets, we re-prove two known results about Chung-Feller property, and explore several new examples including the ones for the large and the little Schröder paths. Especially for the Schröder paths, we are led by the new approach straightforwardly to consider "weighted" free Schröder paths as sup-structures. The weighted structures are not obvious via bijections or other methods.