Chung-Feller Theorems on the Generalized Dyck -Paths and the Bicolored Expansion

Sen-Peng Eu , Tung-Shan Fu and Yeong-Nan Yeh

Department of Applied Mathematics, National University of Kaohsiung,

Kaohsiung, Taiwan

Faculty, National Pingtung Institute of Commerce, Pingtung, Taiwan

Institute of Mathematics, Academia Sinica, Taipei, Taiwan

speu@nuk.edu.tw tsfu@npic.edu.tw mayeh@ccvax.sinica.edu.tw

Abstract. Full Text PDF

In this paper we first consider the Chung-Feller theorems on the generalized Dyck -paths. By a generalized Dyck -path of length we mean a lattice path in the plane from to with the steps and the steps, never passing below the line . Denote the number of generalized -Dyck paths of length as and it is known that the generating function satisfies the functional equation . Also, by a generalized -Dyck path with flaws we allow steps passing below the line . Here a ‘flaw’ indicates a step below the line .

By Taylor expansions on the generating functions we prove that, for any fixed , the number of generalized Dyck -paths with flaws is independent of the number of flaws. This result generalizes the classic Chung-Feller theorem when . Combinatorial proofs, as well as algebraic ones, are also given.

We then introduce the concept of bicoloring expansions of a lattice path on the plane, and investigate why and when the Chung-Feller type theorems arise.