Sminaire Lotharingien de Combinatoire 57 (2008), Article B57d

DISCRETE EXCURSIONS

MIREILLE BOUSQUET-MÉLOU

Abstract. It is well known that the length generating function E(t) of Dyck paths (excursions with steps ±1) satisfies 1 − E + t^{2}E^{2} = 0. The generating function E^{(k)}(t) of Dyck paths of height at most k is E^{(k)} = F_{k}/F_{k+1}, where the F_{k} are polynomials in t given by F_{0} = F_{1} = 1 and F_{k+1} = F_{k} − t^{2}F_{k−1}. This means that the generating function of these polynomials is ∑_{k≥0} F_{k}z^{k} = 1/(1 − z + t^{2}z^{2}). We note that the denominator of this fraction is the minimal polynomial of the algebraic series E(t).

This pattern persists for walks with general steps. For any finite set of steps S, the generating function E^{(k)}(t) of excursions (generalized Dyck paths) taking their steps in S and of height at most k is the ratio F_{k}/F_{k+1} of two polynomials. These polynomials satisfy a linear recurrence relation with coefficients in ℚ[t]. Their (rational) generating function can be written ∑_{k≥0} F_{k}z^{k} = N(t, z)/D(t, z). The excursion generating function E(t) is algebraic and satisfies D(t, E(t)) = 0 (while N(t, E(t)) ≠ 0).

If max S = a and min S = b, the polynomials D(t, z) and N(t, z) can be taken to be respectively of degree d_{a,b} = \binom{a+b}{a} and d_{a,b} − a − b in z. These degrees are in general optimal: for instance, when S = {a, −b} with a and b coprime, D(t, z) is irreducible, and is thus the minimal polynomial of the excursion generating function E(t).

The proofs of these results involve a slightly unusual mixture of combinatorial and algebraic tools, among which the kernel method (which solves certain functional equations), symmetric functions, and a pinch of Galois theory.

1. Introduction

One of the most classical combinatorial incarnations of the famous Catalan numbers, C_{n} = \binom{2n}{n}/(n + 1), is the set of Dyck paths. These are one-dimensional walks that start and end at 0, take steps ±1, and always remain at a non-negative level (Figure 1, left). By factoring such walks at their first return to 0, one easily proves that their length generating function E ≡ E(t) is algebraic, and satisfies

E = 1 + t^{2}E^{2}.

This immediately yields:

E = \frac{1 − \sqrt{1 − 4t^{2}}}{2t^{2}} = ∑_{n≥0} C_{n}t^{2n}.

The author was supported by the french Agence Nationale de la Recherche, via the project SADA, ANR-05-NT05-3-41532.

MIREILLE BOUSQUET-MÉLOU

Figure 1. Left: A Dyck path of length 16 and height 4. Right: An excursion (generalized Dyck path) of length 8 and height 7, with steps in S = {−3, 5}.

The same factorization gives a recurrence relation that defines the series E^{(k)} ≡ E^{(k)}(t) counting Dyck paths of height at most k:

E^{(0)} = 1 and for k ≥ 1, E^{(k)} = 1 + t^{2}E^{(k−1)}E^{(k)}.

This recursion can be used to prove that E^{(k)} is rational, and more precisely, that

E^{(k)} = \frac{F_{k}}{F_{k+1}} , where F_{0} = F_{1} = 1 and F_{k+1} = F_{k} − t^{2}F_{k−1}.

The aim of this paper is to describe what happens for generalized Dyck paths (also known as excursions) taking their steps in an arbitrary finite set S ⊂ ℤ (see an example in Figure 1, right). Their length generating function E is known to be algebraic. What is the degree of this series? How can one compute its minimal polynomial? Furthermore, it is easy to see that the generating function E^{(k)} can still be written F_{k}/F_{k+1}, for some polynomials F_{k}. Does the sequence (F_{k})_{k} satisfy a linear recurrence relation? Of what order? How can one determine this recursion? Note that any linear recursion of order d, of the form

∑_{i=0}^{d} a_{i}F_{k−i} = 0  (1)

with a_{i} ∈ ℚ[t], gives a non-linear recursion of order d for the series E^{(k)},

∑_{i=0}^{d} a_{i}E^{(k−i+1)} ⋯ E^{(k)} = 0,  (2)

and, by taking the limit k → ∞, an algebraic equation of degree d satisfied by E = lim_{k} E^{(k)}:

∑_{i=0}^{d} a_{i}E^{i} = 0.

This establishes a close link between the (still hypothetical) recursion for the sequence F_{k} and the algebraicity of E. The connection between (1) and (2) is central in the recent paper [2] dealing with excursions with steps ±1, ±2.

A slightly surprising outcome of this paper is that symmetric functions are closely related to the enumeration of excursions. This can be seen in the following summary of our answers to the above questions. Assume min S = −b and max S = a. Then the excursion generating function E is algebraic of degree at most d_{a,b} := \binom{a+b}{a}. The degree is exactly d_{a,b} in the generic case (to be defined), but also when S = {−b, a} with a and b coprime. Computing a polynomial of degree d_{a,b} that annihilates E boils down to computing the elementary plethysms e_{k}[e_{a}] on an alphabet with a + b letters, for 0 ≤ k ≤ d_{a,b}.

The generating function E^{(k)} counting excursions of height at most k is rational and can be written F_{k}/F_{k+1} for some polynomials F_{k}. These polynomials satisfy a linear recurrence relation of the form (1), of order d_{a,b}, which is valid for k > d_{a,b} − a − b. Moreover, F_{k} can be expressed as a determinant of varying size k, but also as a rectangular Schur function taking the form of a determinant of constant size a + b.

These results are detailed in the next section. Not all of them are new. The generating function of excursions, given in Proposition 1, first appeared in [6], but can be derived from the earlier paper [17]. An algorithm for computing a polynomial of degree d_{a,b} that annihilates E was described in [5]. Hence the first part of the next section, which deals with unbounded excursions, is mostly a survey (the results on the exact degree of E are however new). The second part — excursions of bounded height — is new, although an attempt in the same vein appears in [3].

Let us finish with the plan of this paper. The kernel method has become a standard tool to solve certain functional equations arising in various combinatorial problems [4, 14, 26]. We illustrate it in Section 3 by counting unbounded excursions. We use it again in Section 4 to obtain the generating function of excursions of bounded height. Remarkably, the same result can be obtained by combining the transfer-matrix method and the dual Jacobi–Trudi identity. In Section 5, we determine the recurrence relation satisfied by the polynomials F_{k}. More precisely, we compute the rational series ∑_{k} F_{k}z^{k}. This is equivalent to computing the generating function of rectangular Schur functions ∑_{k} s_{k^{a}}z^{k}, where a = max S. Finally, we discuss in Section 6 the exact degree of the series E for certain step sets S. This involves a bit of Galois theory.

2. Statement of the results

We consider one-dimensional walks that start from 0, take their steps in a finite set S ⊂ ℤ, and always remain at a non-negative level. More formally, a (nonnegative) walk of length n will be a sequence (s_{1}, s_{2}, …, s_{n}) ∈ S^{n} such that for all i ≤ n, the partial sum s_{1} + ⋯ + s_{i} is non-negative. The final level of this walk is s_{1}+⋯+s_{n}, and its height is max_{i} s_{1}+⋯+s_{i}. An excursion is a non-negative walk ending at level 0 (Figure 1). We are interested in the enumeration of excursions.

The generating functions we consider are fairly general, in that every step s ∈ S is weighted by an element ω_{s} of some field 𝕂 of characteristic 0. For instance, all the ω_{s} may be 1. Or they may be independent indeterminates. In the latter case, 𝕂 is the fraction field ℚ(ω_{s}, s ∈ S). The length of the walks is taken into account by an additional indeterminate t, transcendental over 𝕂. In particular, the generating function of excursions is

E := ∑ ω_{s_{1}} ⋯ ω_{s_{n}}t^{n},

where the sum runs over all excursions (s_{1}, s_{2}, …, s_{n}). This is a power series in t with coefficients in 𝕂. In one occasion (Example 2), we will then specialize the indeterminates ω_{s} into polynomials in t. The series E becomes a well-defined power series in t.

If min S = −b and max S = a, we assume that ω_{−b} and ω_{a} are non-zero. If d divides all the elements of S, the excursion generating function is unchanged if we replace each s ∈ S by s/d (up to a renaming of the weights ω_{s}). Thus we can always assume that the elements of S are relatively prime. Also, if (s_{1}, s_{2}, …, s_{n}) is an excursion, (−s_{n}, …, −s_{2}, −s_{1}) is also an excursion, with steps in −S. Thus the excursion series obtained for S and −S coincide, up to a renaming of the weights ω_{s}.

The weighting of the walks that we have defined depends on the list of steps that are taken, but not on the positions of these steps in ℤ. For instance, we cannot keep track of the number of visits to 0 with our weights, whereas this parameter is sometimes of interest [1, 8]. However, the methods we present here are fairly robust and can often be adapted to solve variants of the two main questions studied in this paper (including the number of visits to 0).

In the expression of E given below (Proposition 1), an important role is played by the following term, which encodes the steps of S:

P (u) = ∑_{s∈S} ω_{s}u^{s},  (3)

where u is a new indeterminate. This is a Laurent polynomial in u with coefficients in 𝕂. If min S = −b, we define

K(u) = u^{b} (1 − tP (u)) .  (4)

This is now a polynomial in u with coefficients in 𝕂[t]. If max S = a, this polynomial has degree a + b in u. It has a + b roots, which are fractional Laurent series (Puiseux series) in t with coefficients in \overline{𝕂}, an algebraic closure of 𝕂. (We refer the reader to [30, Ch. 6] for generalities on the roots of a polynomial with coefficients in 𝕂[t].) Exactly b of these roots, say U_{1}, …, U_{b}, are finite at t = 0. These roots are actually formal power series in t^{1/b}, and the first term of U_{i} is ξ^{i} (tω_{−b})^{1/b}, where ξ is a bth root of unity. In particular, these b series are distinct, and vanish at t = 0. We call them the small roots of K. The a other roots, U_{b+1}, …, U_{a+b}, are the large roots of K. They are Laurent series in t^{1/a}, and their first term is ct^{−1/a}, for some c ≠ 0. Note that K(u) factors as

K(u) = u^{b}(1 − tP (u)) = −tω_{a} ∏_{i=1}^{a+b} (u − U_{i}) ,

so that the elementary symmetric functions of the U_{i}’s are:

e_{i}(U) = (−1)^{i} (\frac{ω_{a−i}}{ω_{a}} − \frac{1}{tω_{a}} χ_{a=i}) ,  (5)

with U = (U_{1}, …, U_{a+b}). We refer to [30, Ch. 7] or [23] for generalities on symmetric functions.

2.1. Unbounded excursions

At least three different approaches have been used to count excursions. The first one generalizes the factorization of Dyck paths mentioned at the beginning of the introduction. It yields a system of algebraic equations defining E [1, 15, 21, 22, 24]. The factorization differs from one paper to another. To our knowledge, the simplest, and most systematic one, appears in [15].

A second approach [17] relies on a factorization of unconstrained walks taking their steps in S, and on a related factorization of formal power series. The expression of E that can be derived from [17] (by combining Proposition 4.4 and the proof of Proposition 5.1) coincides with the expression obtained by the third approach, which is based on a step by step construction of the walks [6, 5]. This expression of E is given in (6) below. We repeat in Section 3 the proof of (6) published in [6], as it will be extended later to count bounded excursions.

Proposition 1. The generating function of excursions is algebraic over 𝕂(t) of degree at most d_{a,b} = \binom{a+b}{a}. It can be written as:

E = \frac{(−1)^{b+1}}{tω_{−b}} ∏_{i=1}^{b} U_{i} = \frac{(−1)^{a+1}}{tω_{a}} ∏_{i=b+1}^{a+b} \frac{1}{U_{i}} ,  (6)

where U_{1}, …, U_{b} (respectively U_{b+1}, …, U_{a+b}) are the small (respectively large) roots of the polynomial K(u) given by (4). The quantity defined by

D(t, z) = ∏_{I⊂⟦a+b⟧, |I|=a} (1 + (−1)^{a}ztω_{a}U_{I}) ,  (7)

with ⟦a + b⟧ = {1, 2, …, a + b} and

U_{I} = ∏_{i∈I} U_{i},

is a polynomial in t and z with coefficients in 𝕂, of degree d_{a,b} in z, satisfying D(t, E) = 0.

Once the expression (6) is established, the other statements easily follow. Indeed, the second expression of E shows that D(t, E) = 0. Moreover, the expression of D(t, z) is symmetric in the roots U_{1}, …, U_{a+b}, so that its coefficients belong to 𝕂(t). More precisely, the form (5) of the elementary symmetric functions of the U_{i}’s shows that D(t, z) is a Laurent polynomial in t. But the valuation of U_{i} in t is at least −1/a, and this implies that D(t, z) is a polynomial in t.

Clearly, the degree of D(t, z) in z is d_{a,b} = \binom{a+b}{a}. Thus the excursion generating function E has degree at most d_{a,b}. We prove in Section 6 that D(t, z) is actually irreducible in the two following cases:

• S = ⟦−b, a⟧ = {−b, …, a − 1, a} and ω_{−b}, …, ω_{a} are independent indeterminates (the generic case),

• S = {−b, a} with ω_{−b} = ω_{a} = 1 and a and b coprime (two-step excursions). As shown by Example 2 below, D(t, z) is not always irreducible.

An algebraic equation for E. As argued above, D(t, z) is a polynomial in t and z that vanishes for z = E. However, its expression (7) involves the series U_{i}, while one would prefer to obtain an explicit polynomial in t and z. Recall that the series U_{i} are only known via their elementary symmetric functions (5). How can one compute a polynomial expression of D(t, z)? The approaches based on resultants or Gröbner bases become very quickly ineffective.

In the generic case where S = ⟦−b, a⟧ and the weights ω_{s} are indeterminates, K(u) is the general polynomial of degree a + b in u, and the problem can be rephrased as follows: Take n = a + b variables u_{1}, …, u_{n}, and expand the polynomial

Q(z) = ∏_{I⊂⟦n⟧, |I|=a}(1 − zu_{I})  (8)

in the basis of elementary symmetric functions of u_{1}, …, u_{n}. For instance, for a = 2 and b = 1,

Q(z) = (1 − zu_{1}u_{2})(1 − zu_{1}u_{3})(1 − zu_{2}u_{3})

= 1 − z(u_{1}u_{2} + u_{1}u_{3} + u_{2}u_{3}) + z^{2}(u_{1}^{2}u_{2}u_{3} + u_{1}u_{2}^{2}u_{3} + u_{1}u_{2}u_{3}^{2}) − z^{3}(u_{1}u_{2}u_{3})^{2}

= 1 − ze_{2} + z^{2}e_{3,1} − z^{3}e_{3,3},

while for a = b = 2,

Q(z) = 1−ze_{2}+z^{2}(e_{3,1}−e_{4})−z^{3}(e_{3,3}+e_{4,1,1}−2e_{4,2})+z^{4}e_{4}(e_{3,1}−e_{4})−z^{5}e_{4,4,2}+z^{6}e_{4,4,4}.

(9)

Using the standard notation for plethysm [30, Appendix 2], the polynomial Q(z) reads

Q(z) = ∑_{k=0}^{d_{a,b}}(−z)^{k}e_{k}[e_{a}].

This shows that, in the generic case, the problem of expressing D(t, z) as a polynomial in t and z is equivalent to expanding the plethysms e_{k}[e_{a}] in the basis of elementary symmetric functions, for an alphabet of n = a + b variables. Unfortunately, there is no general expression for the expansion of e_{k}[e_{a}] in any standard basis of symmetric functions, and only algorithmic solutions exist [9, 10]. Most of them expand plethysms in the basis of Schur functions. This is justified by the representation-theoretic meaning of plethysm. Still, in our walk problem, the natural basis is that of elementary functions. We have used for our calculations the simple platypus^{1} algorithm presented in [5], which only exploits the connections between power sums and elementary symmetric functions. This algorithm takes advantage automatically of simplifications occurring in non-generic cases. For instance, when only two steps are allowed, say −b and a, all the elementary symmetric functions of the U_{i}’s vanish, apart from e_{0}(U), e_{a}(U) and e_{a+b}(U). It would be a shame to compute the general expansion of e_{k}[e_{a}] in the elementary basis, and then specialize most of the e_{i} to 0. The platypus algorithm directly gives the expansion of e_{k}[e_{a}] modulo the ideal generated by the e_{i}, for i ≠ 0, a, a + b. For instance, when a = 2 and b = 1,

1Don’t ask me why it is called so!

Q(z) ≡ 1 − ze_{2} − z^{3}e_{3}^{2},

while for a = 2 and b = 3,

Q(z) ≡ 1 − ze_{2} − 2z^{5}e_{5}^{2} + z^{6}e_{2}e_{5}^{2} − z^{7}e_{2}^{2}e_{5}^{2} + z^{10}e_{5}^{4}.

and for a = 5 and b = 2,

Q(z) ≡ 1 − ze_{5} − 3z^{7}e_{7}^{5} + 2z^{8}e_{5}e_{7}^{5} − 2z^{9}e_{5}^{2}e_{7}^{5} + z^{10}e_{5}^{3}e_{7}^{5} − z^{11}e_{5}^{4}e_{7}^{5}

+ 3z^{14}e_{7}^{10} − z^{15}e_{5}e_{7}^{10} + 2z^{16}e_{5}^{2}e_{7}^{10} − z^{21}e_{7}^{15}.

From the above examples, one may suspect that, in the two-step case, the coefficient of z^{k} in Q(z) is always a monomial in the e_{i}. Going back to the polynomial D(t, z), and given that

e_{a}(U) = \frac{(−1)^{a+1}}{tω_{a}} and e_{a+b}(U) = (−1)^{a+b} \frac{ω_{−b}}{ω_{a}} ,

this would mean that the coefficient of z^{k} in D(t, z) is always a monomial in t. This observation first gave us some hope to find (in the two-step case) a simple description of D(t, z) and, why not, a direct combinatorial proof of D(t, E) = 0. However, this nice pattern does not persist: for a = 3 and b = 5, the coefficient of z^{16} in Q(z) contains e_{8}^{6} and e_{3}^{8}e_{8}^{3}.

For the sake of completeness, let us describe this platypus algorithm. Take a polynomial L(z) of degree n with constant term 1, and define U_{1}, …, U_{n} implicitly by

L(z) = ∏_{k=1}^{n}(1 − zU_{k}).

The algorithm gives a polynomial expression of

Q(z) = ∏_{|I|=a}(1 − zU_{I}) = ∑_{k=0}^{d}(−z)^{k}e_{k}[e_{a}](U)

with d = \binom{n}{a} and U = (U_{1}, …, U_{n}). The only general identity that is needed is the expansion of e_{a} in power sums. This can be obtained from a series expansion via

e_{a} = [z^{a}] exp (− ∑_{i≥1} \frac{(−z)^{i}}{i} p_{i}) = Φ_{a}(p_{1}, …, p_{a})  (10)

for some polynomial Φ_{a}. The rest of the calculation also uses series expansions, and goes as follows:

• compute p_{i}(U) for 1 ≤ i ≤ ad using p_{i}(U) = i[z^{i}] log(1/L(z)), • compute log Q(z) up to the coefficient of z^{d} using

log Q(z) = − ∑_{i≥1} \frac{z^{i}}{i} Φ_{a}(p_{i}(U), p_{2i}(U), …, p_{ai}(U)),  (11)

• compute Q(z) up to the coefficient of z^{d} using Q(z) = exp(log Q(z)). Since Q(z) has degree d, the calculation is complete. The identity (11) follows from (10) and

log Q(z) = − ∑_{i≥1} \frac{z^{i}}{i} ∑_{|I|=a} U_{I}^{i} = − ∑_{i≥1} \frac{z^{i}}{i} e_{a}(U_{1}^{i}, …, U_{n}^{i}).

Given a set of steps S, with max S = a, one obtains a polynomial expression of D(t, z) by applying the platypus algorithm to

L(z) = ∑_{s∈S} \frac{ω_{s}}{ω_{a}} z^{a−s} − \frac{z^{a}}{tω_{a}} .

If the output of the algorithm is the polynomial Q(z), then D(t, z) = Q((−1)^{a+1}tω_{a}z).

Example 1: Two step excursions. The simplest walks we can consider are obtained for S = {−b, a} and ω_{a} = ω_{−b} = 1. We always assume that a and b are coprime.

If b = 1, Proposition 1 gives E = U/t, where U is the only power series satisfying U = t(1+U^{a+1}). Equivalently, E = 1+t^{a+1}E^{a+1}. This equation can be understood combinatorially by looking at the first visit of the walk at levels a, a − 1, …, 1, 0, and factoring the walk at these points. Of course, a similar result holds when a = 1.

If a, b > 1, it is still possible, but more difficult, to write directly a system of polynomial equations, based on factorizations of the walks, that define the series E. See for instance [15, 21, 22, 24]. It would be interesting to work out the precise link between the components of these systems and the series U_{i}. To compare both types of results, take a = 3 and b = 2. On the one hand, it is shown in [15] that E is the first component of the solution of

\{ \begin{matrix}E & = & 1 + L_{1}R_{1} + L_{2}R_{2} & L_{1} & = & L_{2}R_{1} + L_{3}R_{2} \\ R_{1} & = & L_{1}R_{2} & L_{2} & = & L_{3}R_{1} \\ R_{2} & = & tE & L_{3} & = & tE. \end{matrix}

On the other hand, Proposition 1 gives E = −U_{1}U_{2}/t, where U_{1}, U_{2} are the small roots of u^{2} = t(1 + u^{5}). The platypus algorithm gives D(t, E) = 0 with

D(t, z) = 1 − z + t^{5}z^{5}(2 − z + z^{2}) + t^{10}z^{10}.  (12)

This polynomial is irreducible. Similarly, for a = 4 and b = 3, D(t, E) = 0 with

D(t, z) = 1 − z + t^{7}z^{7} (5 − 4 z + z^{2} + 3 z^{3} − z^{5} + z^{6})

+ t^{14}z^{14} (10 − 6 z + 3 z^{2} + 5 z^{3} − z^{4} + z^{5})

+ t^{21}z^{21} (10 − 4 z + 3 z^{2} + z^{3} − z^{4}) + t^{28}z^{28} (5 − z + z^{2} − z^{3}) + z^{35}t^{35}. (13)

We prove in Section 6 that, in the case of two step walks, D(t, z) is always irreducible. That is, the degree of E is exactly \binom{a+b}{a}.

Example 2: Playing basket-ball with A. and Z. In a recent paper [2], the authors consider excursions with steps in {±1, ±2}, where the steps ±2 have length 2 rather than 1. They use factorizations of walks to count excursions (more specifically, excursions of bounded height). This problem fits in our framework by choosing ω_{−2} = ω_{2} = ω and ω_{−1} = ω_{1} = 1, and then specializing ω = t. Observe that the small roots of u^{2} = t(ω+u+u^{3}+ωu^{4}), involved in Proposition 1, specialize into the small roots U_{1} and U_{2} of u^{2} = t(t + u + u^{3} + tu^{4}) when ω is set to t. We obtain E = −U_{1}U_{2}/t^{2}. The platypus algorithm yields

D(t, z) = D̄(t, z)(1 + t^{2}z)^{2},  (14)

where

D̄(t, z) = t^{8}z^{4} − t^{4} (1 + 2 t^{2}) z^{3} + t^{2} (3 + 2 t^{2}) z^{2} − (1 + 2 t^{2}) z + 1  (15)

is the minimal polynomial of E. This factorization is an interesting phenomenon, which is not related to the unequal lengths of the steps. Indeed, the same phenomenon occurs when S = {±1, ±2} and all weights are 1. In this case, one finds:

D(t, z) = D̄(t, z)(1 + tz)^{2}

with D̄(t, z) = t^{4}z^{4} − t^{2}(2t + 1)z^{3} + t(3t + 2)z^{2} − (2t + 1)z + 1,

so that the excursion generating function has degree 4 again.

The factorization of D(t, z) is due to the symmetry of the set of steps. For each set S such that S = −S and weights ω_{s} such that ω_{s} = ω_{−s}, the polynomial P (u) given by (3) is symmetric in u and 1/u. In particular, a = b. This implies that the small and large roots of 1−tP (u) can be grouped by pairs: U_{a+1} = 1/U_{1}, …, U_{2a} = 1/U_{a}. In particular, if a is even, the polynomial D(t, z) given by (7) contains the factor (1 + tω_{a}z) at least \binom{a}{a/2} times. In the basket-ball case (a = 2), this explains the factor (1 + tz)^{2} occurring in D(t, z). More generally, we prove in Section 7 that if S is symmetric, with symmetric weights, then the degree of E is at most 2^{a}, where a = max S.

2.2. Excursions of bounded height

We now turn our attention to the enumeration of excursions of height at most k. These are walks on a finite directed graph, so that the classical transfer-matrix method applies^{2}. The vertices of the graph are 0, 1, …, k, and there is an edge from i to j if j − i ∈ S. The adjacency matrix of this graph is A^{(k)} = (A_{i,j})_{0≤i,j≤k} with

A_{i,j} = \{ \begin{matrix}ω_{j−i} & if j − i ∈ S, \\ 0 & otherwise. \end{matrix}  (16)

2In language theoretic terms, the words of S^{∗} that encode these bounded excursions are recognized by a finite automaton.

By considering the nth power of A^{(k)}, it is easy to see [29, Ch. 4] that the series E^{(k)} counting excursions of height at most k is the entry (0, 0) in (1 − tA^{(k)})^{−1}. The translational invariance of our step system gives

E^{(k)} = \frac{F_{k}}{F_{k+1}}

where F_{0} = 1 and F_{k+1} is the determinant of 1 − tA^{(k)}. The size of this matrix, k + 1, grows with the height.

As was already observed in [3], the series counting walks confined in a strip of fixed height can also be expressed using determinants of size a+b, where a = max S and −b = min S. However, the expressions given in the above reference are heavy. A different route yields determinants that are Schur functions in the series U_{i} (recall that these series are the roots of the polynomial K(u) given by (4)). This was shown in [7] for the enumeration of culminating walks. The case of excursions is even simpler, as it only involves rectangular Schur functions.

Let us recall the definition of Schur functions in n variables x_{1}, …, x_{n}. Let δ = (n − 1, n − 2, …, 1, 0). For any integer partition λ with at most n parts, λ = (λ_{1}, …, λ_{n}) with λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} ≥ 0,

s_{λ}(x_{1}, …, x_{n}) = \frac{a_{δ+λ}}{a_{δ}} , with a_{μ} = det (x_{i}^{μ_{j}})_{1≤i,j≤n} .  (17)

Proposition 2. The generating function of excursions of height at most k is

E^{(k)} = \frac{F_{k}}{F_{k+1}} = \frac{(−1)^{a+1}}{tω_{a}} \frac{s_{k^{a}}(U)}{s_{(k+1)^{a}}(U)}

where U = (U_{1}, …, U_{a+b}) is the collection of roots of the polynomial K(u) given by (4), and F_{k+1} = det(1 − tA^{(k)}) where A^{(k)} is the adjacency matrix (16). In particular,

F_{k} = (−1)^{k(a+1)}(tω_{a})^{k}s_{k^{a}}(U).  (18)

This proposition is proved in Section 4 in two different ways. In Section 5, we derive from the Schur expression of F_{k} that these polynomials satisfy a linear recurrence relation. Equivalently, the generating function ∑_{k} F_{k}z^{k} is a rational function of t and z.

Proposition 3. The generating function of the polynomials F_{k} is rational, and can be written as

∑_{k≥0} F_{k}z^{k} = \frac{N(t, z)}{D(t, z)}

where D(t, z) is given by (7), and N(t, z) has degree \binom{a+b}{a} − a − b in z. Moreover,

D(t, E) = 0 and N(t, E) ≠ 0.

In other words, the sequence F_{k} satisfies a linear recurrence relation of the form (1), of order d_{a,b} = \binom{a+b}{a}, valid for k > \binom{a+b}{a} − a − b (with F_{i} = 0 for i < 0). This proposition follows from Proposition 4 (Section 5), which deals with the generating function of rectangular Schur functions of height a: for symmetric functions in n variables,

∑_{k} s_{k^{a}}z^{k} = \frac{P (z)}{Q(z)}  (19)

where Q(z) is given by (8) and has degree \binom{n}{a}, while P (z) has degree \binom{n}{a} − n.

Computational aspects. We have shown in Section 2.1 that, given the step set S, the polynomial D(t, z) can be computed via the platypus algorithm. One way to determine the numerator N(t, z) is to compute F_{k} explicitly (e.g. as the determinant of (1 − tA^{(k)})) for k ≤ δ := \binom{a+b}{a} − a − b, and then to compute N(t, z) = D(t, z) ∑_{k} F_{k}z^{k} up to the coefficient of z^{δ}.

In the generic case, computing the generating function of the polynomials F_{k} boils down to computing the generating function (19). As discussed above, the platypus algorithm can be used to determine Q(z) in terms of the elementary symmetric functions. In order to determine P (z), we express the Schur functions s_{k^{a}}, for k ≤ δ := \binom{n}{a} − n, in the elementary basis. This can be done using the dual Jacobi–Trudi identity (see Section 5 for details). One finally obtains P (z) by expanding the product Q(z) ∑_{k} s_{k^{a}}z^{k} in the elementary basis up to order δ. For instance, for a = b = 2,

∑_{k≥0} s_{k^{a}}z^{k} = \frac{1 − z^{2}e_{4}}{Q(z)} ,

where Q(z) is given by (9). More values of P (z) are given in Section 7.2. Let us now revisit the examples of Section 2.1.

Example 1: Two step excursions. When S = {a, −1}, one has D(t, z) = 1−z+ t^{a+1}z^{a+1}. The polynomials F_{k} satisfy the recursion F_{k} = F_{k−1} − t^{a+1}F_{k−a−1}, which can be understood combinatorially using Viennot’s theory of heaps of pieces [33]. Via this theory, F_{k} appears as the generating function of trivial heaps of segments of length a on the line ⟦0, k⟧, each segment being weighted by −t^{a+1}. The recursion is valid for k ≥ 1, with F_{0} = 1 and F_{i} = 0 for i < 0. The generating function of the F_{k}’s is

∑_{k≥0} F_{k}z^{k} = \frac{1}{1 − z + t^{a+1}z^{a+1}} .

When a = 3 and b = 2, the minimal polynomial of the excursion series E is given by (12) and the generating function of the polynomials F_{k} is found to be

∑_{k≥0} F_{k}z^{k} = \frac{1 + t^{5}z^{5}}{1 − z + t^{5}z^{5}(2 − z + z^{2}) + t^{10}z^{10}} .

For a = 4 and b = 3, we refer to (13) for the minimal polynomial D(t, z) of E, and

∑_{k≥0} F_{k}z^{k} = \frac{1 + t^{7}z^{7} (4 + z^{3} + z^{4}) + t^{14}z^{14} (6 + z^{3}) + 4 t^{21}z^{21} + t^{28}z^{28}}{D(t, z)} .

Example 2: Basket-ball again. For S = {±1, ±2} with ω_{−2} = ω_{2} = t, ω_{−1} = ω_{1} = 1,

∑_{k≥0} F_{k}z^{k} = \frac{1 − t^{2}z}{(1 + t^{2}z) (1 − z(1 + 2t^{2}) + z^{2}t^{2}(3 + 2t^{2}) − z^{3}t^{4}(1 + 2 t^{2}) + z^{4}t^{8})}.

The denominator is not irreducible. Its second factor is the minimal polynomial of E, see (15). Moreover, comparing to (14) shows that N(t, z) and D(t, z) have a factor (1 + t^{2}z) in common. A similar phenomenon occurs for S = {±1, ±2} with ω_{s} = 1 for all s. In this case,

∑_{k≥0} F_{k}z^{k} = \frac{1 − tz}{(1 + zt) (1 − z (1 + 2 t) + t (2 + 3 t) z^{2} − t^{2} (1 + 2 t) z^{3} + z^{4}t^{4})}.

Again, the minimal polynomial of E is the second factor of the denominator, and N(t, z) and D(t, z) have a factor (1 + tz) in common.

3. Enumeration of unbounded excursions

Here we establish the expression (6) of the excursion generating function E. The proof is based on a step-by step construction of non-negative walks with steps in S, and on the so-called kernel method. This type of argument is by no means original. The proof that we are going to present can be found in [6, Example 3], then in [5], and finds its origin in [20, Ex. 2.2.1.4 and 2.2.1.11]. The reason why we repeat the proof is because it will be adapted in Section 4 to count excursions of bounded height.

Let W be the set of walks that start from 0, take their steps in S, and always remain at a non-negative level. Let W (t, u) be their generating function, where the variable t counts the length, the variable u counts the final height, and each step s ∈ S is weighted by ω_{s}:

W (t, u) = ∑_{(s_{1},s_{2},...,s_{n})∈W} ω_{s_{1}} ⋯ ω_{s_{n}}t^{n}u^{s_{1}+···+s_{n}}.

We often denote W (t, u) ≡ W (u), and use the notation W_{h} for the generating function of walks of W ending at height h:

W (t, u) = ∑_{h≥0} u^{h}W_{h} where W_{h} = _{∑_{(s_{1},s_{2},...,s_{n})∈W} ; s_{1}+···+s_{n}=h}ω_{s_{1}} ⋯ ω_{s_{n}}t^{n}.

A non-empty walk of W is obtained by adding a step of S at the end of another walk of W. However, we must avoid adding a step i to a walk ending at height j, if i + j < 0. This gives

W (u) = 1 + t (∑_{s∈S} ω_{s}u^{s}) W (u) − t_{∑_{i∈S,j≥0} ; i+j<0}ω_{i}u^{i+j}W_{j}.

Let min S = −b. Rewrite the above equation so as to involve only non-negative powers of u:

u^{b}(1 − tP (u))W (u) = u^{b} − t ∑_{h=1}^{b} u^{b−h}_{∑_{i∈S,j≥0} ; i+j=−h}ω_{i}W_{j},  (20)

with P (u) = ∑_{s∈S} ω_{s}u^{s}. The coefficient of W (u) is the kernel K(u) of the equation, given in (4). As above, we denote by U_{1}, …, U_{b} (respectively U_{b+1}, …, U_{a+b}) the roots of K(u) that are finite (respectively infinite) at t = 0. For 1 ≤ i ≤ b, the series W (U_{i}) is well-defined (it is a formal power series in t^{1/b}). The left-hand side of (20) vanishes for u = U_{i}, with i ≤ b, and so the right-hand side vanishes too. But the right-hand side is a polynomial in u, of degree b, leading coefficient 1, and it vanishes at u = U_{1}, …, U_{b}. This gives

u^{b}(1 − tP (u))W (u) = ∏_{i=1}^{b}(u − U_{i}).

As the coefficient of u^{0} in the kernel is −tω_{−b}, setting u = 0 in the above equation gives the generating function of excursions:

E = W (0) = \frac{(−1)^{b+1}}{tω_{−b}} ∏_{i=1}^{b} U_{i}.

This is the first expression in (6). The second follows using

U_{1} ⋯ U_{a+b} = (−1)^{a+b}ω_{−b}/ω_{a}  (21)

(see (5)).

Remark. There exists an alternative way to solve (20), which does not exploit the fact that the right-hand side of (20) has degree b in u. This variant will be useful in the enumeration of bounded excursions. Write

Z_{−h} = _{∑_{i∈S,j≥0} ; i+j=−h}ω_{i}W_{j},

so that the right-hand side of (20) reads

u^{b} − t ∑_{h=1}^{b} u^{b−h}Z_{−h}.

This term vanishes for u = U_{1}, …, U_{b}. Hence the b series Z_{−1}, …, Z_{−b} satisfy the following system of b linear equations: For U = U_{i}, with 1 ≤ i ≤ b,

∑_{h=1}^{b} U^{b−h}Z_{−h} = U^{b}/t.

In matrix form, we have MZ = C/t, where M is the square matrix of size b given by

M = ( \begin{matrix}U_{1}^{b−1} & U_{1}^{b−2} & ⋯ & U_{1}^{1} & 1 \\ U_{2}^{b−1} & U_{2}^{b−2} & ⋯ & U_{2}^{1} & 1 \\ ⋮ & & & & ⋮ \\ U_{b}^{b−1} & U_{b}^{b−2} & ⋯ & U_{b}^{1} & 1 \end{matrix} ) ,

Z is the column vector (Z_{−1}, …, Z_{−b}), and C is the column vector (U_{1}^{b}, …, U_{b}^{b}). The determinant of M is the Vandermonde in U_{1}, …, U_{b}, and it is non-zero because the U_{i} are distinct. We are especially interested in the unknown Z_{−b} = ω_{−b}E. Applying Cramer’s rule to solve the above system yields

Z_{−b} = \frac{(−1)^{b+1}}{t} \frac{det(U_{i}^{b−j+1})_{1≤i,j≤b}}{det(U_{i}^{b−j})_{1≤i,j≤b}} .

The two determinants coincide, up to a factor U_{1} … U_{b}, and we finally obtain

E = \frac{Z_{−b}}{ω_{−b}} = \frac{(−1)^{b+1}}{tω_{−b}} U_{1} ⋯ U_{b}.

4. Enumeration of bounded excursions

As argued in Section 2.2, the generating function of excursions of height at most k is

E^{(k)} = \frac{F_{k}}{F_{k+1}} ,  (22)

where F_{k+1} = det(1 − tA^{(k)}) and A^{(k)} is the adjacency matrix (16) describing the allowed steps in the interval ⟦0, k⟧. In order to prove Proposition 2, it remains to establish the expression (18) of the polynomial F_{k} as a Schur function of U_{1}, …, U_{a+b}. We give two proofs. The first one uses the dual Jacobi–Trudi identity to identify F_{k} as a Schur function. The second determines E^{(k)} in terms of Schur functions via the kernel method, and the Schur expression of F_{k} then follows from (22) by induction on k (given that F_{0} = 1).

First proof via the Jacobi–Trudi identity. The dual Jacobi–Trudi identity expresses Schur functions as a determinant in the elementary symmetric functions e_{i} [30, Cor. 7.16.2]: for any partition λ,

s_{λ} = det (e_{λ′_{j}+i−j})_{1≤i,j≤λ_{1}} ,

where λ′ is the conjugate of λ. Apply this identity to λ = (k +1)^{a}. Then λ′ = a^{k+1} and

s_{(k+1)^{a}} = det J^{(k)} with J^{(k)} = (e_{a+i−j})_{1≤i,j≤k+1}.

Now, specialize this to symmetric functions in the a+b variables V = (V_{1}, …, V_{a+b}) where V_{i} = −U_{i} for all i. By (5), the elementary symmetric functions of the V_{i} are

e_{i}(V) = \frac{ω_{a−i}}{ω_{a}} − \frac{1}{tω_{a}} χ_{i=a} = −\frac{1}{tω_{a}} (χ_{i=a} − tω_{a−i}) .

This shows that the matrix J^{(k)} coincides with −(1 − tA^{(k)})/(tω_{a}), so that

s_{λ}(V) = (−tω_{a})^{−(k+1)}F_{k+1} = (−1)^{a(k+1)}s_{λ}(U),

since s_{λ} is homogeneous of degree a(k + 1). This gives the Schur expression of F_{k+1}.

Second proof via the kernel method. We adapt the step by step approach of Section 3 to count excursions of height at most k. Let W^{(k)}(t, u) ≡ W^{(k)}(u) be the generating function of non-negative walks of height at most k. As before, we count them by their length (variable t) and final height (u) with multiplicative weights ω_{s} on the steps. We use notations similar to those of Section 3. When constructing walks step by step, we must still avoid going below level 0, but also above level k. This yields:

W^{(k)}(u) = 1 + t (∑_{s∈S} ω_{s}u^{s}) W^{(k)}(u) − t_{∑_{i∈S,j≥0} ; i+j>k or i+j<0}ω_{i}u^{i+j}W_{j}^{(k)},

or, with min S = −b,

u^{b}(1 − tP (u))W^{(k)}(u) = u^{b} − t ∑_{h=k+1}^{k+a} u^{b+h}Z_{h}^{(k)} − t ∑_{h=1}^{b} u^{b−h}Z_{−h}^{(k)},  (23)

where

Z_{h}^{(k)} = _{∑_{i∈S,j≥0} ; i+j=h}ω_{i}W_{j}^{(k)}.

The series W^{(k)}(u) is now a polynomial in u (with coefficients in the ring of power series in t). This implies that any root U_{i} of the kernel K(u) = u^{b}(1 − tP (u)) can be legally substituted for u in (23). The right-hand side and the left-hand side then vanish, and provide a system of a + b linear equations satisfied by the Z_{h}: For U = U_{i}, with 1 ≤ i ≤ a + b,

∑_{h=k+1}^{k+a} U^{b+h}Z_{h}^{(k)} + ∑_{h=1}^{b} U^{b−h}Z_{−h}^{(k)} = U^{b}/t.

In matrix form, we have M^{(k)}Z^{(k)} = C/t, where M^{(k)} is the square matrix of size a + b given by

M^{(k)} = ( \begin{matrix}U_{1}^{a+b+k} & U_{1}^{a+b+k−1} & ⋯ & U_{1}^{b+k+1} & U_{1}^{b−1} & U_{1}^{b−2} & ⋯ & 1 \\ U_{2}^{a+b+k} & ⋯ & & & & & ⋯ & 1 \\ ⋮ & & & & & & & ⋮ \\ U_{a+b}^{a+b+k} & U_{a+b}^{a+b+k−1} & ⋯ & U_{a+b}^{b+k+1} & U_{a+b}^{b−1} & U_{a+b}^{b−2} & ⋯ & 1 \end{matrix} ) ,

Z^{(k)} is the column vector (Z_{k+a}^{(k)}, …, Z_{k+1}^{(k)}, Z_{−1}^{(k)}, …, Z_{−b}^{(k)}), and C is the column vector (U_{1}^{b}, …, U_{a+b}^{b}). We are especially interested in the series Z_{−b}^{(k)} = ω_{−b}E^{(k)}.

Cramer’s rule now gives

Z_{−b}^{(k)} = \frac{(−1)^{b+1}}{t} \frac{det(U_{i}^{a+b+k}, …, U_{i}^{b+k+1}, U_{i}^{b}, U_{i}^{b−1}, …, U_{i})_{1≤i≤a+b}}{det M^{(k)}} , (24)

provided det M^{(k)} ≠ 0. In view of the definition (17) of Schur functions, this yields:

E^{(k)} = \frac{Z_{−b}^{(k)}}{ω_{−b}} = \frac{(−1)^{b+1}}{tω_{−b}} U_{1} ⋯ U_{a+b} \frac{s_{k^{a}}(U)}{s_{(k+1)^{a}}(U)}.

Thanks to (21), the generating function of excursions of height at most k can finally be rewritten

E^{(k)} = \frac{(−1)^{a+1}}{tω_{a}} \frac{s_{k^{a}}(U)}{s_{(k+1)^{a}}(U)}.

Using (22), we finally express the polynomial F_{k} in terms of Schur functions:

F_{k} = \frac{1}{E^{(0)} ⋯ E^{(k−1)}} = (−1)^{k(a+1)}(tω_{a})^{k}s_{k^{a}}(U).

We still have to prove that the determinant of M^{(k)} is non-zero. Whether M^{(k)} is singular or not, the following variant of (24) remains valid:

det M^{(k)}Z_{−b}^{(k)} = \frac{(−1)^{b+1}}{t} det(U_{i}^{a+b+k}, …, U_{i}^{b+k+1}, U_{i}^{b}, U_{i}^{b−1}, …, U_{i})_{1≤i≤a+b}

= \frac{(−1)^{b+1}}{t} V (U) s_{k^{a}}(U) ∏_{i=1}^{a+b} U_{i},

where V (U) denotes the Vandermonde in the U_{i}’s. Since these series are distinct and non-zero, this shows that if det M^{(k)} = 0, that is, s_{(k+1)^{a}}(U) = 0, then s_{k^{a}}(U) = 0 as well. But this would finally imply s_{0}(U) = 0, while s_{0}(U) = 1. Thus det M^{(k)} ≠ 0, and the second proof of Proposition 2 is now complete.

5. Generating functions of rectangular Schur functions

We will now prove Proposition 3, which connects the (algebraic) excursion generating function E to the polynomials F_{k} occurring in the (rational) generating function E^{(k)} counting excursions of height at most k. Now that we have expressed F_{k} as a Schur function (18), Proposition 3 will be a consequence of the following result.

Proposition 4. Let 1 ≤ a ≤ n. The generating function of rectangular Schur functions of length a in n variables u_{1}, …, u_{n} is

∑_{k≥0} s_{k^{a}}z^{k} = \frac{P (z)}{Q(z)}

where

Q(z) = ∏_{I⊂⟦n⟧, |I|=a} (1 − zu_{I}) = ∑_{k≥0}(−1)^{k}z^{k}e_{k}[e_{a}]  (25)

has degree \binom{n}{a} in z and P (z) has degree \binom{n}{a} − n. (We have used the notation u_{I} = ∏_{i∈I} u_{i}.) Moreover, for all J of cardinality a,

P (1/u_{J}) = ∏_{I:|I|=a,|IΔJ|≥4}(1 − u_{I}/u_{J}).  (26)

Proof. Let us write n = a + b. By definition of Schur functions,

s_{k^{a}} = \frac{1}{V_{n}} det ((u_{i}^{n+k−1}, ⋯, u_{i}^{b+k}, u_{i}^{b−1}, ⋯, 1)_{1≤i≤n}) ,  (27)

where V_{n} = ∏_{1≤i<j≤n}(u_{i} − u_{j}). Thus

∑_{k≥0} s_{k^{a}}z^{k} = \frac{1}{V_{n}} ∑_{k≥0} z^{k} ∑_{σ∈𝔖_{n}} ε(σ) σ (u_{1}^{n+k−1} ⋯ u_{a}^{b+k}u_{a+1}^{b−1} ⋯ u_{n−1}^{1}u_{n}^{0}) (28)

= \frac{1}{V_{n}} ∑_{σ∈𝔖_{n}} ε(σ) σ (\frac{u_{1}^{n−1} ⋯ u_{a}^{b}u_{a+1}^{b−1} ⋯ u_{n−1}^{1}u_{n}^{0}}{1 − zu_{1} ⋯ u_{a}} ) ,

where σ acts on functions of u_{1}, …, u_{n} by permuting the variables:

σF (u_{1}, …, u_{n}) = F (u_{σ(1)}, …, u_{σ(n)}).

Equivalently,

∑_{k≥0} s_{k^{a}}z^{k} = \frac{P (z)}{Q(z)}

where Q(z) is given by (25) and

P (z) = \frac{1}{V_{n}} ∑_{σ∈𝔖_{n}} ε(σ) σ (u_{1}^{n−1} ⋯ u_{n}^{0} ∏_{|I|=a,I≠⟦a⟧} (1 − zu_{I})) .  (29)

The above expression suggests that the degree of P (z) could be as large as \binom{n}{a}−1, while we claim it is only \binom{n}{a} − n. To explain this gap, it suffices to notice that the determinant (27) vanishes for k ∈ {−n + 1, −n + 2, …, −1}. Thus the sum over k in the right-hand side of (28) could just as well start at k = −n + 1, giving:

z^{n−1} ∑_{k≥0} s_{k^{a}}z^{k} = \frac{1}{V_{n}} ∑_{σ∈𝔖_{n}} ε(σ) σ (\frac{u_{1}^{0}u_{2}^{−1} ⋯ u_{a}^{−a+1}u_{a+1}^{b−1} ⋯ u_{n−1}^{1}u_{n}^{0}}{1 − zu_{1} ⋯ u_{a}} ) .

This provides the following alternative expression of P (z):

z^{n−1}P (z) = \frac{1}{V_{n}} ∑_{σ∈𝔖_{n}} ε(σ) σ (u_{1}^{0}u_{2}^{−1} ⋯ u_{a}^{−a+1}u_{a+1}^{b−1} ⋯ u_{n−1}^{1}u_{n}^{0} ∏_{|I|=a,I≠⟦a⟧} (1 − zu_{I})) .

(30)

The right-hand side is a polynomial in z of degree (at most) \binom{n}{a} − 1, and this polynomial is the product of P (z) and z^{n−1}. This shows that P (z) has degree at most \binom{n}{a} − n. Moreover, by extracting the coefficient of z^{\binom{n}{a}−1} in the above identity, one finds:

[z^{\binom{n}{a}−n}]P (z) = \frac{1}{V_{n}} ∑_{σ∈𝔖_{n}} ε(σ) σ (u_{1}^{0}u_{2}^{−1} ⋯ u_{a}^{−a+1}u_{a+1}^{b−1} ⋯ u_{n−1}^{1}u_{n}^{0} ∏_{|I|=a,I≠⟦a⟧} (−u_{I})) .

Up to a sign and a power of u_{1} ⋯ u_{n}, the sum over σ is the Vandermonde in the u_{i}’s. Finally,

[z^{\binom{n}{a}−n}]P (z) = (−1)^{\binom{n}{a}+ab−1} (u_{1} ⋯ u_{n})^{\binom{n−1}{a−1}−a} ,  (31)

so that P (z) has degree \binom{n}{a} − n exactly.

It remains to determine P (1/u_{J}), for |J| = a. We specialize the expression (29) of P (z) to the case z = 1/u_{J}. The only permutations σ having a non-zero contribution are those such that σ(⟦a⟧) = J. Every such permutation σ can be written in a unique way σ = πτσ_{J}, where σ_{J} is the shortest permutation sending ⟦a⟧ to J, and τ (respectively π) is any permutation on J (respectively ^{c}J). Thus, if J = {j_{1}, …, j_{a}} with j_{1} < … < j_{a} and ^{c}J = {k_{1}, …, k_{b}} with k_{1} < … < k_{b}, we have

P (1/u_{J}) = ∏_{|I|=a,I≠J} (1 − u_{I}/u_{J}) \frac{ε(σ_{J})}{V_{n}}

× ∑_{τ∈𝔖(J)}ε(τ)τ (u_{j_{1}}^{n−1} ⋯ u_{j_{a}}^{b}) ∑_{π∈𝔖(^{c}J)}ε(π)π (u_{k_{1}}^{b−1} ⋯ u_{k_{b}}^{0})

= ∏_{|I|=a,I≠J} (1 − u_{I}/u_{J}) \frac{ε(σ_{J})}{V_{n}} u_{J}^{b} V (J) V (^{c}J),

where V (J) denotes the Vandermonde in the variables u_{j}, j ∈ J. This is easily seen to be equivalent to (26).

We can now complete the proof of Proposition 3. We combine the Schur expression of F_{k} given in Proposition 2 with Proposition 4. Set n = a + b. The indeterminates u_{1}, …, u_{a+b} are specialized to U_{1}, …, U_{a+b}, and we obtain:

∑_{k≥0} F_{k}z^{k} = \frac{P ((−1)^{a+1}tω_{a}z)}{Q((−1)^{a+1}tω_{a}z)} = \frac{N(t, z)}{D(t, z)}

where D(t, z) = Q((−1)^{a+1}tω_{a}z) is exactly the polynomial (7). The dominant coefficient of P (z), given by (31), does not vanish when specializing u_{i} to U_{i}. Thus N(t, z) = P ((−1)^{a+1}tω_{a}z) has degree \binom{n}{a} − n exactly. We have already seen that the excursion generating function E given in Proposition 1 satisfies D(t, E) = 0. Now, since E = (−1)^{a+1}/(tω_{a}U_{J}), with J = {b + 1, …, a + b},

N(t, E) = P (1/U_{J}) = ∏_{|I|=a,|IΔJ|≥4} (1 − U_{I}/U_{J})

by (26). Recall that U_{b+1}, …, U_{a+b} are the roots of K(u) with valuation −1/a, while the b other roots have valuation 1/b. This implies that U_{I} ≠ U_{J} for I ≠ J, so that N(t, E) ≠ 0.

6. The degree of the excursion generating function

We conclude this paper by proving that the results stated in Section 2 are, in a sense, optimal. We have defined in (7) a polynomial D(t, z), of degree d_{a,b} = \binom{a+b}{a}, which satisfies D(t, E) = 0 and is the denominator of the rational series ∑_{k} F_{k}z^{k}. We prove that D(t, z) is irreducible in the following two cases:

• S = ⟦−b, a⟧ and ω_{−b}, …, ω_{a} are independent indeterminates,

• S = {−b, a} with ω_{−b} = ω_{a} = 1 and a and b coprime.

In the first case, the kernel K(u) is essentially the general algebraic equation of degree a + b, so that the result may be predictable. The idea is that there are no non-trivial relations between the series U_{i}. The second case is less obvious.

Proposition 5. In the above two cases, the generating function of excursions with steps in S is algebraic of degree d_{a,b} = \binom{a+b}{a}. Its minimal polynomial is given by (7).

Recall, from Example 2 in Section 2.1, that E has sometimes degree less than d_{a,b} (for instance when S = {±1, ±2} with weights 1).

The key tool is the study of the Galois group of the polynomial K(u). We begin with a condition implying the irreducibility of D(t, z).

Lemma 6. Let S be a finite set of steps with weights ω_{s} ∈ 𝕂. Let a = max S, −b = min S and n = a + b. Let K(u) be the polynomial in u, with coefficients in 𝕂(t), defined by (4).

If the Galois group of K(u) over 𝕂(t), seen as a permutation group of the U′_{i}s, is the full symmetric group 𝔖_{n}, then the product U_{1} … U_{b} of the small roots of K(u) has degree d_{a,b} = \binom{a+b}{a}. In other words, the polynomial D(t, z) given by (7) is irreducible.

Proof. The extension 𝕂(t, U_{1}, …, U_{n}) of 𝕂(t) is normal by construction, and separable since we have assumed 𝕂 to be of characteristic 0. Assume that the Galois group of 𝕂(t, U_{1}, …, U_{n}) over 𝕂(t) is 𝔖_{n}. By the main result of Galois theory, the correspondence Φ between subgroups G of 𝔖_{n} and sub-extensions 𝕃 of 𝕂(t, U_{1}, …, U_{n}) defined by

Φ(G) = 𝕃 = {x ∈ 𝕂(t, U_{1}, …, U_{n}) : σ(x) = x for all σ ∈ G}

is bijective. Its inverse is given by

Φ^{−1}(𝕃) = G = {σ ∈ 𝔖_{n} : σ(x) = x for all x ∈ 𝕃}.

Moreover, the degree of 𝕂(t, U_{1}, …, U_{n}) over 𝕃 is |G|.

In particular, let 𝕃 = 𝕂(t, U_{1} ⋯ U_{b}) be the extension of 𝕂(t) generated by the product of the small roots. Given that U_{1}, …, U_{b} have valuation 1/b in t, while U_{b+1}, …, U_{a+b} have valuation −1/a, the only permutations σ of 𝔖_{n} that leave U_{1} … U_{b} unchanged are those that fix the set ⟦b⟧. That is, Φ^{−1}(𝕃) ≃ 𝔖_{b} × 𝔖_{a}.

Thus 𝕂(t, U_{1}, …, U_{n}) has degree a!b! over 𝕃, degree (a + b)! over 𝕂(t), so that 𝕃 = 𝕂(t, U_{1} ⋯ U_{b}) has degree \binom{a+b}{a} over 𝕂(t).

We now apply the above lemma to prove Proposition 5. Proof of Proposition 5. In the first case, K(u) is the general equation of degree n = a + b. It is well-known that its Galois group is 𝔖_{n}. See for instance [31].

In the second case, we want to prove that the Galois group of K(u) = u^{b} − t(1 + u^{a+b}) over ℚ(t) is 𝔖_{n}, with n = a + b. This has been proved for trinomials u^{a+b} + αu^{b} + β with two indeterminate coefficients α and β (see [28, 11]), and for some trinomials with rational coefficients [25, 12]. The latter results are of course harder than the former. Given that we could not find any reference dealing with trinomials involving exactly one indeterminate coefficient, we will rely on the strong results obtained for trinomials of ℚ[u].

We first note that it suffices to prove that the trinomial u^{b} − t_{0}(1 + u^{a+b}) has Galois group 𝔖_{n} over ℚ for some rational number t_{0}. Since a and b are coprime, Theorem 8 of [27] implies that there exist only finitely many α ∈ ℤ such that u^{a+b} + αu^{b} + 1 is reducible. Thus we can choose α ∈ ℤ, coprime with n = a + b, and such that the above trinomial is irreducible. Then by [25, Thm. 1], this trinomial has Galois group 𝔖_{n} over ℚ.

7. Concluding remarks and questions

7.1. The degree of the excursion generating function

We have shown in Section 6 that the degree of E is maximal, equal to \binom{a+b}{a}, both in the generic case and in the two-step case. This can be extended to all set steps such that K(u) has at least two (algebraically independent) indeterminate coefficients, using the results of [11].

It would be interesting to study more cases, in particular those involving a symmetry, which reduces the degree. Assume S = −S, and ω_{−s} = ω_{s} for all s ∈ S. In particular, a = b. Then, as discussed in Example 2, the small and large roots of K(u) are simply related by U_{a+1} = 1/U_{1}, …, U_{2a} = 1/U_{a}. This implies that many products U_{i_{1}} ⋯ U_{i_{a}}, with i_{1} < ⋯ < i_{a}, are actually of the form U_{j_{1}} ⋯ U_{j_{a−2k}} for some k > 0. The products that reduce in that way have a minimal polynomial that strictly divides

Q(z) = ∏_{|I|=a}(1 − zU_{I}).

The non-reducing products U_{i_{1}} ⋯ U_{i_{a}} are the 2^{a} terms U_{I} = U_{1}^{±1} ⋯ U_{a}^{±1}. Thus

Q̄(z) = ∏_{ε∈{±1}^{a}}(1 − zU^{ε}),

is a polynomial in z and t that divides Q(z), and vanishes at z = E. Hence in the symmetric case, E has degree at most 2^{a}.

One could try to study systematically the cases S = ⟦−a, a⟧ or S = {±1, ±a}, with weights 1. When S = {±1, ±2}, we have seen in Example 2 that E has degree 4. The Galois group G of K(u) = u^{2} − t(1 + u)^{2}(1 − u + u^{2}) over ℚ(t) can be seen to be isomorphic to the dihedral group D_{4}. More precisely,

G = {id, (1, 2, 3, 4), (1, 4, 3, 2), (1, 3)(2, 4), (1, 2)(3, 4), (1, 4)(2, 3), (1, 3), (2, 4)}.

The subgroup that leaves U_{1}U_{2} invariant is the subgroup of index 4 generated by (1, 2)(3, 4). This explains why E = −U_{1}U_{2}/t has degree 4.

7.2. The generating function of rectangular Schur functions

We proved in Section 5 that, for symmetric functions in n variables, the generating function of rectangular Schur functions of height a is rational:

∑_{k≥0} s_{k^{a}}z^{k} = \frac{P (z)}{Q(z)},

where Q(z) is given by (25) and has degree \binom{n}{a}, while P (z) has degree \binom{n}{a}−n. We have given two expressions of P (z) in terms of the u_{i}’s (see (29–30)), and proved that P (1/u_{J}) has a simple expression (26). However, we have no expansion of P (z) in symmetric functions, other than

P (z) = ∑_{i=0}^{\binom{n}{a}−n} z^{i} ∑_{j+k=i}(−1)^{j}e_{j}[e_{a}] s_{k^{a}},

which comes directly from the fact that P (z) = Q(z) ∑_{k≥0} s_{k^{a}}z^{k}. It would be interesting to find a simpler expression for the coefficients of P (z). The term (−1)^{j}, in particular, leaves hope for possible simplifications, which may in turn allow us to compute P (z) more efficiently. Let us give the expression of P for a few values of a and n: for a = 2 and n = 4,

P (z) = 1 − e_{4}z^{2} = 1 − s_{4}z^{2}.

For a = 2 and n = 5,

P (z) = 1 − e_{4} z^{2} + e_{5,1} z^{3} − e_{5}^{2}z^{5} = 1 − s_{1^{4}}z^{2} + s_{2,1^{4}}z^{3} − s_{2^{5}}z^{5}.

For a = 3 and n = 6,

P (z) = 1 − s_{21^{4}}z^{2} + (s_{2^{4}1} + s_{321^{4}}) z^{3} − s_{3^{2}2^{2}1^{2}}z^{4} − (s_{3^{5}} + s_{52^{5}}) z^{5}

+ (s_{53^{3}2^{2}} + s_{4^{3}2^{3}} + s_{4^{2}3^{3}1}) z^{6} − 2 s_{54^{2}3^{2}2}z^{7} + (s_{5^{3}3^{3}} + s_{64^{3}3^{2}} + s_{5^{2}4^{3}2}) z^{8}

− (s_{5^{5}2} + s_{74^{5}}) z^{9} − s_{6^{2}5^{2}4^{2}}z^{10} + (s_{6^{4}54} + s_{765^{4}}) z^{11} − s_{76^{4}5}z^{12} + s_{7^{6}}z^{14}.

We have used the Schur basis rather than the elementary basis because it seems, from these examples, that the coefficient of z^{i} in P (z) is either Schur-positive or Schur-negative. The conversions to Schur functions have been made with the package ACE [32].

7.3. The height of random excursions

Equip the set of excursions of length n with the uniform distribution. It is known that the random excursion of length n thus obtained converges in law to the Brownian excursion, after normalizing the length by n and the height by κ\sqrt{n}, for some constant κ depending on S [18]. This implies that the (normalized) height of a discrete excursion converges in law to the height of the Brownian excursion (described by a theta distribution [19]). Is it possible to re-derive this limit law from our enumerative results?

Indeed, the average height of Dyck paths — equivalently, of plane trees — was derived in [13] from an expression of E^{(k)} that is equivalent to our Schur expression of this series (Proposition 2). The same expression was then used in [16] to obtain the limit law of the height. Is it possible, using the asymptotic tools developed in [5] for unbounded excursions, to work out the law of the height of general excursions by starting from our Schur expression of E^{(k)}?

Acknowledgements. I am indebted to Alain Lascoux and Christophe Carré for providing efficient programs to compute plethysms. I also thank Alain Salinier for interesting e-discussions about the Galois groups of trinomials, and for pointing out Reference [27].

References

[1] A. Ayyer and D. Zeilberger. Two dimensional directed lattice walks with boundaries.

arχiv:cond-mat/0701674v2.

[2] A. Ayyer and D. Zeilberger. The number of [old-time] basketball games with final score n n where the home team was never losing but also never ahead by more than w points. Electron. J. Combin., 14(1):Research Paper 19, 8 pp. (electronic), 2007. arχiv:math.CO/0610734.

[3] C. Banderier. Combinatoire analytique des chemins et des cartes. PhD thesis, Université Paris 6, 2001.

[4] C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps. Generating functions for generating trees. Discrete Math., 246(1-3):29–55, 2002.

[5] C. Banderier and P. Flajolet. Basic analytic combinatorics of directed lattice paths. Theoret. Comput. Sci., 281(1-2):37–80, 2002.

[6] M. Bousquet-Mélou and M. Petkovšek. Linear recurrences with constant coefficients: the multivariate case. Discrete Math., 225(1-3):51–75, 2000.

[7] M. Bousquet-Mélou and Y. Ponty. Culminating paths. arχiv:0706.0694v1.

[8] R. Brak, A. L. Owczarek, A. Rechnitzer, and S. G. Whittington. A directed walk model of a long chain polymer in a slit with attractive walls. J. Phys. A, 38(20):4309–4325, 2005.

[9] C. Carré. Plethysm of elementary functions. Bayreuth. Math. Schr., 31:1–18, 1990.

[10] Y. M. Chen, A. M. Garsia, and J. Remmel. Algorithms for plethysm. In Combinatorics and algebra (Boulder, Colo., 1983), volume 34 of Contemp. Math., pages 109–153. Amer. Math. Soc., Providence, RI, 1984.

[11] S. D. Cohen. The Galois group of a polynomial with two indeterminate coefficients. Pacific J. Math., 90(1):63–76, 1980. See also the erratum, Pacific J. Math. 97 (2):483–486, 1981.

[12] S. D. Cohen, A. Movahhedi, and A. Salinier. Galois groups of trinomials. J. Algebra, 222(2):561–573, 1999.

[13] N. G. de Bruijn, D. E. Knuth, and S. O. Rice. The average height of planted plane trees. In Graph theory and computing, pages 15–22. Academic Press, New York, 1972.

[14] A. de Mier and M. Noy. A solution to the tennis ball problem. Theoret. Comput. Sci., 346(2-3):254–264, 2005.

[15] P. Duchon. On the enumeration and generation of generalized Dyck words. Discrete Math., 225(1-3):121–135, 2000.

[16] P. Flajolet and A. Odlyzko. The average height of binary trees and other simple trees. J. Comput. System Sci., 25(2):171–213, 1982.

[17] I. M. Gessel. A factorization for formal Laurent series and lattice path enumeration. J. Combin. Theory Ser. A, 28(3):321–337, 1980.

[18] W. D. Kaigh. An invariance principle for random walk conditioned by a late return to zero. Ann. Probability, 4(1):115–121, 1976.

[19] D. P. Kennedy. The distribution of the maximum Brownian excursion. J. Appl. Probability, 13(2):371–376, 1976.

[20] D. E. Knuth. The art of computer programming, Vol. 1: Fundamental algorithms. Addison-Wesley Series in Computer Science and Information Processing, Reading, Mass.-London-Amsterdam, second edition, 1973.

[21] J. Labelle. Langages de Dyck généralisés. Ann. Sci. Math. Québec, 17(1):53–64, 1993.

[22] J. Labelle and Y. N. Yeh. Generalized Dyck paths. Discrete Math., 82(1):1–6, 1990.

[23] A. Lascoux. Symmetric functions and combinatorial operators on polynomials, volume 99 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 2003.

[24] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri. Underdiagonal lattice paths with unrestricted steps. Discrete Appl. Math., 91(1-3):197–213, 1999.

[25] H. Osada. The Galois groups of the polynomials X^{n}+aX^{l}+b. J. Number Theory, 25(2):230– 238, 1987.

[26] H. Prodinger. The kernel method: a collection of examples. Sém. Lothar. Combin., 50:Art. B50f, 19 pp. (electronic), 2003/04.

[27] A. Schinzel. On reducible trinomials. Dissertationes Math. (Rozprawy Mat.), 329:83, 1993.

[28] J. H. Smith. General trinomials having symmetric Galois group. Proc. Amer. Math. Soc., 63(2):208–212, 1977. See also the erratum, Proc. Amer. Math. Soc. 77 (2):298, 1979.

[29] R. P. Stanley. Enumerative combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1997.

[30] R. P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.

[31] I. Stewart. Galois Theory. Chapman & Hall/CRC, Boca Raton, FL, 2004.

[32] S. Veigneau. ACE, an Algebraic Combinatorics Environment for the computer algebra system MAPLE: User’s Reference Manual, Version 3.0. Report 98–11, IGM, 1998.

[33] G. X. Viennot. Heaps of pieces. I. Basic definitions and combinatorial lemmas. In Combinatoire énumérative (Montréal, Québec, 1985), volume 1234 of Lecture Notes in Math., pages 321–350. Springer, Berlin, 1986.

CNRS, LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France

  E-mail address: mireille.bousquet@labri.fr