Introduction

Random and exhaustive generation has a fundamental role in the study of parameters characterizing different classes of combinatorial objects as well as for testing the algorithms operating on them. Many classes of paths in the plane and other combinatorial objects have been studied from the point of view of random generation [AS95, BBHT17, BBJ17, BPS95, DFLS04]. In their books [Rus03,Knu08], F. Ruskey and D. Knuth propose many algorithms for the exhaustive generation of several combinatorial objects according to their size. These algorithms can be classified into two main types: the recursive algorithms and those based on the use of a (next) procedure able to generate the successor of any object according to a fixed (usually lexicographic) order. In this paper we present some algorithms of both the above mentioned kinds for the exhaustive generation of three classes of lattice paths in the discrete plane: prefixes of Dyck, Motzkin and q-coloured Motzkin paths, also called Dyck, Motzkin and q-coloured Motzkin positive paths. Furthermore we show that the proposed algorithms have the CAT (Constant Amortized Time) property [Rus03], that is the average number of operations needed to generate any object of a given size does not depend on the size itself but it is limited by a constant.

We consider three kinds of steps U = (1, 1), D = (1, −1), F = (1, 0), called rise, fall and flat steps. An n-length Dyck (Motzkin) path is a path in Z 2 made up of U and D steps (U , D and F steps) starting from (0, 0), ending in (n, 0) and never going under the x-axis. If the flat steps can be coloured in q ≥ 2 different ways (that is we have q different flat steps F 1 , F 2 , ..., F q ) we obtain q-coloured Motzkin paths (called bicoloured when q = 2). Positive Dyck (Motzkin, q-coloured Motzkin) paths are prefixes of Dyck (Motzkin, q-coloured Motzkin) paths, that is paths having the above mentioned properties but ending at a point (n, h), where h ≥ 0 is called the height of the path.

We can establish a total order among the paths in the same class in a very natural way. If p = p 1 p 2 ...p n and r = r 1 r 2 ...r n are two paths we say that p precedes r if there is an index k > 0 such that p i = r i for i = 1, ..., k − 1 and the step p k lies under the step r k (for the flat steps of different colours we can choose an order whatever, so we have D < F 1 < F 2 < ... < F q < U ). We will define some algorithms able to exhaustively generate the paths having the same length according to the above order.

Dyck prefixes

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 different 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 prefixes correspond to ballot sequences and the number of n-length Dyck prefixes is

d n = n n 2

(sequence A001405 in [S]). From this we can easily obtain that

d 2n = 2d 2n−1

and

d 2n+1 = 2n + 1 n + 1 d 2n < 2d 2n

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 different paths. The even length paths include also 0-height paths, that is Dyck paths enumerated by Catalan numbers (C n ), and only a rise step can be added at the end of these paths. As a results from the 2n-length paths we obtain 2d 2n − C n different (2n + 1)-length paths.

In order to exhaustively generate the n-length paths according to the natural order above defined, we represent them by means of n-length words on the alphabet {0, 1}, by associating 1 to each rise step and 0 to each fall step, and then generate the words in lexicographic order.

The first n-length word is f irst(n) = (10) n 2 if n is even and f irst(n) = (10) n 2 1 if n is odd. The last one is always 1 n . Furthermore we define f irst(n) = ε when n ≤ 0. We denote by h(w) the difference 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 w is v1 and h(w ) = h(w) + 2. If w = v01 p then w = v10 k z where k is the maximum number of 0's that can be added after v1, that is

k = min{p, h(w) − p + 2} because h(v1) = h(w) − p + 2, and z = f irst(p − k). Furthermore, h(w ) = h(w) − 2p + 2 if p < h(w) − p + 2 and h(w ) = 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 flag 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 modified for generating the next sequence from w = v01 p is equal to p + 1. Let t n be the total number of final 1's in all the n-length words (that is the number of 1's which take part in the 1 p suffixes). The following relation Algorithm 1 procedure next for Dyck prefixes

void next ( ) { int 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 { a [ n−p ] = 1 ; h=h−p+2; j=n−p+1; while ( h>0 && j<=n ) { a [ j ] = 0 ; j=j +1; h=h−1;} while ( j <n ) { a [ j ] = 1 ; a [ j +1]=0; j=j +2;} i f ( j==n ) {a [ n ] = 1 ; h=h+1;} } } holds t n = t n−1 + d n−1 because

an element 1 can be added at the end of any (n − 1)-length word and the final 1's are still final 1's. So the total number of operations necessary to generate all the n-length words is t n + d n and the average number for each word is

avg n = t n + d n d n = t n d n + 1

So the quantity r n = tn dn must be evaluated.

r 2n = t 2n d 2n = t 2n−1 + d 2n−1 2d 2n−1 = 1 2 (r 2n−1 + 1) r 2n+1 = t 2n+1 d 2n+1 = t 2n + d 2n 2n+1 n+1 d 2n = t 2n−1 + d 2n−1 + 2d 2n−1 2 2n+1 n+1 d 2n−1 = n + 1 2(2n + 1) (r 2n−1 + 3) If r 2n−1 < 2 then r 2n+1 < n + 1 2(2n + 1) 5 = 5n + 5 4n + 2 < 2

for n > 1.

Since r 1 < 2 we can conclude that r n < 2 for n ≥ 1 and avg n < 3, so the algorithm has the CAT property.

A recursive version can also be defined. The array a and h have the same meaning and do not necessitate any initialization. The array a is filled from left to right: the first parameter of the procedure dyckR is the next position j to be defined and the second parameter indicates the height of the Dyck prefix represented in the first j − 1 entries of a. If the value of the first parameter in a call is greater than n, a new prefix is contained in a and it can be displayed (or elaborated). Otherwise the prefix 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 d n leafs and d n − 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 prefix 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 prefixes void dyckR ( int j , int h ) { i f ( j >n ) { p r i n t ( a ) ; } e l s e { i f ( h>0) { a [ j ] = 0 ; dyckR ( j +1, h −1);} a [ j ] = 1 ; dyckR ( j +1, h +1); } } Algorithm 3 improved recursive procedure for Dyck prefixes void dyckRC ( int j , int h ) { i f ( j >n ) { p r i n t ( a ) ; } e l s e { a [ j ] = 0 ; i f ( h==1 && j <n ) { a [ j +1]=1; dyckRC ( j +2, 1 ) ; } 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.

Motzkin prefixes

Motzkin numbers [Aig98, DS77] enumerate many combinatorial structures which are very close to those enumerated by Catalan numbers [Sta15]. Motzkin prefixes 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 m n of n-length Motzkin prefixes, but for our sakes the recurrence relation (18) [BPS91]:

m n = 2m n−1 + 3 n − 1 n + 1 m n−2 ,

with the conditions m 0 = 1 and m 1 = 2, is sufficient to state that

m n > 2m n−1 .

In order to exhaustively generate the n-length Motzkin prefixes we represent them by means of n-length words on the alphabet {0, 1, 2}, by associating 2 to each rise step, 1 to each flat step and 0 to each fall step. In this way the natural order for the paths defined in the introduction corresponds to the lexicographic order on the words.

The first n-length word is 1 n and the last one is 2 n . We denote by h(w) the height of the path coded by w, that is the difference 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 w is v1 (w = v2) and h(w ) = h(w) + 1. If w = v02 p then w = v10 k 1 p−k where k is the maximum number of 0's that can be added after v1, that is k = min{p, h(w)−p+1} because h(v1) = h(w) − p + 1. Furthermore, h(w ) = h(w) − p + 1 − k. In an analogous way, if w = v12 p then w = v20 k 1 p−k where k is the maximum number of 0's that can be added after v2, that is k = min{p, h(w)−p+1} because h(v2) = h(w) − p + 1. In this case too, h(w

) = h(w) − p + 1 − k.

As a result, it is necessary to scan a word w from right to left till the rightmost element different 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 1 n , 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. In order to evaluate the complexity of the algorithm we remark that the number of elements tested and modified for generating the next sequence from w = v02 p or w = v12 p is equal to p + 1. Let t n be the total number of final 2's in all the n-length words (that is the number of 2's which take part in the 2 p suffixes). The following relation holds t n = t n−1 + m n−1 because an element 2 can be added at the end of any (n − 1)-length word and the final 2's are still final 2's. So the total number of operations necessary to generate all the n-length words is t n + m n and the average number for each word is

avg n = t n + m n m n

It is easy to verify that t n < m n . This is true for n = 1, and if we assume that

t k < m k for k ≤ n − 1, we obtain t n = t n−1 + m n−1 < 2m n−1 < m n .

As a result

avg n = t n + m n m n < m n + m n m n = 2.

So this algorithm too has the CAT property.

A recursive version can be defined in this case too. The array a and h have the same meaning and do not necessitate any initialization. The array a is filled from left to right: the first parameter of the procedure motzR is the next position j to be defined and the second parameter indicates the height of the Motzkin prefix represented in the first j − 1 entries of a. If the value of the first parameter in a call is greater than n, a new prefix is contained in a and it can be displayed (or elaborated). Otherwise the prefix 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 flat 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 flat 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 m n leafs and a number of internal nodes less than m n − 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 prefixes void motzR ( int j , int h ) { i f ( j >n ) { p r i n t ( a ) ; } e l s e { i f ( h>0) {a [ j ] = 0 ; motzR ( j +1, h −1);} a [ j ] = 1 ; motzR ( j +1, h ) ; a [ j ] = 2 ; motzR ( j +1, h +1); } } 4 q-coloured Motzkin prefixes q-coloured Motzkin paths [BDPP95] are a natural generalization of Motzkin paths obtained by allowing q different colours be used for flat steps. When q = 2, bicoloured Motzkin paths are enumerated by Catalan numbers, while their prefixes are counted by the binomial coefficients d n = 2n+1 n+1 (sequence A001700 in [S]). The discussion relative to Motzkin prefixes can be easily extended to the prefixes of q-coloured Motzkin paths. They can be represented by words on the alphabet Σ q = {0, 1, ..., q, q + 1} where q + 1 corresponds to a rise step, 0 to a fall step and 1, 2 ,..., q to the different flat steps. The first n-length word is 1 n and the last one (q + 1) n . If w = vx(q + 1) p , where x ∈ Σ q and x < q + 1, then the successive word is w = vx 0 k 1 p−k , where x = x + 1 and k is the maximum number of 0's that can be added after vx . We have that h(vx ) = h(vx) = h(w) − p if 0 < x < q + 1, because we only change the colour of a flat step, and h(vx ) = h(vx) + 1 = h(w) − p + 1 otherwise, because we transform a fall step in a flat step or a flat step in a rise step. As a result, k = min{p, h(vx )}.

In order to obtain w it is again necessary to scan w from right to left till the rightmost element different 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 prefixes. As far as the complexity of the algorithm is concerned, we remark that the number of elements tested and modified for generating the next sequence from w = vx2 p , where x < q + 1, is equal to p + 1. Let c n,q be the number of n-length q-coloured Motzkin prefixes. We have that c n,q > (q + 1) • c n−1,q because a rise or any flat step can always be added to an (n − 1)-length q-coloured prefix.

The total number t n,q of final (q +1)'s in all the n-length words again satisfies the relation t n,q = t n−1,q +c n−1,q because an element (q + 1) can be added at the end of any (n − 1)-length word and the final (q + 1)'s are still final (q + 1)'s. So the total number of operations necessary to generate all the n-length words is t n,q + c n,q .

In this case too, we can verify that t n,q < c n,q . This is true for n = 1, as a matter of fact t 1,q = 1 and c 1,q = q + 1. By assuming that t k,q < c k,q for k ≤ n − 1, we obtain t n,q = t n−1,q + c n−1,q < 2c n−1,q < c n,q .

As a result the average number of elements tested and modified in to generate each word is avg n = t n,q + c n,q c n,q < c n,q + c n,q c n,q = 2 and this algorithm too has the CAT property.

We can also define a recursive procedure with the same parameters used for Motzkin prefixes. This procedure (Algorithm 7) adds in position j, corresponding to the first parameter, a fall step (if the height h of the prefix so long defined is positive), a flat step of any colour, and a rise step. Obviously the recursion stops when j > n.

Algorithm 7 recursive procedure for q-coloured Motzkin prefixes void qmotzR ( int j , int h ) { int i ; i f ( j >n ) { p r i n t ( a ) ; } e l s e { i f ( h>0) { a [ j ] = 0 ; qmotzR ( j +1, h −1);} f o r ( i =1; i<=q ; i=i +1) { a [ j ]= i ; qmotzR ( j +1, h ) ; } a [ j ]=q+1; qmotzR ( j +1, h +1); } } 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.

Further developments

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 prefixes of words avoiding those patterns.