Jean-Luc Baril
email: barjl@u-bourgogne.fr

Helmut Prodinger
email: hproding@sun.ac.za

Enumeration of Partial Lukasiewicz Paths

Keywords: Asymptotics, Enumeration, Partial Lukasiewicz paths 2020 Mathematics Subject Classification: 05A05, 05A15, 05A15

Lukasiewicz paths are lattice paths in N 2 starting at the origin, ending on the x-axis, and consisting of steps in the set {(1, k), k ≥ -1}. We give bivariate generating functions and exact values for the number of n-length prefixes (resp. suffixes) of these paths ending (resp. starting) at height k ≥ 0 with a given type of step. We make a similar study for paths of bounded height, and we prove that the average height of n-length paths ending at a fixed height behaves as √ πn when n → ∞. Finally, we study prefixes of alternate Lukasiewicz paths, i.e., Lukasiewicz paths that do not contain two consecutive steps in the same direction.

Introduction

A Lukasiewicz path of length n ≥ 0 is a lattice path in N 2 starting at the origin (0, 0), ending on the x-axis, consisting of n steps lying in S = {(1, k), k ≥ -1}. We denote by the empty path, i.e., the path of length zero. These paths constitute a natural generalization of Dyck and Motzkin paths (see [START_REF] Deutsch | Dyck path enumeration[END_REF][START_REF] Donaghey | Motzkin numbers[END_REF]), which are made using steps into the sets {(1, 1), (1, -1)} and {(1, 1), (1, 0), (1, -1)}, respectively. We refer to [START_REF] Baril | Enumeration of Lukasiewicz paths modulo some patterns Discrete Math[END_REF][START_REF] Gessel | Lattice paths and Faber polynomials[END_REF][START_REF] Raney | Functional composition patterns and power series reversion[END_REF][START_REF] Stanley | Enumerative Combinatorics[END_REF][START_REF] Varvak | Lattice path encodings in a combinatorial proof of a differential identity[END_REF][START_REF] Viennot | Une théorie combinatoire des polynômes orthogonaux généraux[END_REF] for some combinatorial studies on Lukasiewicz paths. Let L n , n ≥ 0, be the set of Lukasiewicz paths of length n, and L = n≥0 L n . For convenience, we set D = (1, -1), F = (1, 0), U k = (1, k) for k ≥ 1. See Figure 1 for an illustration of a Lukasiewicz path of length 18. Note that Lukasiewicz paths can be interpreted as an algebraic language of words w ∈ {x 0 , x 1 , x 2 , . . .} such that δ(w) = -1 and δ(w ) ≥ 0 for any proper prefix w of w where δ is the map from {x 0 , x 1 , x 2 , . . .} to Z defined by δ(w 1 w 2 . . . w n ) = n i=1 δ(w i ) with δ(x i ) = i -1 (see [START_REF] Lothaire | Combinatorics on Words[END_REF][START_REF] Schützenberger | Le théorème de Lagrange selon G. N. Raney[END_REF]). Any non-empty Lukasiewicz path L ∈ L can be decomposed (see [START_REF] Flajolet | Analytic Combinatorics[END_REF]) into one of the two following forms:

(1) L = F L with L ∈ L, or (2) L = U k L 1 DL 2 D . . . L k DL with k ≥ 1 and L 1 , L 2 , . . . , L k , L ∈ L (see Figure 2). Due to this decomposition, the generating function L(z) = n≥0 a n z n where a n is the cardinality of L n , satisfies the functional equation L(z) = 1 + zL(z) + k≥1 z k+1 L(z) k+1 , or equivalently, L(z) = . Therefore, a n is the n-th Catalan number a n = 1 n+1 2n n (see sequence A000108 in [START_REF] Sloane | The On-line Encyclopedia of Integer Sequences[END_REF]). In this paper, we provide enumerating results for several classes of partial Lukasiewicz paths (prefixes and suffixes of Lukasiewicz paths, partial alternate Lukasiewicz paths). More precisely, in Sections 2 and 3, we give bivariate generating functions and exact values for the number of n-length prefixes (resp. suffixes) of these paths ending at height k ≥ 0 with a given type of step (down, up, or horizontal step). In Sections 4 and 5, we make a similar study for paths of bounded height. In Section 6, we prove that the average height of n-length paths ending at a fixed height behaves as √ πn when n → ∞. In Section 7, we focus on partial alternate Lukasiewicz paths, i.e., Lukasiewicz paths that do contain two consecutive steps with the same direction.

All our explicit formulae follow from the standard identity

[z n ] 1 - √ 1 -4z 2z k = 2n -1 + k n - 2n -1 + k n .

Enumeration of Partial Lukasiewicz paths

Partial Lukasiewicz paths of length n (i.e., n-length prefixes of Lukasiewicz paths) ending at height k can be constructed through the following state diagram (Figure 3). The diagram has three types of states ranging from 0 to infinity on three layers; in the drawing, only the first fifth states of each type are shown. The first type of states (top layer) refers to an up-step leading to a state, the second type (middle layer) refers to a horizontal step leading to a state, and the third type (bottom layer) refers to a down-step leading to a state. Any path from the origin to a state of rank k of a layer represents a partial Lukasiewicz path ending at height k. For k ≥ 0, we consider the generating function

f k = f k (z) (resp. g k = g k (z), h k = h k (z))
, where the coefficient of z n in the series expansion is the number of partial Lukasiewicz paths of length n ending at height k with an up-step U k , k ≥ 1, (resp. with a down-step D, resp. with a horizontal step F ). Considering the state diagram in Figure 3, f k (resp. g k , h k ) is the generating function in the variable z marking the length of the paths ending on the (k + 1)-th state of the top (resp. middle, bottom) layer. So, we easily obtain the following equations:

f 0 = 1, and f k = z k-1 =0 f + z k-1 =0 g + z k-1 =0 h , k ≥ 1, g k = zf k+1 + zg k+1 + zh k+1 , k ≥ 0, h k = zf k + zg k + zh k , k ≥ 0. (1)
Now, we introduce bivariate generating functions

F (u, z) = k≥0 u k f k (z), G(u, z) = k≥0 u k g k (z), and H(u, z) = k≥0 u k h k (z).
For short, we also use the notation F (u), G(u) and H(u) for these functions. Summing the recursions in (1), we have:

F (u) = 1 + z k≥1 u k k-1 =0 f + k-1 =0 g + k-1 =0 h = 1 + z k≥0 u k+1 1 -u f k + z k≥0 u k+1 1 -u g k + z k≥0 u k+1 1 -u h k = 1 + uz 1 -u (F (u) + G(u) + H(u)), G(u) = z k≥0 u k f k+1 + g k+1 + h k+1 = z u (F (u) + G(u) + H(u) -F (0) -G(0) -H(0)), H(u) = z 1 -z (F (u) + G(u)),
where F (0) + G(0) + H(0) is the number of Lukasiewicz paths of length n, i.e.,

F (0) + G(0) + H(0) = L(z) = 1 - √ 1 -4z 2z .
Solving these functional equations, we deduce

F (u) = 1 -z - z 1 + √ 1 -4z 2u -1 - √ 1 -4z , G(u) = √ 1 -4z + 2z -1 2u -1 - √ 1 -4z , and
H(u) = z + z √ 1 -4z -1 2u -1 - √ 1 -4z ,
which implies that

f k = [u k ]F (u) = 2 k z (1 + √ 1 -4z) k = z 1 - √ 1 -4z 2z k , (2)
g k = [u k ]G(u) = 2 k (1 -2z - √ 1 -4z) (1 + √ 1 -4z) k+1 = (1 -2z - √ 1 -4z) 2 1 - √ 1 -4z 2z k+1 = z 1 - √ 1 -4z 2z k+2 -z 1 - √ 1 -4z 2z k+1 , (3)
and

h k = [u k ]H(u) = 2 k z(1 - √ 1 -4z) (1 + √ 1 -4z) k+1 = z(1 - √ 1 -4z) 2 1 - √ 1 -4z 2z k+1 = z 2 1 - √ 1 -4z 2z k+2 . (4)
Theorem 1. The bivariate generating function for the total number of partial Lukasiewicz paths of length n with respect to the height of the end-point is given by

Total (z, u) = 1 + -1 + √ 1 -4z 2u -1 - √ 1 -4z ,
and we have

[u k ]Total (z, u) = [k = 0] + zL(z) k+2 .
Finally, we have for n ≥ 1,

[z n ][u k ]Total (z, u) = k + 2 n + k + 1 2n + k -1 n -1 , [z n ][u k ]F (u) = k n + k -1 2n + k -3 n -1 , [z n ][u k ]G(u) = k + 3 n + k + 1 2n + k -2 n -2 , [z n ][u k ]H(u) = k + 2 n + k 2n + k -3 n -2 .
Here are examples of the series expansions of [u k ]Total (z, u) for k = 0, 1, 2, 3 (leading terms): 9 , which correspond respectively to A000108, A000245, A002057, and A000344 in [START_REF] Sloane | The On-line Encyclopedia of Integer Sequences[END_REF].

• 1 + z + 2z 2 + 5z 3 + 14z 4 + 42z 5 + 132z 6 + 429z 7 + 1430z 8 + 4862z 9 , • z + 3z 2 + 9z 3 + 28z 4 + 90z 5 + 297z 6 + 1001z 7 + 3432z 8 + 11934z 9 , • z + 4z 2 + 14z 3 + 48z 4 + 165z 5 + 572z 6 + 2002z 7 + 7072z 8 + 25194z 9 , • z + 5z 2 + 20z 3 + 75z 4 + 275z 5 + 1001z 6 + 3640z 7 + 13260z 8 + 48450z
According to Theorem 3.1 and Theorem 3.3 in [START_REF] Gudmundsson | Dyck paths, standard Young Tableaux, and pattern avoiding permutations[END_REF], [z n ][u k ]Total (z, u) counts also standard Young tableaux of shape (n+2, n-k +1) (see [START_REF] Knuth | The Art of Computer Programming[END_REF][START_REF] Young | On quantitative substitutional analysis[END_REF] for the definition of a standard Young tableau), and Dyck paths of semilength n + k starting with at least k up-steps and touching the x-axis somewhere between the two end-points.

Partial Lukasiewicz paths from right to left

In this section, we count partial Lukasiewicz paths that read from right to left, i.e., paths in N 2 starting at the origin, consisting of steps (1, k), k ≤ 1, and ending at a given height with a given type of step. Of course, this study is completely equivalent to counting suffixes of Lukasiewicz paths starting at a given height with a given type of step. We denote here by f k , g k , and h k the generating functions for the number of these paths (with respect to the length) ending at height k with an up-step, down-step, or a horizontal step, respectively.

Then we have f 0 = 1, and

f k = zf k-1 + zg k-1 + zh k-1 , k ≥ 1, g k = z ≥k+1 f + z ≥k+1 g + z ≥k+1 h , k ≥ 0, h k = zf k + zg k + zh k , k ≥ 0. ( 5
)
Considering the bivariate generating functions

F (u) = k≥0 u k f k (z), G(u) = k≥0 u k g k (z), and
H(u) = k≥0 u k h k (z),
and summing the recursions in (5), we obtain:

F (u) = 1 + z k≥1 u k (f k-1 + g k-1 + h k-1 ) = 1 + zuF (u) + zuG(u) + zuH(u), G(u) = z k≥0 u k ≥k+1 f + ≥k+1 g + ≥k+1 h = z k≥1 1 -u k 1 -u f k + z k≥1 1 -u k 1 -u g k + z k≥1 1 -u k 1 -u h k = z 1 -u (F (1) + G(1) + H(1) -F (u) -G(u) -H(u)), H(u) = z 1 -z (F (u) + G(u)),
with

F (0) + G(0) + H(0) = L(z) = 1 - √ 1 -4z 2z .
Moreover, we have

F (1) + G(1) + H(1) = L(z) -1 z ,
since there is a bijection between all partial Lukasiewicz paths of length n that read from right to left and Lukasiewicz paths that read from left to right of length n + 1 (from a Lukasiewicz path, we remove the first step, and we read it from right to left). Solving these functional equations, we deduce

F (u) = - 1 + √ 1 -4z 2zu - √ 1 -4z -1 , G(u) = -1 + √ 1 -4z + 2z 2zu - √ 1 -4z -1 , H(u) = - 2z 2zu - √ 1 -4z -1 ,
which implies that

f k = [u k ]F (u) = 2 k z k (1 + √ 1 -4z) k , (6)
g k = [u k ]G(u) = 2 k z k (1 -2z - √ 1 -4z) (1 + √ 1 -4z) k+1
, and ( 7)

h k = [u k ]H(u) = 2 k+1 z k+1 (1 + √ 1 -4z) k+1 . ( 8
)
Theorem 2. The bivariate generating function for the total number of partial Lukasiewicz paths of length n (from right to left) with respect to the height of the end-point is given by

Total (z, u) = 1 + 2 1 -2zu + √ 1 -4z ,
and we have

[u k ]Total (z, u) = z k L(z) k+1 .
Finally, for n ≥ 1, we obtain:

[z n ][u k ]T otal(z, u) = k + 1 n + 1 2n -k n , [z n ][u k ]F (u) = k n 2n -k -1 n -1 , [z n ][u k ]G(u) = k + 3 n + 1 2n -k -2 n , [z n ][u k ]H(u) = k + 1 n 2n -k -2 n -1 .
Here are examples of the series expansions of [u k ]Total (z, u) for k = 0, 1, 2, 3 (leading terms):

• 1 + z + 2z 2 + 5z 3 + 14z 4 + 42z 5 + 132z 6 + 429z 7 + 1430z 8 + 4862z 9 ,
• z + 2z 2 + 5z 3 + 14z 4 + 42z 5 + 132z 6 + 429z 7 + 1430z 8 + 4862z 9 , • z 2 + 3z 3 + 9z 4 + 28z 5 + 90z 6 + 297z 7 + 1001z 8 + 3432z 9 , • z 3 + 4z 4 + 14z 5 + 48z 6 + 165z 7 + 572z 8 + 2002z 9 , which correspond to shifts of A000108, A000245, A002057, and A000344 in [START_REF] Sloane | The On-line Encyclopedia of Integer Sequences[END_REF].

Partial Lukasiewicz paths constrained by height

In this section, we count partial Lukasiewicz paths bounded by a given height t ≥ 0. We introduce the notation f t k , g t k , h t k for 0 ≤ k ≤ t, F t (u), G t (u) and H t (u), which are the counterparts of f k , g k , h k , F (u), G(u) and H(u). Considering the state diagram of Figure 3 where each layer consists of only t + 1 states, we deduce the following system of equations:

                       -1 0 0 0 0 0 0 0 0 • • • 0 -1 0 z z z 0 0 0 • • • z z z -1 0 0 0 0 0 0 • • • z z z -1 0 0 0 0 0 • • • 0 0 0 0 -1 0 z z z • • • 0 0 0 z z z -1 0 0 0 • • • z z z z z z -1 0 0 • • • 0 0 0 0 0 0 0 -1 0 • • • 0 0 0 0 0 0 z z z -1 • • • . . . . . . . . . . . . . . . . . . . . . . . . . . .                        •                        f t 0 g t 0 h t 0 f t 1 g t 1 h t 1 f t 2 g t 2 h t 2 . . .                        =                        -1 0 0 0 0 0 0 0 0 . . .                        .
For a given height t ≥ 0, the previous matrix (denoted A t ) is square with 3(t + 1) rows. Using classical properties of the determinant, we can prove that D t = det(A t ) satisfies

D t+2 + D t+1 + zD t = 0,
anchored with D 0 = z -1, and D 1 = 1 -2z. Then we deduce,

D t = z(-1) t+2 1 - √ 1 -4z t+2 2 t+1 √ 1 -4z 1 + √ 1 -4z + z(-1) t+1 1 + √ 1 -4z t+2 2 t+1 √ 1 -4z 1 - √ 1 -4z , which corresponds to D t = (-1) t+1 • F t ,
where F t is the generalized Fibonacci polynomial (see [START_REF] Florez | Irreducibility of generalized Fibonacci polynomials[END_REF][START_REF] Kreweras | Sur les éventails de segments[END_REF]):

F t = 1 - t + 1 1 z + t 2 z 2 - t -1 3 z 3 + . . . .
For instance, we have D 3 = F 3 = 1 -4z + 3z 2 , and D 4 = -F 4 = -1 + 5z -6z 2 + z 3 . Using Cramer's rule to solve the system, for 0 ≤ k ≤ t, we have

f t k = N t 3k+1 D t , g t k = N t 3k+2 D t , h t k = N t 3k+3 D t , (9)
where N t k is the determinant of the matrix A t (k) obtained from A t by replacing the (k + 1)-th column with the vector (-1, 0, 0, 0, . . . , 0, 0) T .

As we have done for D t , it is easy to prove that N t k satisfies the two recurrence relations

N t+2 k + N t+1 k + zN t k = 0, 1 ≤ k, 1 + k 3 ≤ t, and
N t+1 k+3 = -N t k , 4 ≤ k, 1 ≤ t. Calculating N t k for (t, k) ∈ {0, 1, 2} × {1, 2, 3}
, and for (t, k) ∈ {1, 2, 3} × {4, 5, 6}, we can easily obtain a closed form for N t 3k+i , 1 ≤ i ≤ 3. See Table 1 for exact values of N t k when 0 ≤ t ≤ 4 and 1 ≤ k ≤ 12. In particular, for t ≥ 0, we have N t 1 = D t (see above for a closed form),

k/t 0 1 2 3 4 1 z -1 1 -2z -(z 2 -3z + 1) 3z 2 -4z + 1 z 3 -6z 2 + 5z -1 2 0 z 2 -z 2 z 2 (1 -z) -z 2 (1 -2z) 3 -z z(1 -z) -z(1 -2z) z(z 2 -3z + 1) -z(3z 2 -4z + 1) 4 z(1 -z) -z(1 -2z) z(z 2 -3z + 1) -z(3z 2 -4z + 1) 5 0 -z 2 z 2 -z 2 (1 -z) 6 z 2 -z 2 z 2 (1 -z) -z 2 (1 -2z) 7 -z(1 -z) z(1 -2z) -z(z 2 -3z + 1) 8 0 z 2 -z 2 9 -z 2 z 2 -z 2 (1 -z) 10 z(1 -z) -z(1 -2z) 11 0 -z 2 12 z 2 -z 2 13 . . .
N t 2 = z 2 -2z 1+ √ 1-4z t √ 1 -4z - z 2 - 2z - √ 1-4z+1 t √ 1 -4z , N t 3 = - z 2 -1 + √ 1 -4z -2z 1+ √ 1-4z t √ 1 -4z 1 + √ 1 -4z - z 2 1 + √ 1 -4z - 2z - √ 1-4z+1 t √ 1 -4z - √ 1 -4z + 1 ,
and for t ≥ 1,

N t 4 = N t 3 , N t 5 = -N t-1 2
, and N t 6 = N t 2 . Using (9), we can deduce closed forms for f t k , g t k , h t k , 0 ≤ k ≤ 1, and k ≤ t. Using the above recurrence relations for N t k , we deduce closed forms for

f t k , g t k , h t k , 2 ≤ k ≤ t.
Theorem 3. For 2 ≤ k ≤ t, we have

f k = [u k ]F (u) = N t-k+1 3 D t (-1) k-1 , (10)
g k = [u k ]G(u) = N t-k 2 D t (-1) k , and (11)
h k = [u k ]H(u) = N t-k+1 2 D t (-1) k-1 . ( 12
)
For t = 2, 3, 4, the first terms of the series expansion of f 2 are • z + 2z 2 + 5z 3 + 13z 4 + 34z 5 + 89z 6 + 233z 7 + 610z 8 + 1597z 9 , • z + 2z 2 + 5z 3 + 14z 4 + 41z 5 + 122z 6 + 365z 7 + 1094z 8 + 3281z 9 , • z + 2z 2 + 5z 3 + 14z 4 + 42z 5 + 131z 6 + 417z 7 + 1341z 8 + 4334z 9 , which correspond to the sequences A001519, A007051, A080937 in [START_REF] Sloane | The On-line Encyclopedia of Integer Sequences[END_REF], that also count Dyck paths of semilength n of height at most t + 1.

Theorem 4. The generating function [u k ]Total t (z, u) for the number of partial Lukasiewicz paths of height at most t ≥ 0, ending at height k ≥ 1, is given by

(-1) k-1 N t-k+1 3 -N t-k 2 + N t-k+1 2 D t .
Moreover, we have

[u 0 ]Total t (z, u) = D t + N t 2 + N t 3 D t .
The generating function for the total number of partial Lukasiewicz paths of height at most t ≥ 0 is given by

Total t (z, 1) = (-1) t+1 • D -1 t = F -1 t .
For t = 0, 1, 2, 3, 4, the first terms of the series expansion of Total t (z, 1) are

• 1 + z + z 2 + z 3 + z 4 + z 5 + z 6 + z 7 + z 8 + z 9 , • 1 + 2z + 4z 2 + 8z 3 + 16z 4 + 32z 5 + 64z 6 + 128z 7 + 256z 8 + 512z 9 , • 1 + 3z + 8z 2 + 21z 3 + 55z 4 + 144z 5 + 377z 6 + 987z 7 + 2584z 8 + 6765z 9 ,
• 1 + 4z + 13z 2 + 40z 3 + 121z 4 + 364z 5 + 1093z 6 + 3280z 7 + 9841z 8 + 29524z 9 , • 1 + 5z + 19z 2 + 66z 3 + 221z 4 + 728z 5 + 2380z 6 + 7753z 7 + 25213z 8 + 81927z 9 , which correspond to A000012, A000079, A001906, A003462, A005021 in [START_REF] Sloane | The On-line Encyclopedia of Integer Sequences[END_REF].

Using [START_REF] Kreweras | Sur les éventails de segments[END_REF], [z n ] Total t (z, 1) counts also paths of length 2n + 1 + t in N 2 starting at the origin, ending at (n + t + 1, n), consisting of steps (0, 1), and (1, 0), and such that all its points (x, y) satisfy x -t -1 ≤ y ≤ x. It would be interesting to exhibit a constructive bijection between these paths and partial Lukasiewicz paths of height at most t ≥ 0.

Partial Lukasiewicz paths constrained by height from right-to-left

In this section, we count partial Lukasiewicz paths from right-to-left bounded by a given height t ≥ 0. We denote here by f t k , g t k , h t k for 0 ≤ k ≤ t, F t (u), G t (u) and H t (u), the generating functions in the same way as for Section 4. We deduce the following system of equations:

                       -1 0 0 0 0 0 0 0 0 • • • 0 -1 0 z z z z z z • • • z z z -1 0 0 0 0 0 0 • • • z z z -1 0 0 0 0 0 • • • 0 0 0 0 -1 0 z z z • • • 0 0 0 z z z -1 0 0 0 • • • 0 0 0 z z z -1 0 0 • • • 0 0 0 0 0 0 0 -1 0 • • • 0 0 0 0 0 0 z z z -1 • • • . . . . . . . . . . . . . . . . . . . . . . . . . . .                        •                        f t 0 g t 0 h t 0 f t 1 g t 1 h t 1 f t 2 g t 2 h t 2 . . .                        =                        -1 0 0 0 0 0 0 0 0 . . .                       
.

Jean-Luc Baril and Helmut Prodinger

For a given height t ≥ 0, the previous matrix (denoted A t ) is square with 3(t + 1) rows. Using classical properties of the determinant, we can prove that det(A t ) = det(A t ) = D t , for t ≥ 0. Using Cramer's rule to solve the system, for 0 ≤ k ≤ t, we have

f t k = N t 3k+1 D t , g t k = N t 3k+2 D t , h t k = N t 3k+3 D t , (13)
where N t k is the determinant of the matrix A t (k) obtained from A t by replacing the k-th column with the vector (-1, 0, 0, 0, . . . , 0, 0) T .

As we have done for D t , it is easy to prove that N t k satisfies the two recurrence relations

N t+2 k + N t+1 k + zN t k = 0, 1 ≤ k ≤ 3, 2 ≤ t, and
N t+1 k = -zN t k-3 , 4 ≤ k, 0 ≤ t, where N t
k is the same as in Section 4 whenever (t, k) ∈ N × {1, 2, 3}.

Theorem 5. For 0 ≤ k ≤ t, we have

f k = [u k ]F (u) = N t-k 1 D t (-1) k z k , (14)
g k = [u k ]G(u) = N t-k 2 D t (-1) k z k , and (15)
h k = [u k ]H(u) = N t-k 3 D t (-1) k z k . (16)
Theorem 6. The generating function [u k ]Total t (z, u) for the number of partial Lukasiewicz paths (from right to left) of height at most t ≥ 0, ending at height k ≥ 0, is given by

(-1) k z k N t-k 1 + N t-k 2 + N t-k 3 D t .
The generating function for the total number of partial Lukasiewicz paths (from right to left) of height at most t ≥ 2 is given by Total t (z, 1) = D t-2 D t .

Moreover, we have Total 0 (z, 1) = 1 1 -z , and Total 1 (z, 1) = 1 1 -2z .

For t = 0, 1, 2, 3, the first terms of the series expansion of Total t (z, 1) are

• 1 + z + z 2 + z 3 + z 4 + z 5 + z 6 + z 7 + z 8 + z 9 , • 1 + 2z + 4z 2 + 8z 3 + 16z 4 + 32z 5 + 64z 6 + 128z 7 + 256z 8 + 512z 9 , • 1 + 2z + 5z 2 + 13z 3 + 34z 4 + 89z 5 + 233z 6 + 610z 7 + 1597z 8 + 4181z 9 , • 1 + 2z + 5z 2 + 14z 3 + 41z 4 + 122z 5 + 365z 6 + 1094z 7 + 3281z 8 + 9842z 9 ,
which correspond to A000012, A000079, A001519, A007051 in [START_REF] Sloane | The On-line Encyclopedia of Integer Sequences[END_REF]. Note that the two series in Theorem 4 and Theorem 6 coincide when t = 0, 1 since, in these cases, partial Lukasiewicz paths bounded by the height t are identical from left-to-right and from right-to-left.

The average height of Lukasiewicz paths

In this section, we prove that the average height of n-length partial Lukasiewicz paths (from left to right, and from right to left) ending at a fixed height behaves as √ πn when n → ∞

The fact that the formula is different for small values of t and that we start the sum at 1 and not at 3, does not change the main term. We get

R >t ∼ (1 + u) 3 (1 -u) u 2 t≥1 u t 1 -u t ∼ -8 log(1 -u),
and the coefficient of z n in it is asymptotic to 4 n+1 n .

For the total number of paths, we get the asymptotic formula

4 n+1 √ πn 3/2 ,
and the average height is again asymptotic to √ πn.

Partial alternate Lukasiewicz paths

In this section, we study prefixes of alternate Lukasiewicz paths, i.e., Lukasiewicz paths that do not contain two consecutive steps with the same direction (or equivalently, walks in the state diagram of Figure 3 without two consecutive arrows of the same color). We refer to Figure 4 for the state diagram associated with these paths. We denote here by f k , g k , and h k the generating functions for the number of these paths (with respect to the length) ending at height k with an up-step, down-step, or a horizontal step, respectively. We have the following equations:

f 0 = 1, and f k = zf 0 + z k-1 =0 g + z k-1 =0 h , k ≥ 1, g k = zf k+1 + zh k+1 , k ≥ 0, h k = zf k + zg k , k ≥ 0. ( 17
)
Considering the bivariate generating functions and summing the recursions in [START_REF] Stanley | Enumerative Combinatorics[END_REF], we obtain

F (u) = 1 + z k≥1 u k 1 + k-1 =0 g + k-1 =0 h = 1 + zu 1 -u + z k≥0 u k+1 1 -u g k + z k≥0 u k+1 1 -u h k
Here are examples of the series expansions of [u k ]Total (z, u) for k = 0, 1, 2, 3 (leading terms): • 1 + z + z 2 + 3z 3 + 5z 4 + 9z 5 + 19z 6 + 39z 7 + 81z 8 + 173z 9 , • z + 3z 2 + 5z 3 + 11z 4 + 25z 5 + 53z 6 + 115z 7 + 255z 8 + 565z 9 ; • z + 3z 2 + 7z 3 + 19z 4 + 45z 5 + 105z 6 + 247z 7 + 575z 8 + 1333z 9 , • z + 3z 2 + 9z 3 + 27z 4 + 69z 5 + 177z 6 + 443z 7 + 1087z 8 + 2645z 9 , which do not appear in [START_REF] Sloane | The On-line Encyclopedia of Integer Sequences[END_REF]. The first terms of the series expansion of the generating function for the number of alternate Lukasiewicz paths are 1 + z + z 2 + 3z 3 + 5z 4 + 9z 5 + 19z 6 + 39z 7 + 81z 8 + 173z 9 .

A singularity analysis of the generating function [u 0 ]Total (z, u) gives The reason that this constant appears, results from the singularity analysis. Indeed, one needs the solution closest to the origin of 4z 6 -4z 4 -4z 3 -4z 2 + 1 = 0, which is a = 0.403031716762 . . . . Maple provides the curious explicit version if one asks for a simplification.

Figure 1 :

 1 Figure 1: A Lukasiewicz path of length 18: U 5 DDF F DU 2 DDDDU 2 F U 2 DDDD.

1 1 -

 1 zL(z) . Then,L(z) = 1- √ 1-4z 2z

Figure 2 :

 2 Figure 2: The two forms of a non-empty Lukasiewicz path.

Figure 3 :

 3 Figure 3: The state diagram for the generation of partial Lukasiewicz paths. Black (resp. red, blue) arrows correspond to up-steps (resp. down-steps, horizontal steps).

Figure 4 :

 4 Figure 4: The state diagram for partial alternate Lukasiewicz paths. Black (resp. red, blue) arrows correspond to up-steps (resp. down-steps, horizontal steps).

F

  (u, z) = k≥0 u k f k (z), G(u, z) = k≥0 u k g k (z), and H(u, z) = k≥0 u k h k (z),

[√ πa 2 (a 2 + 1

 221 z n ][u 0 ]Total (z, u) ∼ √ -6a 6 + 4a 4 + 3a 3 + 2a 2 (a + 1)2 n -a 2 + a + 1 n

Table 1 :

 1 The first values of N t k for 0 ≤ t ≤ 4 and 1 ≤ k ≤ 12.

The left-to-right model

We simplify the expressions given in Section 4 using the substitution z = u (1+u) 2 , first used in [START_REF] De Bruijn | The average height of planted plane trees[END_REF]. Then, we find

We start with paths ending on the x-axis, as the formula is (slightly) different. The generating function of these paths bounded by t is

Taking the limit when t → ∞, we retrieve, as expected,

Then, the generating function of paths of height at least t + 1 is

We refer to [START_REF] Heuberger | The height of multiple edge plane trees[END_REF] where a similar instance is worked out with an extensive amount of detail. For the average height, we have (before normalizing by the Catalan numbers) to compute

The goal is to find the local behavior of u ∼ 1 since it translates to the local behavior of z ∼ 1 4 . To find this, we set u = e -t and we use the Mellin transform. We do not need to do the actual computation, since we just cite the result from [START_REF] Heuberger | The height of multiple edge plane trees[END_REF]. First, the factor is simple since we have

Since we only compute the leading term of the asymptotic expansion, we use

found in [START_REF] Heuberger | The height of multiple edge plane trees[END_REF] for instance. So, we obtain

Singularity analysis of generating functions (see [START_REF] Flajolet | Singularity analysis of generating functions[END_REF]) allows us to translate this to the coefficients of z n , with the result ∼ 4 n n . For Catalan numbers, we have the well-known

Finally, the average height of paths ending on the x-axis behaves as

For path ending at height k ≥ 1, the generating function of paths bounded by t is

The limit for t → ∞ is u(1 + u) k , and

For the average height (the leading term only, before normalization), we compute

For the total number of paths ending at height k, we have

and the average height (k fixed, n → ∞) is asymptotic to

as before.

To compute the average height of paths with unspecified endpoints makes no sense in this model since the number of such paths of length n is infinite.

The right-to left model

We simplify the expressions given in Section 5 using the substitution z = u (1+u) 2 . We have to analyze

Taking the limit when t → ∞, we obtain

.

For the average, we must compute

where we took liberties about two missing terms, which do not influence the main term of the average height. As before, we get the asymptotic behavior (k + 1)

For the total number of paths ending at height k, we get

and the average height (k fixed, n → ∞) is again asymptotic to √ πn. Now we move to the Lukasiewicz paths with unspecified end and have to consider

Solving these functional equations, we deduce

Now we apply the kernel method on H(u). We have

with

In order to compute H(0), it suffices to plug u = s 2 in the numerator of [START_REF] Varvak | Lattice path encodings in a combinatorial proof of a differential identity[END_REF]. Then, H(0) satisfies zH(0)(s 2 z -s 2 + 1) -s 2 2 z + s 2 2 -s 2 = 0, which implies that

After this, and using s 1 s 2 (1 + z 2 ) = z 2 , we simplify of both, numerators and denominators, in F (u), G(u), H(u) by factorizing them with (u -s 2 ).

Finally, we easily obtain

Since the series expansion of s 1 does not have pretty coefficients, we cannot expect this from our final answers.

Theorem 7. The bivariate generating function for the total number of partial alternate Lukasiewicz paths with respect to the length and the height of the end-point is given by Total (z, u) = s 2 1 z 2 + s 1 uz 2 + 2s 1 z 3 + s 2 1 -s 1 u + zs 1 + z 2 (z 2 + 1) (-u + s 1 )s 1 .

Moreover, we have