Geometric properties of k-coloured Motzkin paths
PANOS TSIKOURAS
Department of Informatics
University of Piraeus
80, Karaoli and Dimitriou Str., 18534
GREECE
Abstract: - In this work, we investigate some enumeration problems related to geometric properties of k-coloured Motzkin paths. Several results on Dyck paths are extended to k-coloured Motzkin paths and some new results are presented.
Key-Words: - Motzkin paths, Motzkin words, k-coloured Motzkin paths, Dyck paths.
1 Introduction
A k-Motzkin path of length n is a lattice path of N2 running from (0,0) to (n,0), that never passes below the x-axis and whose permitted steps are the up diagonal step (1,1), the down diagonal step (1,-1) and the coloured horizontal step (1,0) which is labeled with one out of k colours, k ÎN. These steps are called rise, fall and level step, respectively. It is clear that each k-coloured Motzkin path is coded by a k-coloured Motzkin word Î{a, , b1, b2, …, bk}* so that every rise (resp. fall) corresponds to the letter a (resp. ) and every coloured level step corresponds to some letter of {b1, b2, …, bk}; see Fig.1. In the cases k=0,1 we obtain the well-known Dyck and Motzkin paths, enumerated by the Catalan numbers (n : even) and the Motzkin numbers Mn respectively. It is also known [6] that the number of 2-coloured Motzkin paths of length n is equal to Cn+1.
Finally, it has been proved [9] that the number of 3-coloured Motzkin paths is equal to , which is also the cardinality of the set of all tree-like polyhexes with n+1 hexagons [7], [9]; see Fig. 2.
The enumeration of Dyck paths according to several parameters has been extensively studied [2], [3], [4], [5]. The same subject has been studied in [1], [9] for k-coloured Motzkin paths.
2 Results
In this work, new results in the same direction are presented, referring to parameters related to some geometric properties of k-coloured Motzkin paths.
A peak (resp. valley) of a k-coloured Motzkin path is formed by a rise followed by a fall (resp. by a fall followed by a rise). A left peak (resp. left valley) is formed by a rise (resp. fall) followed by either a level step or a fall (resp. rise). A double rise is formed by two successive rises, whereas a peak is called high peak if the starting point of its rise does not lie on the x-axis.
We count the numbers pδ, vδ lpδ and lvδ of all k-coloured Motzkin paths of length n, with r rises and δ peaks, or valleys, or left peaks or left valleys. More precisely, we have
,
,
,
Other parameters, induced by geometric properties of k-coloured Motzkin paths at a certain level are considered and their relation to the above is shown. Furthermore, appropriate bijections of the set of k-coloured Motzkin paths are constructed in order to show that some parameters are equidistributed. For instance this is shown for the parameters “number of valleys”, “number of double rises” and “number of high peaks” on the set of k-coloured Motzkin paths, extending the analogous result on Dyck paths [2], [8].
Most of the proofs in this work use the generating functions of the set of all k-coloured Motzkin paths according to the relevant parameters.
u = b1 a b1 a a b2 b3 b1 a a a b2 a
Fig. 1: A 3-coloured Motzkin path of length 20 and its corresponding word
u = b1 b3 a b3 a b2 b2 b3 a b2 b1
Fig. 2 : A tree-like polyhex and its corresponding 3-coloured Motzkin path and word
References:
[1] E. Barrucci, A. Del Lungo, E. Pergola and R. Pinzani, A construction for enumerating k-coloured Motzkin paths, Proceedings of the First Annual International Conference on Computing and Combinatorics, Springer, 1995, pp. 254-263.
[2] E. Deutsch, Dyck path enumeration, Discrete Mathematics, Vol. 204, No. 1-3, 1999, pp. 167-202.
[3] E. Deutsch, A bijection on Dyck paths and its consequences, Discrete Mathematics, Vol. 179, No. 1-3, 1998, pp. 253-256.
[4] E. Deutsch, A bijection on Dyck paths and its consequences-Corrig., Discrete Mathematics, Vol. 187, No. 1-3, 1998, p. 297.
[5] E. Deutsch, An involution on Dyck paths and its consequences, Discrete Mathematics, Vol 204, No. 1-3, 1999, pp. 163-166.
[6] E. Deutsch and L. W. Shapiro, A bijection between ordered trees and 2-Motzkin paths, and its many consequences, Discrete Mathematics, Vol. 256, No. 3, 2002, pp. 655-670.
[7] F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proceedings of Edinburgh Mathematical Society, Vol. 17, No. 2, 1970, pp. 1-13.
[8] T. Mansour, Counting peaks at height k in a Dyck path, Journal of Integer Sequences, Vol. 5, No. 1, 2002, Article 02.1.1.
[9] A. Sapounakis and P. Tsikouras, On k-colored Motzkin words, Journal of Integer Sequences, Vol 7, No. 2, 2004, Article 04.2.5.