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: