#####
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*+*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
*\sum*_{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
**Q**[*t*]. Their (rational) generating function can be written
*\sum*_{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*)) 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.

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

The following versions are available: