Séminaire Lotharingien de Combinatoire, B57d (2008), 23 pp.

Mireille Bousquet-Mélou

Discrete Excursions

Abstract. It is well known that the length generating function E(t) of Dyck paths (excursions with steps +-1) satisfies 1-E+t2E2=0. The generating function E(k)(t) of Dyck paths of height at most k is E(k)=Fk/Fk+1, where the Fk are polynomials in t given by F0=F1=1 and Fk+1= Fk-t2Fk-1. This means that the generating function of these polynomials is \sumk>=0Fkzk = 1/(1-z+t2z2). 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 Fk/Fk+1 of two polynomials. These polynomials satisfy a linear recurrence relation with coefficients in Q[t]. Their (rational) generating function can be written \sumk>=0Fkzk = 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)) does not vanish). 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 da,b = \binom {a+b} a and da,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.

Received: January 8, 2007. Accepted: January 5, 2008. Final Version: February 18, 2008.

The following versions are available: