Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Chung-Feller Property in View of Generating Functions. | Chung-Feller Property in View of Generating Functions Shu-Chung Liu Department of Applied Mathematics National Hsinchu University of Education Hsinchu City Taiwan liularry@ Yi Wang t Department of Applied Mathematics Dalian University of Technology Dalian China wangyi@ Yeong-Nan Yeh ỉ Institute of Mathematics Academia Sinica Taipei Taiwan mayeh@ Submitted Aug 16 2009 Accepted Apr 29 2011 Published May 8 2011 Mathematics Subject Classification 05A15 05A18 Abstract The classical Chung-Feller Theorem offers an elegant perspective for enumerating the Catalan number Cn -U 2 . One of the various proofs is by the uniform-n n 1 n partition method. The method shows that the set of the free Dyck n-paths which have 2n in total is uniformly partitioned into n 1 blocks and the ordinary Dyck n-paths form one of these blocks therefore the cardinality of each block is __1 t2nl Tn this xrlìí-lí WI1 UhnniT-Ppllpr a sol n I 1 t n . in tins all ic ie vv e s L utt y L ne e 11 LHi g 1- eiei pp r oper Ly a s u j s L r Lic I u r e se L can be uniformly partitioned such that one of the partition blocks is isomorphic to a well-known structure set. The previous works about the uniform-partition method used bijections but here we apply generating functions as a new approach. By claiming a functional equation involving the generating functions of sup- and sub-structure sets we re-prove two known results about Chung-Feller property and explore several new examples including the ones for the large and the little Schroder paths. Especially for the Schroder paths we are led by the new approach straightforwardly to consider weighted free Schroder paths as sup-structures. The weighted structures are not obvious via bijections or other methods. Partially supported by NSC 98-2115-M-134-005-MY3 tPartially supported by NSFC 11071030 Partially supported by NSC 98-2115-M-001-019-MY3 Corresponding author THE ELECTRONIC JOURNAL OF .
