  It is well-known that the length generating function E(t) of Dyck paths
(excursions with steps +1 and -1) satisfies 1-E+t^2E^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^2F_{k-1}.
This means that the generating function of these polynomials is \sum_{k\ge 0}
F_k z^k= 1/(1-z+t^2z^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 more 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\ge 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))\not = 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}=binomial(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.
