Font Size: a A A

Refinements Of Two Identities On (n,m)-Dyck Paths

Posted on:2019-02-11Degree:MasterType:Thesis
Country:ChinaCandidate:K YuFull Text:PDF
GTID:2370330566460558Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
For integers n,m with n?1 and 0?m?n,an?n,m?-Dyck path is a lattice path in the integer lattice Z×Z using up steps?0,1?and down steps?1,0?that goes from the origin?0,0?to the point?n,n?and contains exactly m up steps below the line y=x.The classical Chung-Feller theorem says that the total number of?n,m?-Dyck path is independent of m and is equal to the n-th Catalan number Cn=1/?n+1????.For any integer k with 1?k?n,let pn,m,kbe the total number of?n,m?-Dyck paths with k peaks.Ma and Yeh proved that pn,m,k=pn,n-m,n-kfor 0?m?n,and pn,m,k+pn,m,n-k=pn,m+1,k+pn,m+1,n-kfor 1?m?n-2.In this paper we give bijective proofs of these two results.Using our bijections,we also get refined enumeration results on the numbers pn,m,kand pn,m,k+pn,m,n-kaccording to the starting and ending steps.
Keywords/Search Tags:Lattice paths, (n,m)-Dyck paths, Chung-Feller theorem, bijective proof
PDF Full Text Request
Related items