A Chung-Feller theorem for lattice paths with respect to cyclically shifting boundaries

作者：Guo, Victor J. W.^*; Wang, Xiao-Xin

来源：Journal of Algebraic Combinatorics, 2019, 50(2): 119-126.

DOI：10.1007/s10801-018-0845-z

• Chung-Feller theorem
• Lattice paths
• Piecewise linear boundary
• Catalan numbers
• Double ascent

Irving and Rattan gave a formula for counting lattice paths dominated by a cyclically shifting piecewise linear boundary of varying slope. Their main result may be considered as a deep extension of well-known enumerative formulas concerning lattice paths from (0, 0) to (kn, n) lying under the line x=ky). On the other hand, the classical Chung-Feller theorem tells us that the number of lattice paths from (0, 0) to (n, n) with exactly 2k steps above the line x=y is independent of k and is therefore the Catalan number 1n+1. In this paper, we study the number of lattice path boundary pairs (P,a) with k flaws, where P is a lattice path from (0, 0) to (n, m), is a weak m-part composition of n, and a flaw is a horizontal step of P above the boundary partial differential. We prove bijectively, for a given a, that summing these numbers over all cyclic shifts of the boundary partial differential. That is, we generalize the Irving-Rattan formula to a Chung-Feller-type theorem. We also give a refinement of this result by taking the number of double ascents of lattice paths into account.

• 出版日期2019-9
• 单位淮阴师范学院; 华东师范大学