Discrete Excursions

Mireille Bousquet-Mélou

Séminaire lotharingien de combinatoire, Tome 57 (2007-2010)

Résumé

It is well known that the length generating function E(t) of Dyck paths (excursions with steps +-1) satisfies 1-E+t²E²=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₀=F₁=1 and F_k+1= F_k-t²F_k-1. This means that the generating function of these polynomials is \sum_k>=0F_kz^k = 1/(1-z+t²z²). 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 Q[t]. Their (rational) generating function can be written \sum_k>=0F_kz^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)) 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 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.