中央研究院 数學研咒所 Chung- Feller theorem The number of Dyck path of semi-length n with m up-steps under x-axis is the n-th Catalan number and independent on m K.L. Chung W. Feller, On fluctuations in-coin tossing Proc. Natl. Acad. Sci. USA 35(1949) 605-608 第16页
第16页 K.L. Chung, W. Feller, On fluctuations in-coin tossing, Proc. Natl. Acad. Sci. USA 35 (1949) 605-608 Chung-Feller theorem: The number of Dyck path of semi-length n with m up-steps under x-axis is the n-th Catalan number and independent on m
中央研究院 数學研咒所 Uniform partition(An uniform partition for Dyck paths The number of up- 平个 steps(1, 1) lying below x-axis ⌒果圆 第17页
第17页 Uniform partition (An uniform partition for Dyck paths) The number of upsteps (1,1) lying below x-axis
中央研究院 数學研咒所 Let C(y)=∑∑cnk="y n≥0k=0 Substituti ng Cn. with c, by Chung -Feller the orem, We have C(:)=∑∑="yk=yC( (yz)-C(=) n≥0k=0 y 第18页
第18页 = = − − = = − = 0 0 , 0 0 , 1 ( ) ( ) ( ) We have Substituti ng with by Chung Feller the orem, ( ) Let n n k n k n n k n n n k n k n k y yC yz C z C y,z c z y c c C y,z c z y
中央研究院 数學研咒所 Lifted Motzkin paths A lifted n-Motizkin path is a lattice path from(0,0) to(n+l, 1) in the plane integer lattice ZXZ consisting of up-step(1, 1), level-step(1, 0)and down-step (I D), which never passes below the line 第19页
第19页 Lifted Motzkin paths • A lifted n-Motizkin path is a lattice path from (0,0) to (n+1,1) in the plane integer lattice Z×Z consisting of up-step (1,1), level-step (1,0) and down-step (1,-1), which never passes below the line y=1 except (0,0)
中央研究院 数學研咒所 Free Lifted Motzkin paths A free lifted n-Motizkin path is a lattice path from (0,0) to(n+l, 1 in the plane integer lattice ZXz consisting up-step(1, 1), level-step(1, 0)and down-step (1, -1). 第20页
第20页 Free Lifted Motzkin paths • A free lifted n-Motizkin path is a lattice path from (0,0) to (n+1,1) in the plane integer lattice Z×Z consisting of up-step (1,1), level-step (1,0) and down-step (1,-1)