The Chung-Feller Theorem For Lattice Path Boundary Pairs

Irving and Rattan gave a formula for counting lattice paths dominated by a cyclically shifting piece 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(eg.the Dyck paths when k = 1).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(k = 0,1,…,n)steps above the line y = x is independent of k,and is therefore the Catalan number 1/n+1(?).In this thesis,we study the number of lattice paths boundary pairs(P,a)with k flaws,where P is a lattice path from(0,0)to(n,m),a is a weak m-part composition of n,and k flaws is meant k horizontal steps of P above the boundary(?)a.We prove bijectively,for a giv-en a,summing these numbers over all cyclic shifts of the boundary(?)a is equal to(?).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.