tailieunhanh - Báo cáo toán học: "Counting peaks and valleys in k-colored Motzkin paths"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Counting peaks and valleys in k-colored Motzkin paths. | Counting peaks and valleys in k-colored Motzkin paths A. Sapounakis and P. Tsikouras Department of Informatics University of Piraeus Piraeus GREECE arissap@ pgtsik@ Submitted Oct 6 2004 Accepted Mar 10 2005 Published Mar 18 2005 Mathematics Subject Classifications 05A15 05A19 Abstract This paper deals with the enumeration of fc-colored Motzkin paths with a fixed number of left and right peaks and valleys. Further enumeration results are obtained when peaks and valleys are counted at low and high level. Many well-known results for Dyck paths are obtained as special cases. 1 Introduction A wide range of articles dealing with Dyck and Motzkin paths and related topics appears frequently in the literature . 1 7 9 12 13 14 15 20 . More generally k-colored Motzkin paths 2 17 which have horizontal steps colored by means of k colors are of particular interest and have important applications . 3 4 8 17 for k 2 and 11 17 for k 3 . In this paper several enumeration results for the set M of k-colored Motzkin paths according to various parameters are established with the aid of generating functions. Most of these results are known for k 0 . for Dyck paths while they are new even for k 1 . for Motzkin paths . In section 2 some basic dehnitions and notations referring to the set M and various parameters of it are given. In section 3 using some simple bijections several parameters of M are categorized into classes the elements of which are equidistributed. Then by picking a parameter from each class . the number of left peaks right valleys double rises and peaks the generating function of M is found according to length number of rises and this parameter giving several enumeration results. In section 4 resp. section 5 parameters related to peaks and valleys at low resp. high level are considered. Several well-known results on Dyck paths are generalized to k-colored Motzkin paths. For example it is shown that the parameters number of high peaks and .