We refer to lattice positive paths as to paths in the discrete plane constituted by di erent kinds of steps (north-east, east and south-east), starting from the origin and never going under the x-axis. They have been deeply studied both from a combinatorial and an algorithmic point of view. We propose some algorithms for the exhaustive generation of positive paths which are pre xes of Dyck, Motzkin and q-coloured Motzkin paths, according to their length. For each kind of path we de ne a recursive version as well an iterative one, specifying which path follows a given one in the lexicographic order. Furthermore we study the complexity of these algorithms by using the relations between the number of paths of given size and the number of north-east steps appearing in the nal rise.
Copyright c by the paper's authors. Copying permitted for private and academic purposes.
In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18{20 June 2018, published at http://ceur-ws.org
We can establish a total order among the paths in the same class in a very natural way. If p = p1p2:::pn and r = r1r2:::rn are two paths we say that p precedes r if there is an index k > 0 such that pi = ri for i = 1; :::; k 1 and the step pk lies under the step rk (for the at steps of di erent colours we can choose an order whatever, so we have D < F1 < F2 < ::: < Fq < U ). We will de ne some algorithms able to exhaustively generate the paths having the same length according to the above order. 2
Dyck paths have been widely studied, both from a combinatorial and an algorithmic point of view, directly or in connection with the numerous combinatorial structures in bijection with them and enumerated by Catalan numbers. Well-formed parenthesis, binary trees, parallelogram polyominoes, triangulations of a polygon, chords on a circle, pattern avoiding permutations are only a few examples. The book of Stanley [Sta15] presents 214 di erent kinds of objects counted by Catalan numbers and many others enumerated by sequences related to them. In the literature there exist also many papers dealing with exhaustive generation and Gray codes for structures enumerated by Catalan numbers (see for instance [BR98, Rus03, RW08, VW06, Wal98]).
Dyck pre xes correspond to ballot sequences and the number of n-length Dyck pre xes is (sequence A001405 in [S]). From this we can easily obtain that and dn = n n b 2 c d2n = 2d2n 1
These relations have a very simple interpretation. Any odd length path has a strictly positive height, so we can add at its end either a rise or a fall step. As a result from any (2n 1)-length path we obtain two 2n-length di erent paths. The even length paths include also 0-height paths, that is Dyck paths enumerated by Catalan numbers (Cn), and only a rise step can be added at the end of these paths. As a results from the 2n-length paths we obtain 2d2n Cn di erent (2n + 1)-length paths.
In order to exhaustively generate the n-length paths according to the natural order above de ned, we represent them by means of n-length words on the alphabet f0; 1g, by associating 1 to each rise step and 0 to each fall step, and then generate the words in lexicographic order.
The rst n-length word is f irst(n) = (10) n2 if n is even and f irst(n) = (10)b n2 c1 if n is odd. The last one is always 1n. Furthermore we de ne f irst(n) = " when n 0. We denote by h(w) the di erence between the number of 1's and the number of 0's in the word w, that is the height of the corresponding path. Let w = v0, then the following word w0 is v1 and h(w0) = h(w) + 2. If w = v01p then w0 = v10kz where k is the maximum number of 0's that can be added after v1, that is k = minfp; h(w) p + 2g because h(v1) = h(w) p + 2, and z = f irst(p k). Furthermore, h(w0) = h(w) 2p + 2 if p < h(w) p + 2 and h(w0) = h(z) otherwise.
As a result, in order to obtain the successor of a word w it is necessary to scan w from right to left till the rightmost 0 is detected and then modify w from this position to the end as described above. This can be achieved by the procedure next() (described in Algorithm 1 in a Java style). We suppose that a is a global array containing w in the entries 1::n, a[0] = 0 is a ag for recognizing the last word, h is a global variable containing the height of the path represented in a and f inish a global boolean variable whose value becomes true when the procedure recognizes the last sequence. After initializing a with f irst(n), h with h(f irst(n)) and f inish with f alse, the procedure is used into a do-while cycle which stops when f inish becomes true.
In order to evaluate the complexity of the algorithm it is easy to see that the number of elements tested and modi ed for generating the next sequence from w = v01p is equal to p + 1. Let tn be the total number of nal 1's in all the n-length words (that is the number of 1's which take part in the 1p su xes). The following relation Algorithm 1 procedure next for Dyck pre xes void n e x t ( ) f i n t j , p=0; while ( a [ n p]==1) p=p+1; i f ( p==n ) f i n i s h=true ; e l s e f a [ n p ] = 1 ; h=h p+2; j=n p+1; while ( h>0 && j<=n ) f a [ j ] = 0 ; j=j +1; h=h 1;g while ( j <n ) f a [ j ] = 1 ; a [ j +1]=0; j=j +2;g i f ( j==n ) f a [ n ] = 1 ; h=h+1;g g holds tn = tn 1 + dn 1 because an element 1 can be added at the end of any (n 1)-length word and the nal 1's are still nal 1's. So the total number of operations necessary to generate all the n-length words is tn + dn and the average number for each word is avgn = tn + dn = tn + 1
dn dn So the quantity rn = dtnn must be evaluated.
r2n = t2n = t2n 1 + d2n 1 = 1 d2n 2d2n 1 2
(r2n 1 + 1) r2n+1 = t2n+1 = t22nnn+++11 dd22nn = t2n 1 + d2n 1 + 2d2n 1 = d2n+1 2 2nn++11 d2n 1
n + 1 2(2n + 1) (r2n 1 + 3)
If r2n 1 < 2 then for n > 1.
n + 1 r2n+1 < 2(2n + 1) 5 = 5n + 5 4n + 2 < 2 Since r1 < 2 we can conclude that rn < 2 for n 1 and avgn < 3, so the algorithm has the CAT property.
A recursive version can also be de ned. The array a and h have the same meaning and do not necessitate any initialization. The array a is lled from left to right: the rst parameter of the procedure dyckR is the next position j to be de ned and the second parameter indicates the height of the Dyck pre x represented in the rst j 1 entries of a. If the value of the rst parameter in a call is greater than n, a new pre x is contained in a and it can be displayed (or elaborated). Otherwise the pre x is not yet completed: a fall step is added (a[j] = 0) and a recursive call with parameters j + 1 and h 1 is generated only if h > 0, while a rise step can always be added (a[j] = 1) followed by a recursive call with parameters j + 1 and h + 1. The initial call is dyckR(1; 0).
In order to evaluate the complexity we can consider the total number of recursive calls made for generating all the n-length words, because any call makes a constant number of operations. We can slightly modify the procedure in such a way that any call outputs a new word or generate exactly two recursive calls. In this way the recursion tree is a binary tree with dn leafs and dn 1 internal nodes and, as a result, we have that the average number of calls for a word is less than 2 and the algorithm is CAT. When we add a fall step, the height of the pre x decreases by 1. So if the height was 1 it becomes 0 and at a successive call only a rise step can be added. So when the height is equal to 1 and we add a fall step in position j, if j < n, we add also a rise step in position j + 1 and make a call with parameters j + 2 and 1. As a result, the only calls with h = 0 are those with j = n and in the recursion tree any internal node has exactly two sons. In this case the initial call should Algorithm 2 recursive procedure for Dyck pre xes void dyckR ( i n t j , i n t h ) f i f ( j >n ) f p r i n t ( a ) ; g e l s e f i f ( h>0) f a [ j ] = 0 ; dyckR ( j +1 , h 1);g a [ j ] = 1 ; dyckR ( j +1 , h +1); Algorithm 3 improved recursive procedure for Dyck pre xes void dyckRC ( i n t j , i n t h ) f i f ( j >n ) f p r i n t ( a ) ; g e l s e f a [ j ] = 0 ; i f ( h==1 && j <n ) f a [ j +1]=1; dyckRC ( j +2 , 1 ) ; g e l s e dyckRC ( j +1 , h 1); a [ j ] = 1 ; dyckRC ( j +1 , h +1); be dyckRC(2; 1), after initializing a[1] = 1. 3
Motzkin numbers [Aig98, DS77] enumerate many combinatorial structures which are very close to those enumerated by Catalan numbers [Sta15]. Motzkin pre xes have been deeply studied mainly due to their relation with directed animals and percolation [BPS94, GV88]. They are enumerated by sequence A005773 in [S]. There is no closed formula for the number mn of n-length Motzkin pre xes, but for our sakes the recurrence relation (18) [BPS91]: with the conditions m0 = 1 and m1 = 2, is su cient to state that mn = 2mn 1 + 3 n 1 n + 1
mn 2; mn > 2mn 1:
In order to exhaustively generate the n-length Motzkin pre xes we represent them by means of n-length words on the alphabet f0; 1; 2g, by associating 2 to each rise step, 1 to each at step and 0 to each fall step. In this way the natural order for the paths de ned in the introduction corresponds to the lexicographic order on the words.
The rst n-length word is 1n and the last one is 2n. We denote by h(w) the height of the path coded by w, that is the di erence between the number of 2's and the number of 0's in the word w.
Let w = v0 (w = v1), then the following word w0 is v1 (w0 = v2) and h(w0) = h(w) + 1. If w = v02p then w0 = v10k1p k where k is the maximum number of 0's that can be added after v1, that is k = minfp; h(w) p+1g because h(v1) = h(w) p + 1. Furthermore, h(w0) = h(w) p + 1 k. In an analogous way, if w = v12p then w0 = v20k1p k where k is the maximum number of 0's that can be added after v2, that is k = minfp; h(w) p+1g because h(v2) = h(w) p + 1. In this case too, h(w0) = h(w) p + 1 k.
As a result, it is necessary to scan a word w from right to left till the rightmost element di erent from 2 is detected and then modify w from this position to the end as described above, in order to obtain its successor. This can be achieved by the procedure next() (described in Algorithm 4 in a Java style). We suppose that a is a global array containing w in the entries 1::n, a[0] = 0 is useful for recognizing the last word, h is a global variable containing the height of the path represented in a and f inish a global boolean variable whose value becomes true when the procedure recognizes the last sequence. After initializing a with 1n, h with 0 and f inish with f alse, the procedure is used into a do-while cycle which stops when f inish becomes true. Algorithm 4 procedure next for Motzkin pre xes void n e x t ( ) f i n t j , p=0; while ( a [ n p]==2) p=p+1; i f ( p==n ) f i n i s h =true ; e l s e f a [ n p]= a [ n p ] + 1 ; h=h p+1; j=n p+1; while ( h>0 && j<=n ) f a [ j ] = 0 ; h=h 1; j=j +1;g while ( j<=n ) f a [ j ] = 1 ; j=j +1;g g g
In order to evaluate the complexity of the algorithm we remark that the number of elements tested and modi ed for generating the next sequence from w = v02p or w = v12p is equal to p + 1. Let tn be the total number of nal 2's in all the n-length words (that is the number of 2's which take part in the 2p su xes). The following relation holds tn = tn 1 + mn 1 because an element 2 can be added at the end of any (n 1)-length word and the nal 2's are still nal 2's. So the total number of operations necessary to generate all the n-length words is tn + mn and the average number for each word is
It is easy to verify that tn < mn. This is true for n = 1, and if we assume that tk < mk for k obtain n 1, we avgn = tn + mn
mn tn = tn 1 + mn 1 < 2mn 1 < mn: avgn = tn + mn < mn mn + mn = 2: mn As a result So this algorithm too has the CAT property.
A recursive version can be de ned in this case too. The array a and h have the same meaning and do not necessitate any initialization. The array a is lled from left to right: the rst parameter of the procedure motzR is the next position j to be de ned and the second parameter indicates the height of the Motzkin pre x represented in the rst j 1 entries of a. If the value of the rst parameter in a call is greater than n, a new pre x is contained in a and it can be displayed (or elaborated). Otherwise the pre x is not yet completed: a fall step is added (a[j] = 0) and a recursive call with parameters j + 1 and h 1 is generated only if h > 0, while a at and a rise step can always be added (a[j] = 1 and a[j] = 2) followed by a recursive call with parameters j + 1 and h for the at step and parameters j +1 and h+1 for the rise step, respectively. The initial call is motzR(1; 0).
In order to evaluate the complexity we can consider the total number of recursive calls made for generating all the n-length words, because any call makes a constant number of operations. We remark that any call outputs a new word or generate at least two recursive calls. The recursion tree is a tree with mn leafs and a number of internal nodes less than mn 1 and, as a result, the average number of calls for a word is less than 2 and the algorithm is CAT. Algorithm 5 recursive procedure for Motzkin pre xes
q-coloured Motzkin paths [BDPP95] are a natural generalization of Motzkin paths obtained by allowing q di erent colours be used for at steps. When q = 2, bicoloured Motzkin paths are enumerated by Catalan numbers, while their pre xes are counted by the binomial coe cients dn = 2n+1 (sequence A001700 in [S]). n+1
The discussion relative to Motzkin pre xes can be easily extended to the pre xes of q-coloured Motzkin paths. They can be represented by words on the alphabet q = f0; 1; :::; q; q + 1g where q + 1 corresponds to a rise step, 0 to a fall step and 1, 2 ,..., q to the di erent at steps. The rst n-length word is 1n and the last one (q + 1)n. If w = vx(q + 1)p, where x 2 q and x < q + 1, then the successive word is w0 = vx00k1p k, where x0 = x + 1 and k is the maximum number of 0's that can be added after vx0. We have that h(vx0) = h(vx) = h(w) p if 0 < x < q + 1, because we only change the colour of a at step, and h(vx0) = h(vx) + 1 = h(w) p + 1 otherwise, because we transform a fall step in a at step or a at step in a rise step. As a result, k = minfp; h(vx0)g.
In order to obtain w0 it is again necessary to scan w from right to left till the rightmost element di erent from q + 1 is detected and then modify w starting from this position as described above. This is achieved by the procedure next() (Algorithm 6). The variables, their meaning and initialization and the use context of the procedure are the same as for Motzkin pre xes.
Algorithm 6 procedure next for q-coloured Motzkin pre xes void n e x t ( ) f i n t j , p=0; while ( a [ n p]==q+1) p=p+1; i f ( p==n ) f i n i s h=true ; e l s e f a [ n p]= a [ n p ] + 1 ; h=h p ; i f ( a [ n p ] = = 1 j j a [ n p]==q+1) h=h+1; j=n p+1; while ( h>0 && j<=n ) f a [ j ] = 0 ; h=h 1; j=j +1;g while ( j<=n ) f a [ j ] = 1 ; j=j +1;g g g
As far as the complexity of the algorithm is concerned, we remark that the number of elements tested and modi ed for generating the next sequence from w = vx2p, where x < q + 1, is equal to p + 1. Let cn;q be the number of n-length q-coloured Motzkin pre xes. We have that cn;q > (q + 1) cn 1;q because a rise or any at step can always be added to an (n 1)-length q-coloured pre x.
The total number tn;q of nal (q +1)'s in all the n-length words again satis es the relation tn;q = tn 1;q +cn 1;q because an element (q + 1) can be added at the end of any (n 1)-length word and the nal (q + 1)'s are still nal (q + 1)'s. So the total number of operations necessary to generate all the n-length words is tn;q + cn;q.
In this case too, we can verify that tn;q < cn;q. This is true for n = 1, as a matter of fact t1;q = 1 and c1;q = q + 1. By assuming that tk;q < ck;q for k n 1, we obtain tn;q = tn 1;q + cn 1;q < 2cn 1;q < cn;q: As a result the average number of elements tested and modi ed in to generate each word is and this algorithm too has the CAT property.
We can also de ne a recursive procedure with the same parameters used for Motzkin pre xes. This procedure (Algorithm 7) adds in position j, corresponding to the rst parameter, a fall step (if the height h of the prex so long de ned is positive), a at step of any colour, and a rise step. Obviously the recursion stops when j > n. Algorithm 7 recursive procedure for q-coloured Motzkin pre xes void qmotzR ( i n t j , i n t h ) f i n t i ; i f ( j >n ) f p r i n t ( a ) ; g e l s e f i f ( h>0) f a [ j ] = 0 ; qmotzR ( j +1 , h 1 ) ; g f o r ( i =1; i <=q ; i=i +1) f a [ j ]= i ; qmotzR ( j +1 , h ) ; g a [ j ]=q +1; qmotzR ( j +1 , h + 1 ) ; g g
Any call of such procedure produces a new sequence or generate at least q + 1 recursive calls. As a result this version too has the CAT property. 5
Recently binary words avoiding one or more patterns [BMPP12] have been employed in order to construct sets of words constituting a non-overlapping code [Bla15], in particular Dyck words and Motzkin words were used in [BPP12] and [BBPPS16]. Their exhaustive generation and Gray code were tackled in [BBPSV14, BBPSV15, BBPV15, BBPV17]. It would be interesting to establish similar procedures for pre xes of words avoiding those patterns.
Acknowledgements
This work was partially supported by the GNCS 2018 project \Proprieta combinatorie e rilevamento di pattern in strutture discrete lineari e bidimensionali". [Aig98] M. Aigner. Motzkin numbers. European Journal of Combinatorics, 19:663-675, 1998. [AS95] L. Alonso and R. Schott. Random generation of trees - random generators in computer science. Kluwer, 1995. [BBHT17] A. Bacher, O. Bodini, H.-K. Hwang and T.-H. Tsai. Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation. ACM Transactions on Algorithms, 13:Art. 24, 43 pp., 2017. [BBJ17] A. Bacher, O. Bodini and A. Jacquot. E cient random sampling of binary and unary-binary trees via holonomic equations. Theoretical Computer Science, 695:42{53, 2017. [BBPPS16] E. Barcucci, S. Bilotta, E. Pergola, R. Pinzani and J. Succi. Cross-bi x-free sets generation via
Motzkin paths. RAIRO - Theoretical Informatics and Applications, 50:81{91, 2016. [BPS91] E. Barcucci, R. Pinzani and R. Sprugnoli. The Motzkin family. Pure Mathematics and Applications, 2:249{279, 1991. [S] N. J. A. Sloane. The on-line encyclopedia of integer sequences. At http://oeis.org. [Sta15] R. P. Stanley. Catalan numbers. Cambridge University Press, 2015.