DISCRETE EXCURSIONS

MIREILLE BOUSQUET-MÉLOU

Abstrat. Itis wellknown thatthelengthgenerating funtion

### E(t)

^{of}

^{Dyk}

paths(exursions with steps

### ± 1

^{)}

^{satises}

### 1 − E + t ^{2} E ^{2} = 0

^{.}

^{The}

^{generating}

funtion

### E ^{(k)} (t)

^{of}

^{Dyk}

^{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

^{.}

Thismeansthat thegeneratingfuntion of thesepolynomialsis

### P

### k≥0 F k z ^{k} = 1/(1 − z + t ^{2} z ^{2} )

^{.}

^{We}

^{note}

^{that}

^{the}denominator ofthisfrationistheminimal

polynomialofthealgebraiseries

### E(t)

^{.}

This pattern persists for walks with general steps. For any nite set

of steps

### S

^{,}

^{the}

^{generating}

^{funtion}

### E ^{(k)} (t)

^{of}

^{exursions}(generalized Dyk 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 reurrene relation

with oeients in

### Q [t]

^{.}

^{Their}

^{(rational)}

^{generating}

^{funtion}

^{an}

^{be}

^{written}

### P

### k≥0 F k z ^{k} = N(t, z)/D(t, z)

^{.}

^{The}

^{exursion}

^{generating}

^{funtion}

### E(t)

^{is}

^{alge-}

braiandsatises

### D(t, E(t)) = 0

^{(while}

### N(t, E(t)) 6 = 0

^{).}

If

### max S = a

^{and}

### min S = b

^{,}

^{the}polynomials

### D(t, z)

^{and}

### N (t, z)

^{an}

^{be}

^{taken}

toberespetivelyofdegree

### d a,b = ^{a+b} _{a}

and

### d a,b − a − b

^{in}

### z

^{.}

^{These}

^{degrees}

^{are}

ingeneraloptimal: forinstane,when

### S = { a, − b }

^{with}

### a

^{and}

### b

^{oprime,}

### D(t, z)

isirreduible, and is thus the minimalpolynomialof theexursion generating

funtion

### E(t)

^{.}

Theproofsofthese resultsinvolveaslightlyunusual mixtureof ombinato-

rialandalgebraitools,amongwhih thekernelmethod (whihsolvesertain

funtionalequations),symmetrifuntions,andapinh ofGaloistheory.

1. Introdution

One of the most lassial ombinatorial inarnations of the famous Catalan

numbers,

## C _{n} = ^{2n} _{n}

## /(n + 1)

^{,}

^{is}

^{the}

^{set}

^{of}

^{Dyk}

^{paths.}

^{These}

^{are}one-dimensional walksthatstart andendat

## 0

^{,}

^{take}

^{steps}

## ± 1

^{,}

^{and}

^{always}

^{remain}

^{at}

^{a}non-negative level (Figure1,left). Byfatoring suhwalksat their rst returnto 0,one easily

proves that their length generating funtion

## E ≡ E(t)

^{is}

^{algebrai,}

^{and}

^{satises}

## E = 1 + t ^{2} E ^{2} .

This immediatelyyields:

## E = 1 − √

## 1 − 4t ^{2}

## 2t ^{2} = X

### n≥0

## C n t ^{2n} .

Theauthor was supported bythe frenh Agene Nationale de la Reherhe, viathe projet

## 4 5 6 7 8

## 3 2 1

## 4 5 6 7 8

## 3 2 1

Figure1. Left: A Dyk pathof length

## 16

^{and}

^{height}

^{4.}

^{Right:}

^{An}

exursion (generalized Dyk path) of length

## 8

^{and}

^{height}

^{7,}

^{with}

steps in

## S = {− 3, 5 }

^{.}

The same fatorization gives a reurrene relation that denes the series

## E ^{(k)} ≡ E ^{(k)} (t)

^{ounting}

^{Dyk}

^{paths}

^{of}

^{height}

^{at}

^{most}

## k

^{:}

## E ^{(0)} = 1

^{and}

^{for}

## k ≥ 1, E ^{(k)} = 1 + t ^{2} E ^{(k−1)} E ^{(k)} .

This reursionan beused toprovethat

## E ^{(k)}

^{is}

^{rational,}

^{and}

^{more}

^{preisely}

^{,}

^{that}

## E ^{(k)} = F _{k}

## F k+1

## ,

^{where}

## F 0 = F 1 = 1

^{and}

## F k+1 = F k − t ^{2} F k−1 .

The aim of this paper is to desribe what happens for generalized Dyk paths

(also known as exursions) taking their steps in an arbitrary nite set

## S ⊂ Z

(see anexample in Figure1, right). Their lengthgenerating funtion

## E

^{is}

^{known}

to be algebrai. What is the degree of this series? How an one ompute its

minimal polynomial? Furthermore, it is easy to see that the generating funtion

## E ^{(k)}

^{an}

^{still}

^{be}

^{written}

## F k /F k+1

^{,}

^{for}

^{some}polynomials

## F k

^{.}

^{Does}

^{the}

^{sequene}

## (F k ) k

^{satisfy}

^{a}

^{linear}

^{reurrene}

^{relation?}

^{Of}

^{what}

^{order?}

^{How}

^{an}

^{one}

^{determine}

this reursion? Notethat any linear reursion of order

## d

^{,}

^{of}

^{the}

^{form}

### d

## X

### i=0

## a i F k−i = 0

^{(1)}

with

## a _{i} ∈ Q[t]

^{,}

^{gives}

^{a}

^{non-linear}

^{reursion}

^{of}

^{order}

## d

^{for}

^{the}

^{series}

## E ^{(k)}

^{,}

### d

## X

### i=0

## a i E ^{(k−i+1)} · · · E ^{(k)} = 0,

^{(2)}

and, by taking the limit

## k → ∞

^{,}

^{an}

^{algebrai}

^{equation}

^{of}

^{degree}

## d

^{satised}

^{by}

## E = lim k E ^{(k)}

^{:}

### d

## X

### i=0

## a i E ^{i} = 0.

This establishes a lose link between the (still hypothetial) reursion for the

sequene

## F k

^{and}

^{the}algebraiity of

## E

^{.}

^{The}

^{onnetion}

^{between}

^{(1)}

^{and}

^{(2)}

^{is}

entralinthe reent paper[2℄dealing with exursions with steps

## ± 1, ± 2

^{.}

A slightly surprising outome of this paper is that symmetri funtions are

summaryofouranswerstotheabovequestions. Assume

## min S = − b

^{and}

## max S = a

^{.}

^{Then}

^{the}

^{exursion}

^{generating}

^{funtion}

## E

^{is}

^{algebrai}

^{of}

^{degree}

^{at}

^{most}

## d a,b :=

### a+b a

. The degree is exatly

## d _{a,b}

^{in}

^{the}

^{generi}

^{ase}

^{(to}

^{be}

^{dened),}

^{but}

^{also}

when

## S = {− b, a }

^{with}

## a

^{and}

## b

^{oprime.}

^{Computing}

^{a}

^{polynomial}

^{of}

^{degree}

## d _{a,b}

thatannihilates

## E

^{boils}

^{down}

^{to}

^{omputing}

^{the}

^{elementary}

^{plethysms}

## e k [e a ]

^{on}

^{an}

alphabet with

## a + b

^{letters,}

^{for}

## 0 ≤ k ≤ d _{a,b}

^{.}

Thegeneratingfuntion

## E ^{(k)}

^{ounting}

^{exursions}

^{of}

^{height}

^{at}

^{most}

## k

^{is}

^{rational}

and an be written

## F k /F k+1

^{for}

^{some}polynomials

## F k

^{.}

^{These}polynomials satisfy a linear reurrene relation of the form (1), of order

## d a,b

^{,}

^{whih}

^{is}

^{valid}

^{for}

## k >

## d a,b − a − b

^{.}

^{Moreover,}

## F k

^{an}

^{be}

^{expressed}

^{as}

^{a}determinantof varyingsize

## k

^{,}

^{but}

alsoasa retangular Shurfuntion taking the formof adeterminantof onstant

size

## a + b

^{.}

These results are detailed in the next setion. Not all of them are new. The

generating funtion of exursions, given in Proposition 1, rst appeared in [6℄,

but an be derived from the earlier paper [17℄. An algorithm for omputing a

polynomial of degree

## d a,b

^{that}annihilates

## E

^{was}

^{desribed}

^{in}

^{[5℄.}

^{Hene}

^{the}

^{rst}

part of the next setion, whih deals with unbounded exursions, is mostly a

survey (the results on the exat degree of

## E

^{are}

^{however}

^{new).}

^{The}

^{seond}

^{part}

exursions ofbounded height is new,althoughanattempt inthe same vein

appears in[3℄.

Letusnish withtheplanof thispaper. Thekernel methodhas beomeastan-

dard tool to solve ertain funtional equations arising in various ombinatorial

problems [4, 14, 26℄. We illustrateit in Setion 3 by ounting unbounded exur-

sions. Weuse itagaininSetion4toobtainthegenerating funtionofexursions

of bounded height. Remarkably, thesame result anbe obtained byombining the

transfer-matrix methodandthedual JaobiTrudiidentity. InSetion5,wedeter-

mine the reurrene relation satised by the polynomials

## F k

^{.}

^{More}

^{preisely}

^{,}

^{we}

omputetherationalseries

## P

### k F k z ^{k}

^{.}

^{This}

^{is}

^{equivalent}

^{to}

^{omputing}

^{the}

^{generat-}

ing funtion of retangular Shur funtions

## P

### k s k ^{a} z ^{k}

^{,}

^{where}

## a = max S

^{.}

^{Finally,}

we disuss in Setion 6 the exat degree of the series

## E

^{for}

^{ertain}

^{step}

^{sets}

## S

^{.}

This involves a bitof Galois theory.

2. Statement of the results

Weonsider one-dimensionalwalksthat startfrom

## 0

^{,}

^{take}

^{their}

^{steps}

^{in}

^{a}

^{nite}

set

## S ⊂ Z

^{,}

^{and}

^{always}

^{remain}

^{at}

^{a}non-negative level. More formally, a (non- negative)walk oflength

## n

^{will}

^{be}

^{a}

^{sequene}

## (s _{1} , s _{2} , . . . , s _{n} ) ∈ S ^{n}

^{suh}

^{that}

^{for}

^{all}

## i ≤ n

^{,}

^{the}

^{partial}

^{sum}

## s 1 + · · · + s i

^{is}non-negative. The nal level of this walk is

## s _{1} + · · · +s _{n}

^{,}

^{and}

^{its}

^{height}

^{is}

## max _{i} s _{1} + · · · +s _{i}

^{.}

^{An}

^{exursion}

^{is}

^{a}non-negativewalk endingat level 0 (Figure1). Weare interested inthe enumeration of exursions.

Thegeneratingfuntionsweonsider arefairlygeneral,inthateverystep

## s ∈ S

is weighted by an element

## ω s

^{of}

^{some}

^{eld}

## K

^{of}harateristi 0. For instane, all the

## ω s

^{may}

^{be}

^{1.}

^{Or}

^{they}

^{may}

^{be}independent indeterminates. In the latter ase,

## K

^{is}

^{the}

^{fration}

^{eld}

## Q(ω s , s ∈ S )

^{.}

^{The}

^{length}

^{of}

^{the}

^{walks}

^{is}

^{taken}

^{into}

aount by an additional indeterminate

## t

^{,}transendental over

## K

^{.}

^{In}

^{partiular,}

the generating funtion of exursions is

## E := X

## ω s 1 · · · ω s n t ^{n} ,

where the sum runs over all exursions

## (s 1 , s 2 , . . . , s n )

^{.}

^{This}

^{is}

^{a}

^{power}

^{series}

^{in}

## t

^{with}

^{oeients}

^{in}

## K

^{.}

^{In}

^{one}

^{oasion}

^{(Example}

^{2),}

^{we}

^{will}

^{then}

^{speialize}

the indeterminates

## ω s

^{into}polynomials in

## t

^{.}

^{The}

^{series}

## E

^{beomes}

^{a}

^{well-dened}

powerseries in

## t

^{.}

If

## min S = − b

^{and}

## max S = a

^{,}

^{we}

^{assume}

^{that}

## ω −b

^{and}

## ω a

^{are}

^{non-zero.}

^{If}

## d

divides all the elements of

## S

^{,}

^{the}

^{exursion}

^{generating}

^{funtion}

^{is}

^{unhanged}

^{if}

we replaeeah

## s ∈ S

^{by}

## s/d

^{(up}

^{to}

^{a}

^{renaming}

^{of}

^{the}

^{weights}

## ω _{s}

^{).}

^{Thus}

^{we}

^{an}

always assumethat the elementsof

## S

^{are}

^{relatively}

^{prime.}

^{Also,}

^{if}

## (s 1 , s 2 , . . . , s n )

is anexursion,

## ( − s _{n} , . . . , − s _{2} , − s _{1} )

^{is}

^{also}

^{an}

^{exursion,}

^{with}

^{steps}

^{in}

## −S

^{.}

^{Thus}

the exursion series obtained for

## S

^{and}

## −S

^{oinide,}

^{up}

^{to}

^{a}

^{renaming}

^{of}

^{the}

weights

## ω s

^{.}

Theweightingofthewalksthatwehavedeneddependsonthelistofstepsthat

are taken, but not on the positions of these steps in

## Z

^{.}

^{F}

^{or}

^{instane,}

^{we}

^{annot}

keep trak of the number of visits to 0 with our weights, whereas this parameter

is sometimes of interest [1, 8℄. However, the methods we present here are fairly

robustandanoftenbeadaptedtosolvevariantsofthetwomainquestionsstudied

inthis paper (inluding the number of visitsto 0).

In the expression of

## E

^{given}

^{below}(Proposition1), animportantrole is played by the following term,whih enodes the steps of

## S

^{:}

## P (u) = X

### s∈S

## ω s u ^{s} ,

^{(3)}

where

## u

^{is}

^{a}

^{new}indeterminate. ThisisaLaurentpolynomialin

## u

^{with}

^{oeients}

in

## K

^{.}

^{If}

## min S = − b

^{,}

^{we}

^{dene}

## K(u) = u ^{b} (1 − tP (u)) .

^{(4)}

This isnowapolynomialin

## u

^{with}

^{oeients}

^{in}

## K [t]

^{.}

^{If}

## max S = a

^{,}

^{this}

^{polyno-}

mialhas degree

## a + b

^{in}

## u

^{.}

^{It}

^{has}

## a + b

^{roots,}

^{whih}

^{are}

^{frational}

^{Laurent}

^{series}

(Puiseuxseries)in

## t

^{with}

^{oeients}

^{in}

## K

^{,}

^{an}

^{algebrai}

^{losure}

^{of}

## K

^{.}

^{(We}

^{refer}

^{the}

readerto[30, Ch. 6℄ forgeneralitieson the rootsof apolynomialwith oeients

in

## K[t]

^{.)}

^{Exatly}

## b

^{of}

^{these}

^{roots,}

^{say}

## U _{1} , . . . , U _{b}

^{,}

^{are}

^{nite}

^{at}

## t = 0

^{.}

^{These}

^{roots}

are atually formal power series in

## t ^{1/b}

^{,}

^{and}

^{the}

^{rst}

^{term}

^{of}

## U i

^{is}

## ξ ^{i} (tω −b ) ^{1/b}

^{,}

where

## ξ

^{is}

^{a}

## b

^{th}

^{root}

^{of}

^{unity}

^{.}

^{In}

^{partiular,}

^{these}

## b

^{series}

^{are}

^{distint,}

^{and}

^{vanish}

at

## t = 0

^{.}

^{We}

^{all}

^{them}

^{the}

^{small}

^{roots}

^{of}

## K

^{.}

^{The}

## a

^{other}

^{roots,}

## U b+1 , . . . , U a+b

^{,}

are the large roots of

## K

^{.}

^{They}

^{are}

^{Laurent}

^{series}

^{in}

## t ^{1/a}

^{,}

^{and}

^{their}

^{rst}

^{term}

^{is}

## ct ^{−1/a}

^{,}

^{for}

^{some}

## c 6 = 0

^{.}

^{Note}

^{that}

## K(u)

^{fators}

^{as}

## K(u) = u ^{b} (1 − tP (u)) = − tω a a+b

## Y

### i=1

## (u − U i ) ,

so thatthe elementary symmetrifuntions of the

## U i

^{'s}

^{are:}

## e i ( U ) = ( − 1) ^{i} ω a−i

## ω a − 1 tω a

## χ a=i

## ,

^{(5)}

with

## U = (U 1 , . . . , U a+b )

^{.}

^{W}

^{e}

^{refer}

^{to}

^{[30,}

^{Ch.}

^{7℄}

^{or}

^{[23℄}

^{for}generalities on sym- metri funtions.

2.1. Unbounded exursions

At least three dierent approahes have been used to ount exursions. The

rst one generalizes the fatorization of Dyk paths mentioned at the beginning

ofthe introdution. Ityieldsasystemofalgebraiequationsdening

## E

^{[1,}

^{15,}

^{21,}

22, 24℄. The fatorization diers from one paper to another. To our knowledge,

the simplest, and most systematione, appears in [15℄.

A seond approah [17℄ relies on a fatorization of unonstrained walks taking

their steps in

## S

^{,}

^{and}

^{on}

^{a}

^{related}fatorization of formal power series. The ex- pression of

## E

^{that}

^{an}

^{be}

^{derived}

^{from}

^{[17℄}

^{(by}

^{ombining}Proposition 4.4 and the proof of Proposition 5.1) oinides with the expression obtained by the third

approah, whih is based on a step by step onstrution of the walks [6, 5℄. This

expression of

## E

^{is}

^{given}

^{in}

^{(6)}

^{below.}

^{We}

^{repeat}

^{in}

^{Setion}

^{3}

^{the}

^{proof}

^{of}

^{(6)}

published in[6℄, asit willbe extended laterto ount bounded exursions.

Proposition 1. The generating funtion of exursions is algebrai over

## K (t)

^{of}

degree at most

## d a,b = ^{a+b} _{a}

. It an be written as:

## E = ( − 1) ^{b+1} tω −b

### b

## Y

### i=1

## U i = ( − 1) ^{a+1} tω a

### a+b

## Y

### i=b+1

## 1 U i

## ,

^{(6)}

where

## U 1 , . . . , U b

^{(r}

^{espetively}

## U b+1 , . . . , U a+b

^{)}

^{are}

^{the}

^{small}(respetively large) roots of the polynomial

## K(u)

^{given}

^{by}

^{(4).}

^{The}

^{quantity}

^{dened}

^{by}

## D(t, z) = Y

### I⊂Ja+bK, |I|=a

## (1 + ( − 1) ^{a} ztω a U I ) ,

^{(7)}

with

## Ja + bK = { 1, 2, . . . , a + b }

^{and}

## U I = Y

### i∈I

## U i ,

is a polynomial in

## t

^{and}

## z

^{with}

^{oeients}

^{in}

## K

^{,}

^{of}

^{degree}

## d a,b

^{in}

## z

^{,}

^{satisfying}

## D(t, E) = 0

^{.}

One the expression (6) is established, the other statements easily follow. In-

deed,theseondexpressionof

## E

^{shows}

^{that}

## D(t, E ) = 0

^{.}

^{Moreover,}

^{the}

^{expression}

of

## D(t, z)

^{is}

^{symmetri}

^{in}

^{the}

^{roots}

## U _{1} , . . . , U _{a+b}

^{,}

^{so}

^{that}

^{its}

^{oeients}

^{belong}

^{to}

## K(t)

^{.}

^{More}

^{preisely}

^{,}

^{the}

^{form}

^{(5)}

^{of}

^{the}

^{elementary}

^{symmetri}

^{funtions}

^{of}

^{the}

## U i

^{'s}

^{shows}

^{that}

## D(t, z)

^{is}

^{a}

^{Laurent}

^{polynomial}

^{in}

## t

^{.}

^{But}

^{the}

^{valuation}

^{of}

## U i

^{in}

## t

is atleast

## − 1/a

^{,}

^{and}

^{this}

^{implies}

^{that}

## D(t, z)

^{is}

^{a}

^{polynomial}

^{in}

## t

^{.}

Clearly,thedegreeof

## D(t, z)

^{in}

## z

^{is}

## d a,b = ^{a+b} _{a}

. Thusthe exursiongenerating

funtion

## E

^{has}

^{degree}

^{at}

^{most}

## d a,b

^{.}

^{We}

^{prove}

^{in}

^{Setion}

^{6}

^{that}

## D(t, z)

^{is}

^{atually}

irreduible inthe two following ases:

## • S = J − b, aK = {− b, . . . , a − 1, a }

^{and}

## ω −b , . . . , ω a

^{are}independentindeter-

## • S = {− b, a }

^{with}

## ω −b = ω a = 1

^{and}

## a

^{and}

## b

^{oprime}

^{(two-step}exursions).

As shown by Example2 below,

## D(t, z)

^{is}

^{not}

^{always}irreduible.

An algebrai equation for

## E

^{.}

^{As}

^{argued}

^{above,}

## D(t, z)

^{is}

^{a}

^{polynomial}

^{in}

## t

and

## z

^{that}

^{vanishes}

^{for}

## z = E

^{.}

^{However,}

^{its}

^{expression}

^{(7)}

^{involves}

^{the}

^{series}

## U i

^{,}

while one would prefer to obtain an expliit polynomial in

## t

^{and}

## z

^{.}

^{Reall}

^{that}

the series

## U i

^{are}

^{only}

^{known}

^{via}

^{their}

^{elementary}

^{symmetri}

^{funtions}

^{(5).}

^{How}

an one ompute a polynomial expression of

## D(t, z)

^{?}

^{The}

^{approahes}

^{based}

^{on}

resultants orGröbnerbases beomevery quikly ineetive.

In the generi ase where

## S = J − b, aK

^{and}

^{the}

^{weights}

## ω _{s}

^{are}indeterminates,

## K(u)

^{is}

^{the}

^{general}

^{polynomial}

^{of}

^{degree}

## a + b

^{in}

## u

^{,}

^{and}

^{the}

^{problem}

^{an}

^{be}

rephrased asfollows: Take

## n = a + b

^{variables}

## u 1 , . . . , u n

^{,}

^{and}

^{expand}

^{the}

^{polyno-}

mial

## Q(z) = Y

### I⊂JnK, |I|=a

## (1 − zu I )

^{(8)}

in the basis of elementary symmetri funtions of

## u 1 , . . . , u n

^{.}

^{F}

^{or}

^{instane,}

^{for}

## a = 2

^{and}

## b = 1

^{,}

## Q(z) = (1 − zu 1 u 2 )(1 − zu 1 u 3 )(1 − zu 2 u 3 )

## = 1 − z(u 1 u 2 + u 1 u 3 + u 2 u 3 ) + z ^{2} (u ^{2} _{1} u 2 u 3 + u 1 u ^{2} _{2} u 3 + u 1 u 2 u ^{2} _{3} ) − z ^{3} (u 1 u 2 u 3 ) ^{2}

## = 1 − ze 2 + z ^{2} e 3,1 − z ^{3} e 3,3 ,

while for

## a = b = 2

^{,}

## Q(z) = 1 − ze _{2} +z ^{2} (e _{3,1} − e _{4} ) − z ^{3} (e _{3,3} +e _{4,1,1} − 2e _{4,2} )+z ^{4} e _{4} (e _{3,1} − e _{4} ) − z ^{5} e _{4,4,2} +z ^{6} e _{4,4,4} .

(9)

Using the standard notation for plethysm [30, Appendix 2℄, the polynomial

## Q(z)

reads

## Q(z) =

### d a,b

## X

### k=0

## ( − z) ^{k} e _{k} [e _{a} ].

This shows that, inthe generiase, the problemof expressing

## D(t, z)

^{as}

^{a}

^{poly-}

nomial in

## t

^{and}

## z

^{is}

^{equivalent}

^{to}

^{expanding}

^{the}

^{plethysms}

## e k [e a ]

^{in}

^{the}

^{basis}

^{of}

elementary symmetrifuntions, foran alphabetof

## n = a + b

^{variables.}

^{Unfortu-}

nately, there is no general expression for the expansion of

## e k [e a ]

^{in}

^{any}

^{standard}

basis of symmetri funtions, and only algorithmi solutions exist [9, 10℄. Most

of them expand plethysms in the basis of Shur funtions. This is justied by

the representation-theoreti meaningof plethysm. Still,inour walk problem, the

natural basis is that of elementary funtions. We have used for our alulations

the simple platypus 1

algorithm presented in [5℄, whih only exploits the onne-

tions between power sums and elementary symmetri funtions. This algorithm

takes advantage automatially of simpliations ourring in non-generi ases.

For instane, when only two steps are allowed, say

## − b

^{and}

## a

^{,}

^{all}

^{the}

^{elementary}

symmetri funtions of the

## U i

^{'s}

^{vanish,}

^{apart}

^{from}

## e 0 ( U )

^{,}

## e a ( U )

^{and}

## e a+b ( U )

^{.}

^{It}

would be a shame to ompute the general expansion of

## e k [e a ]

^{in}

^{the}

^{elementary}

1

basis,andthenspeializemostofthe

## e i

^{to}

## 0

^{.}

^{The}

^{platypus}

^{algorithm}

^{diretly}

^{gives}

the expansion of

## e k [e a ]

^{modulo}

^{the}

^{ideal}

^{generated}

^{by}

^{the}

## e i

^{,}

^{for}

## i 6 = 0, a, a + b

^{.}

Forinstane, when

## a = 2

^{and}

## b = 1

^{,}

## Q(z) ≡ 1 − ze 2 − z ^{3} e ^{2} _{3} ,

while for

## a = 2

^{and}

## b = 3

^{,}

## Q(z) ≡ 1 − ze 2 − 2z ^{5} e ^{2} _{5} + z ^{6} e 2 e ^{2} _{5} − z ^{7} e ^{2} _{2} e ^{2} _{5} + z ^{10} e ^{4} _{5} .

and for

## a = 5

^{and}

## b = 2

^{,}

## Q(z) ≡ 1 − ze 5 − 3z ^{7} e ^{5} _{7} + 2z ^{8} e 5 e ^{5} _{7} − 2z ^{9} e ^{2} _{5} e ^{5} _{7} + z ^{10} e ^{3} _{5} e ^{5} _{7} − z ^{11} e ^{4} _{5} e ^{5} _{7}

## + 3z ^{14} e ^{10} _{7} − z ^{15} e _{5} e ^{10} _{7} + 2z ^{16} e ^{2} _{5} e ^{10} _{7} − z ^{21} e ^{15} _{7} .

From the above examples,one may suspet that, in the two-step ase, the oe-

ientof

## z ^{k}

^{in}

## Q(z)

^{is}

^{always}

^{a}

^{monomial}

^{in}

^{the}

## e i

^{.}

^{Going}

^{bak}

^{to}

^{the}

^{polynomial}

## D(t, z)

^{,}

^{and}

^{given}

^{that}

## e _{a} ( U ) = ( − 1) ^{a+1} tω a

and

## e _{a+b} ( U ) = ( − 1) ^{a+b} ω −b

## ω a

## ,

this would mean that the oeient of

## z ^{k}

^{in}

## D(t, z)

^{is}

^{always}

^{a}

^{monomial}

^{in}

## t

^{.}

This observation rst gave us some hope to nd (in the two-step ase) a simple

desription of

## D(t, z)

^{and,}

^{why}

^{not,}

^{a}

^{diret}ombinatorialproof of

## D(t, E) = 0

^{.}

However, this nie patterndoesnot persist: for

## a = 3

^{and}

## b = 5

^{,}

^{the}

^{oeient}

^{of}

## z ^{16}

^{in}

## Q(z)

^{ontains}

## e ^{6} _{8}

^{and}

## e ^{8} _{3} e ^{3} _{8}

^{.}

For the sake of ompleteness, let us desribe this platypus algorithm. Take a

polynomial

## L(z)

^{of}

^{degree}

## n

^{with}

^{onstant}

^{term}

^{1,}

^{and}

^{dene}

## U 1 , . . . , U n

^{impliitly}

by

## L(z) =

### n

## Y

### k=1

## (1 − zU _{k} ).

The algorithmgivesa polynomialexpression of

## Q(z) = Y

### |I|=a

## (1 − zU I ) =

### d

## X

### k=0

## ( − z) ^{k} e k [e a ]( U )

with

## d = ^{n} _{a}

and

## U = (U 1 , . . . , U n )

^{.}

^{The}

^{only}

^{general}

^{identity}

^{that}

^{is}

^{needed}

^{is}

the expansion of

## e a

^{in}

^{power}

^{sums.}

^{This}

^{an}

^{be}

^{obtained}

^{from}

^{a}

^{series}

^{expansion}

via

## e _{a} = [z ^{a} ] exp − X

### i≥1

## ( − z) ^{i} i p _{i}

## !

## = Φ _{a} (p _{1} , . . . , p _{a} )

^{(10)}

for some polynomial

## Φ a

^{.}

^{The}

^{rest}

^{of}

^{the}

^{alulation}

^{also}

^{uses}

^{series}expansions, and goes asfollows:

## •

^{ompute}

## p i ( U )

^{for}

## 1 ≤ i ≤ ad

^{using}

## p i ( U ) = i[z ^{i} ] log(1/L(z))

^{,}

## •

^{ompute}

## log Q(z)

^{up}

^{to}

^{the}

^{oeient}

^{of}

## z ^{d}

^{using}

## log Q(z) = − X

### i≥1

## z ^{i}

## i Φ a (p i ( U ), p 2i ( U ), . . . , p ai ( U )),

^{(11)}

## •

^{ompute}

## Q(z)

^{up}

^{to}

^{the}

^{oeient}

^{of}

## z ^{d}

^{using}

## Q(z) = exp(log Q(z))

^{.}

Sine

## Q(z)

^{has}

^{degree}

## d

^{,}

^{the}

^{alulation}

^{is}

^{omplete.}

^{The}

^{identity}

^{(11)}

^{follows}

from(10) and

## log Q(z) = − X

### i≥1

## z ^{i} i

## X

### |I|=a

## U _{I} ^{i} = − X

### i≥1

## z ^{i}

## i e a (U _{1} ^{i} , . . . , U _{n} ^{i} ).

Given a set of steps

## S

^{,}

^{with}

## max S = a

^{,}

^{one}

^{obtains}

^{a}

^{polynomial}

^{expression}

^{of}

## D(t, z)

^{by}

^{applying}

^{the}

^{platypus}

^{algorithm}

^{to}

## L(z) = X

### s∈S

## ω s

## ω a

## z ^{a−s} − z ^{a} tω a

## .

If the output of the algorithm is the polynomial

## Q(z)

^{,}

^{then}

## D(t, z) = Q(( − 1) ^{a+1} tω _{a} z).

Example 1: Two step exursions. The simplest walks we an onsider are

obtained for

## S = {− b, a }

^{and}

## ω a = ω −b = 1

^{.}

^{We}

^{always}

^{assume}

^{that}

## a

^{and}

## b

^{are}

oprime.

If

## b = 1

^{,}Proposition1gives

## E = U/t

^{,}

^{where}

## U

^{is}

^{the}

^{only}

^{power}

^{series}

^{satisfying}

## U = t(1+U ^{a+1} )

^{.}Equivalently,

## E = 1+t ^{a+1} E ^{a+1}

^{.}

^{This}

^{equation}

^{an}

^{be}

^{understood}

ombinatoriallyby lookingatthe rst visit of the walk at levels

## a, a − 1, . . . , 1, 0

^{,}

and fatoring the walk at these points. Of ourse, a similar result holds when

## a = 1

^{.}

If

## a, b > 1

^{,}

^{it}

^{is}

^{still}

^{possible,}

^{but}

^{more}

^{diult,}

^{to}

^{write}

^{diretly}

^{a}

^{system}

^{of}

polynomial equations, based on fatorizations of the walks, that dene the series

## E

^{.}

^{See}

^{for}

^{instane}

^{[15,}

^{21,}

^{22,}

^{24℄.}

^{It}

^{would}

^{be}interestingtoworkout thepreise

linkbetween theomponentsof thesesystemsand theseries

## U i

^{.}

^{T}

^{o}

^{ompare}

^{both}

types of results, take

## a = 3

^{and}

## b = 2

^{.}

^{On}

^{the}

^{one}

^{hand,}

^{it}

^{is}

^{shown}

^{in}

^{[15℄}

^{that}

## E

^{is}

^{the}

^{rst}

^{omponent}

^{of}

^{the}

^{solution}

^{of}

##

##

##

## E = 1 + L 1 R 1 + L 2 R 2 L 1 = L 2 R 1 + L 3 R 2

## R 1 = L 1 R 2 L 2 = L 3 R 1

## R 2 = tE L 3 = tE.

On the other hand, Proposition1 gives

## E = − U 1 U 2 /t

^{,}

^{where}

## U 1 , U 2

^{are}

^{the}

^{small}

rootsof

## u ^{2} = t(1 + u ^{5} )

^{.}

^{The}

^{platypus}

^{algorithm}

^{gives}

## D(t, E) = 0

^{with}

## D(t, z) = 1 − z + t ^{5} z ^{5} (2 − z + z ^{2} ) + t ^{10} z ^{10} .

^{(12)}

This polynomial isirreduible. Similarly,for

## a = 4

^{and}

## b = 3

^{,}

## D(t, E) = 0

^{with}

## D(t, z) = 1 − z + t ^{7} z ^{7} 5 − 4 z + z ^{2} + 3 z ^{3} − z ^{5} + z ^{6}

## + t ^{14} z ^{14} 10 − 6 z + 3 z ^{2} + 5 z ^{3} − z ^{4} + z ^{5} + t ^{21} z ^{21} 10 − 4 z + 3 z ^{2} + z ^{3} − z ^{4}

## + t ^{28} z ^{28} 5 − z + z ^{2} − z ^{3}

## + z ^{35} t ^{35} .

^{(13)}

We prove in Setion 6 that, in the ase of two step walks,

## D(t, z)

^{is}

^{always}

^{irre-}

duible. That is, the degreeof

## E

^{is}

^{exatly}

^{a+b} _{a}

.

Example 2: Playing basket-ball with A. and Z. In a reent paper [2℄, the

authors onsider exursions with steps in

## {± 1, ± 2 }

^{,}

^{where}

^{the}

^{steps}

## ± 2

^{have}

length2ratherthan1. Theyuse fatorizationsofwalkstoountexursions(more

speially,exursions ofbounded height). Thisproblemtsinour frameworkby

hoosing

## ω _{−2} = ω _{2} = ω

^{and}

## ω _{−1} = ω _{1} = 1

^{,}

^{and}

^{then}speializing

## ω = t

^{.}

^{Observe}

thatthesmallrootsof

## u ^{2} = t(ω+u+u ^{3} +ωu ^{4} )

^{,}

^{involved}

^{in}Proposition1,speialize into the smallroots

## U _{1}

^{and}

## U _{2}

^{of}

## u ^{2} = t(t + u + u ^{3} + tu ^{4} )

^{when}

## ω

^{is}

^{set}

^{to}

## t

^{.}

^{W}

^{e}

obtain

## E = − U 1 U 2 /t ^{2}

^{.}

^{The}

^{platypus}

^{algorithm}

^{yields}

## D(t, z ) = ¯ D(t, z)(1 + t ^{2} z) ^{2} ,

^{(14)}

where

## D(t, z) = ¯ t ^{8} z ^{4} − t ^{4} 1 + 2 t ^{2}

## z ^{3} + t ^{2} 3 + 2 t ^{2}

## z ^{2} − 1 + 2 t ^{2}

## z + 1

^{(15)}

is the minimal polynomial of

## E

^{.}

^{This}fatorization is an interesting phenome- non, whih is not related to the unequal lengths of the steps. Indeed, the same

phenomenon ours when

## S = {± 1, ± 2 }

^{and}

^{all}

^{weights}

^{are}

^{1.}

^{In}

^{this}

^{ase,}

^{one}

nds:

## D(t, z) = ¯ D(t, z)(1 + tz) ^{2}

with

## D(t, z) = ¯ t ^{4} z ^{4} − t ^{2} (2t + 1)z ^{3} + t(3t + 2)z ^{2} − (2t + 1)z + 1,

so thatthe exursiongenerating funtion has degree 4 again.

Thefatorization of

## D(t, z)

^{is}

^{due}

^{to}

^{the}

^{symmetry}

^{of}

^{the}

^{set}

^{of}

^{steps.}

^{For}

^{eah}

set

## S

^{suh}

^{that}

## S = −S

^{and}

^{weights}

## ω s

^{suh}

^{that}

## ω s = ω −s

^{,}

^{the}

^{polynomial}

## P (u)

given by(3)issymmetriin

## u

^{and}

## 1/u

^{.}

^{In}

^{partiular,}

## a = b

^{.}

^{This}

^{implies}

^{that}

^{the}

smallandlargerootsof

## 1 − tP (u)

^{an}

^{be}

^{grouped}

^{by}

^{pairs:}

## U a+1 = 1/U 1 , . . . , U 2a = 1/U a

^{.}

^{In}

^{partiular,}

^{if}

## a

^{is}

^{even,}

^{the}

^{polynomial}

## D(t, z)

^{given}

^{by}

^{(7)}

^{ontains}

^{the}

fator

## (1 + tω a z)

^{at}

^{least}

_{a/2} ^{a}

times. Inthe basket-ballase (

## a = 2

^{),}

^{this}

^{explains}

the fator

## (1 + tz) ^{2}

^{ourring}

^{in}

## D(t, z)

^{.}

^{More}

^{generally,}

^{we}

^{prove}

^{in}

^{Setion}

^{7}

that if

## S

^{is}

^{symmetri,}

^{with}

^{symmetri}

^{weights,}

^{then}

^{the}

^{degree}

^{of}

## E

^{is}

^{at}

^{most}

## 2 ^{a}

^{,}

^{where}

## a = max S

^{.}

2.2. Exursions of bounded height

We now turn our attention to the enumeration of exursions of height at most

## k

^{.}

^{These}

^{are}

^{walks}

^{on}

^{a}

^{nite}

^{direted}

^{graph,}

^{so}

^{that}

^{the}

^{lassial}transfer-matrix method applies

2

. The verties of the graph are

## 0, 1, . . . , k

^{,}

^{and}

^{there}

^{is}

^{an}

^{edge}

from

## i

^{to}

## j

^{if}

## j − i ∈ S

^{.}

^{The}

^{adjaeny}

^{matrix}

^{of}

^{this}

^{graph}

^{is}

## A ^{(k)} = (A _{i,j} ) _{0≤i,j≤k}

with

## A i,j =

## ω _{j−i}

^{if}

## j − i ∈ S ,

## 0

^{otherwise.}

^{(16)}

2

In language theoreti terms, the words of

### S ^{∗}

^{that}

^{enode}

^{these}

^{bounded}

^{exursions}

^{are}

By onsidering the

## n

^{th}

^{power}

^{of}

## A ^{(k)}

^{,}

^{it}

^{is}

^{easy}

^{to}

^{see}

^{[29,}

^{Ch.}

^{4℄}

^{that}

^{the}

^{series}

## E ^{(k)}

^{ounting}

^{exursions}

^{of}

^{height}

^{at}

^{most}

## k

^{is}

^{the}

^{entry}

## (0, 0)

^{in}

## (1 − tA ^{(k)} ) ^{−1}

^{.}

The translational invarianeof our step system gives

## E ^{(k)} = F _{k} F k+1

where

## F _{0} = 1

^{and}

## F _{k+1}

^{is}

^{the}determinant of

## 1 − tA ^{(k)}

^{.}

^{The}

^{size}

^{of}

^{this}

^{matrix,}

## k + 1

^{,}

^{grows}

^{with}

^{the}

^{height.}

As was already observed in [3℄, the series ounting walks onned ina strip of

xedheightanalsobeexpressedusingdeterminantsofsize

## a+b

^{,}

^{where}

## a = max S

and

## − b = min S

^{.}

^{However,}

^{the}expressionsgiven inthe aboverefereneareheavy.

A dierent route yields determinants that are Shur funtions in the series

## U i

(reall that these series are the roots of the polynomial

## K(u)

^{given}

^{by}

^{(4)).}

^{This}

wasshown in[7℄forthe enumerationof ulminatingwalks. Thease ofexursions

is even simpler,as itonly involves retangular Shur funtions.

Let us reall the denition of Shur funtions in

## n

^{variables}

## x 1 , . . . , x n

^{.}

^{Let}

## δ = (n − 1, n − 2, . . . , 1, 0)

^{.}

^{F}

^{or}

^{any}

^{integer}

^{partition}

## λ

^{with}

^{at}

^{most}

## n

^{parts,}

## λ = (λ 1 , . . . , λ n )

^{with}

## λ 1 ≥ λ 2 ≥ · · · ≥ λ n ≥ 0

^{,}

## s λ (x 1 , . . . , x n ) = a δ+λ

## a δ

## ,

^{with}

## a µ = det x ^{µ} _{i} ^{j}

### 1≤i,j≤n .

^{(17)}

Proposition 2. The generating funtion of exursions of height at most

## k

^{is}

## E ^{(k)} = F k

## F k+1

## = ( − 1) ^{a+1} tω a

## s k ^{a} ( U ) s (k+1) ^{a} ( U )

where

## U = (U 1 , . . . , U a+b )

^{is}

^{the}

^{olle}

^{tion}

^{of}

^{roots}

^{of}

^{the}

^{polynomial}

## K(u)

^{given}

by (4), and

## F k+1 = det(1 − tA ^{(k)} )

^{where}

## A ^{(k)}

^{is}

^{the}

^{adjaeny}

^{matrix}

^{(16).}

^{In}

partiular,

## F k = ( − 1) ^{k(a+1)} (tω a ) ^{k} s k ^{a} ( U ).

^{(18)}

This proposition is proved in Setion 4 in two dierent ways. In Setion 5,

we derive from the Shur expression of

## F k

^{that}

^{these}polynomialssatisfy a linear reurrene relation. Equivalently, the generating funtion

## P

### k F k z ^{k}

^{is}

^{a}

^{rational}

funtion of

## t

^{and}

## z

^{.}

Proposition 3. The generating funtion of the polynomials

## F k

^{is}

^{rational,}

^{and}

an be written as

## X

### k≥0

## F k z ^{k} = N (t, z) D(t, z)

where

## D(t, z)

^{is}

^{given}

^{by}

^{(7),}

^{and}

## N(t, z)

^{has}

^{degree}

^{a+b} _{a}

## − a − b

^{in}

## z

^{.}

^{Moreover,}

## D(t, E ) = 0

^{and}

## N (t, E) 6 = 0.

In other words, the sequene

## F _{k}

^{satises}

^{a}

^{linear}

^{reurrene}

^{relation}

^{of}

^{the}

form (1), of order

## d a,b = ^{a+b} _{a}

, valid for

## k > ^{a+b} _{a}

## − a − b

^{(with}

## F i = 0

^{for}

## i < 0

^{).}

^{This}proposition follows fromProposition 4 (Setion 5),whih deals with

the generating funtion of retangularShur funtions of height

## a

^{:}

^{for}

^{symmetri}

funtions in

## n

^{variables,}

## X

### k

## s k ^{a} z ^{k} = P (z)

## Q(z)

^{(19)}

where

## Q(z)

^{is}

^{given}

^{by}

^{(8)}

^{and}

^{has}

^{degree}

^{n} _{a}

,while

## P (z)

^{has}

^{degree}

^{n} _{a}

## − n

^{.}

Computational aspets. We have shown in Setion 2.1 that, given the step

set

## S

^{,}

^{the}

^{polynomial}

## D(t, z)

^{an}

^{be}

^{omputed}

^{via}

^{the}

^{platypus}

^{algorithm.}

^{One}

way to determine the numerator

## N (t, z)

^{is}

^{to}

^{ompute}

## F k

^{expliitly}

^{(e.g.}

^{as}

^{the}

determinant of

## (1 − tA ^{(k)} )

^{)}

^{for}

## k ≤ δ := ^{a+b} _{a}

## − a − b

^{,}

^{and}

^{then}

^{to}

^{ompute}

## N (t, z) = D(t, z) P

### k F k z ^{k}

^{up}

^{to}

^{the}

^{oeient}

^{of}

## z ^{δ}

^{.}

In the generi ase, omputing the generating funtion of the polynomials

## F _{k}

boils down to omputing the generating funtion (19). As disussed above, the

platypus algorithm an be used to determine

## Q(z)

^{in}

^{terms}

^{of}

^{the}

^{elementary}

symmetrifuntions. In order to determine

## P (z)

^{,}

^{we}

^{express}

^{the}

^{Shur}

^{funtions}

## s _{k} ^{a}

^{,}

^{for}

## k ≤ δ := ^{n} _{a}

## − n

^{,}

^{in}

^{the}

^{elementary}

^{basis.}

^{This}

^{an}

^{be}

^{done}

^{using}

^{the}

dualJaobiTrudiidentity(see Setion5fordetails). Onenallyobtains

## P (z)

^{by}

expanding the produt

## Q(z) P

### k s k ^{a} z ^{k}

^{in}

^{the}

^{elementary}

^{basis}

^{up}

^{to}

^{order}

## δ

^{.}

^{F}

^{or}

instane, for

## a = b = 2

^{,}

## X

### k≥0

## s k ^{a} z ^{k} = 1 − z ^{2} e 4

## Q(z) ,

where

## Q(z)

^{is}

^{given}

^{by}

^{(9).}

^{More}

^{values}

^{of}

## P (z)

^{are}

^{given}

^{in}

^{Setion}

^{7.2.}

^{Let}

^{us}

nowrevisit the examples of Setion2.1.

Example1: Twostepexursions. When

## S = { a, − 1 }

^{,}

^{one}

^{has}

## D(t, z) = 1 − z+

## t ^{a+1} z ^{a+1}

^{.}

^{The}polynomials

## F k

^{satisfy}

^{the}

^{reursion}

## F k = F k−1 − t ^{a+1} F k−a−1

^{,}

^{whih}

an be understood ombinatoriallyusing Viennot's theory of heaps of piees [33℄.

Viathistheory,

## F _{k}

^{appears}

^{as}

^{the}

^{generating}

^{funtion}

^{of}

^{trivial}

^{heaps}

^{of}

^{segments}

oflength

## a

^{on}

^{the}

^{line}

## J0, kK

^{,}

^{eah}

^{segment}

^{being}

^{weighted}

^{by}

## − t ^{a+1}

^{.}

^{The}

^{reursion}

is valid for

## k ≥ 1

^{,}

^{with}

## F _{0} = 1

^{and}

## F _{i} = 0

^{for}

## i < 0

^{.}

^{The}

^{generating}

^{funtion}

^{of}

the

## F k

^{'s}

^{is}

## X

### k≥0

## F k z ^{k} = 1

## 1 − z + t ^{a+1} z ^{a+1} .

When

## a = 3

^{and}

## b = 2

^{,}

^{the}

^{minimal}

^{polynomial}

^{of}

^{the}

^{exursion}

^{series}

## E

^{is}

^{given}

by (12) and the generating funtion of the polynomials

## F k

^{is}

^{found}

^{to}

^{be}

## X

### k≥0

## F k z ^{k} = 1 + t ^{5} z ^{5}

## 1 − z + t ^{5} z ^{5} (2 − z + z ^{2} ) + t ^{10} z ^{10} .

For

## a = 4

^{and}

## b = 3

^{,}

^{we}

^{refer}

^{to}

^{(13)}

^{for}

^{the}

^{minimal}

^{polynomial}

## D(t, z)

^{of}

## E

^{,}

and

## X

### k≥0

## F k z ^{k} = 1 + t ^{7} z ^{7} (4 + z ^{3} + z ^{4} ) + t ^{14} z ^{14} (6 + z ^{3} ) + 4 t ^{21} z ^{21} + t ^{28} z ^{28}

## D(t, z) .

Example 2: Basket-ball again. For

## S = {± 1, ± 2 }

^{with}

## ω −2 = ω 2 = t, ω −1 = ω 1 = 1

^{,}

## X

### k≥0

## F _{k} z ^{k} = 1 − t ^{2} z

## (1 + t ^{2} z) (1 − z(1 + 2t ^{2} ) + z ^{2} t ^{2} (3 + 2t ^{2} ) − z ^{3} t ^{4} (1 + 2 t ^{2} ) + z ^{4} t ^{8} ) .

The denominator is not irreduible. Its seond fator is the minimal polynomial

of

## E

^{,}

^{see}

^{(15).}

^{Moreover,}

^{omparing}

^{to}

^{(14)}

^{shows}

^{that}

## N (t, z )

^{and}

## D(t, z)

^{have}

^{a}

fator

## (1 + t ^{2} z)

^{in}

^{ommon.}

^{A}

^{similar}

^{phenomenon}

^{ours}

^{for}

## S = {± 1, ± 2 }

^{with}

## ω s = 1

^{for}

^{all}

## s

^{.}

^{In}

^{this}

^{ase,}

## X

### k≥0

## F k z ^{k} = 1 − tz

## (1 + zt) (1 − z (1 + 2 t) + t (2 + 3 t) z ^{2} − t ^{2} (1 + 2 t) z ^{3} + z ^{4} t ^{4} ) .

Again, the minimalpolynomialof

## E

^{is}

^{the}

^{seond}

^{fator}

^{of}

^{the}denominator,and

## N (t, z)

^{and}

## D(t, z)

^{have}

^{a}

^{fator}

## (1 + tz)

^{in}

^{ommon.}

3. Enumeration of unbounded exursions

Hereweestablishtheexpression(6)oftheexursiongeneratingfuntion

## E

^{.}

^{The}

proof is based ona step-by step onstrution of non-negative walks with steps in

## S

^{,}

^{and}

^{on}

^{the}

^{so-alled}

^{kernel}

^{method.}

^{This}

^{type}

^{of}

^{argument}

^{is}

^{by}

^{no}

^{means}

original. The proof that we are going topresent an be found in [6, Example 3℄,

then in [5℄, and nds its origin in [20, Ex. 2.2.1.4 and 2.2.1.11℄. The reason why

we repeat the proofis beause itwillbe adapted inSetion4 toountexursions

of bounded height.

Let

## W

^{be}

^{the}

^{set}

^{of}

^{walks}

^{that}

^{start}

^{from}

^{0,}

^{take}

^{their}

^{steps}

^{in}

## S

^{,}

^{and}

^{always}

remain at a non-negative level. Let

## W (t, u)

^{be}

^{their}

^{generating}

^{funtion,}

^{where}

the variable

## t

^{ounts}

^{the}

^{length,}

^{the}

^{variable}

## u

^{ounts}

^{the}

^{nal}

^{height,}

^{and}

^{eah}

step

## s ∈ S

^{is}

^{weighted}

^{by}

## ω s

^{:}

## W (t, u) = X

### (s ^{1} ,s ^{2} ,...,s n )∈W

## ω s 1 · · · ω s n t ^{n} u ^{s} ^{1} ^{+···+s} ^{n} .

We often denote

## W (t, u) ≡ W (u)

^{,}

^{and}

^{use}

^{the}

^{notation}

## W h

^{for}

^{the}

^{generating}

funtion of walks of

## W

^{ending}

^{at}

^{height}

## h

^{:}

## W (t, u) = X

### h≥0

## u ^{h} W h

^{where}

## W h = X

### (s 1 ,s 2 ,...,s n )∈W s 1 +···+s n =h

## ω s 1 · · · ω s n t ^{n} .

A non-empty walk of

## W

^{is}

^{obtained}

^{by}

^{adding}

^{a}

^{step}

^{of}

## S

^{at}

^{the}

^{end}

^{of}

^{another}

walk of

## W

^{.}

^{However,}

^{we}

^{must}

^{avoid}

^{adding}

^{a}

^{step}

## i

^{to}

^{a}

^{walk}

^{ending}

^{at}

^{height}

## j

^{,}

if

## i + j < 0

^{.}

^{This}

^{gives}

## W (u) = 1 + t X

### s∈S

## ω s u ^{s}

## !

## W (u) − t X

### i∈S,j≥0 i+j<0

## ω i u ^{i+j} W j .

Let

## min S = − b

^{.}

^{Rewrite}

^{the}

^{above}

^{equation}

^{so}

^{as}

^{to}

^{involve}

^{only}non-negative powers of

## u

^{:}

## u ^{b} (1 − tP (u))W (u) = u ^{b} − t

### b

## X

### h=1

## u ^{b−h} X

### i∈S ,j≥0 i+j=−h

## ω i W j ,

^{(20)}

with

## P (u) = P

### s∈S ω _{s} u ^{s} .

^{The}

^{oeient}

^{of}

## W (u)

^{is}

^{the}

^{kernel}

## K(u)

^{of}

^{the}

^{equation,}

given in (4). As above, we denote by

## U _{1} , . . . , U _{b}

(respetively ## U _{b+1} , . . . , U _{a+b}

^{)}

^{the}

roots of

## K(u)

^{that}

^{are}

^{nite}(respetively innite) at

## t = 0

^{.}

^{F}

^{or}

## 1 ≤ i ≤ b

^{,}

^{the}

series

## W (U i )

^{is}

^{well-dened}

^{(it}

^{is}

^{a}

^{formal}

^{power}

^{series}

^{in}

## t ^{1/b}

^{).}

^{The}

^{left-hand}

^{side}

of (20) vanishes for

## u = U i

^{,}

^{with}

## i ≤ b

^{,}

^{and}

^{so}

^{the}

^{right-hand}

^{side}

^{vanishes}

^{too.}

Butthe right-handside isapolynomialin

## u

^{,}

^{of}

^{degree}

## b

^{,}

^{leading}

^{oeient}

^{1,}

^{and}

it vanishesat

## u = U 1 , . . . , U b

^{.}

^{This}

^{gives}

## u ^{b} (1 − tP (u))W (u) =

### b

## Y

### i=1

## (u − U i ).

Asthe oeientof

## u ^{0}

^{in}

^{the}

^{kernel}

^{is}

## − tω −b

^{,}

^{setting}

## u = 0

^{in}

^{the}

^{above}

^{equation}

gives the generating funtion of exursions:

## E = W (0) = ( − 1) ^{b+1} tω −b

### b

## Y

### i=1

## U i .

This is the rst expression in(6). The seond follows using

## U _{1} · · · U _{a+b} = ( − 1) ^{a+b} ω _{−b} /ω _{a}

^{(21)}

(see (5)).

Remark. There exists an alternative way to solve (20), whih does not exploit

the fat that the right-hand side of (20) has degree

## b

^{in}

## u

^{.}

^{This}

^{variant}

^{will}

^{be}

useful in the enumeration of bounded exursions. Write

## Z −h = X

### i∈S,j≥0 i+j=−h

## ω i W j ,

so thatthe right-handside of (20) reads

## u ^{b} − t

### b

## X

### h=1

## u ^{b−h} Z −h .

This term vanishesfor

## u = U _{1} , . . . , U _{b}

^{.}

^{Hene}

^{the}

## b

^{series}

## Z _{−1} , . . . , Z _{−b}

^{satisfy}

^{the}

following system of

## b

^{linear}

^{equations:}

^{F}

^{or}

## U = U i

^{,}

^{with}

## 1 ≤ i ≤ b

^{,}

### b

## X

### h=1

## U ^{b−h} Z −h = U ^{b} /t.

Inmatrix form,we have

## MZ = C /t

^{,}

^{where}

## M

^{is}

^{the}

^{square}

^{matrix}

^{of}

^{size}

## b

^{given}

by

## M =

##

##

##

##

##

## U _{1} ^{b−1} U _{1} ^{b−2} · · · U _{1} ^{1} 1 U _{2} ^{b−1} U _{2} ^{b−2} · · · U _{2} ^{1} 1

.

.

.

.

.

.

## U _{b} ^{b−1} U _{b} ^{b−2} · · · U _{b} ^{1} 1

##

##

##

##

## ,

## Z

^{is}

^{the}

^{olumn}

^{vetor}

## (Z −1 , . . . , Z −b )

^{,}

^{and}

## C

^{is}

^{the}

^{olumn}

^{vetor}

## (U _{1} ^{b} , . . . , U _{b} ^{b} )

^{.}

The determinant of

## M

^{is}

^{the}

^{V}

^{andermonde}

^{in}

## U 1 , . . . , U b

^{,}

^{and}

^{it}

^{is}

^{non-zero}

^{be-}

ausethe

## U i

^{are}

^{distint.}

^{We}

^{are}

^{espeially}

^{interested}

^{in}

^{the}

^{unknown}

## Z −b = ω −b E

^{.}

Applying Cramer's rule to solve the above system yields

## Z _{−b} = ( − 1) ^{b+1} t

## det(U _{i} ^{b−j+1} ) 1≤i,j≤b

## det(U _{i} ^{b−j} ) 1≤i,j≤b

## .

The two determinantsoinide, up toa fator

## U 1 . . . U b

^{,}

^{and}

^{we}

^{nally}

^{obtain}

## E = Z −b

## ω −b

## = ( − 1) ^{b+1} tω −b

## U _{1} · · · U _{b} .

4. Enumeration of bounded exursions

AsarguedinSetion2.2,thegeneratingfuntionofexursions ofheightatmost

## k

^{is}

## E ^{(k)} = F k

## F k+1

## ,

^{(22)}

where

## F k+1 = det(1 − tA ^{(k)} )

^{and}

## A ^{(k)}

^{is}

^{the}

^{adjaeny}

^{matrix}

^{(16)}

^{desribing}

the allowed steps in the interval

## J0, kK

^{.}

^{In}

^{order}

^{to}

^{prove}Proposition 2, it re- mains to establish the expression (18) of the polynomial

## F _{k}

^{as}

^{a}

^{Shur}

^{funtion}

of

## U 1 , . . . , U a+b

^{.}

^{We}

^{give}

^{two}

^{proofs.}

^{The}

^{rst}

^{one}

^{uses}

^{the}

^{dual}

^{JaobiT}

^{rudi}

identity to identify

## F k

^{as}

^{a}

^{Shur}

^{funtion.}

^{The}

^{seond}

^{determines}

## E ^{(k)}

^{in}

^{terms}

of Shur funtions via the kernel method, and the Shur expression of

## F k

^{then}

follows from(22) by indution on

## k

^{(given}

^{that}

## F 0 = 1

^{).}

First proof via the JaobiTrudi identity. The dual JaobiTrudi identity

expresses Shurfuntionsasadeterminantinthe elementarysymmetrifuntions

## e i

^{[30,}

^{Cor.}

^{7.16.2℄:}

^{for}

^{any}

^{partition}

## λ

^{,}

## s λ = det

## e λ ^{′} _{j} +i−j

### 1≤i,j≤λ ^{1} ,

where

## λ ^{′}

^{is}

^{the}

^{onjugate}

^{of}

## λ

^{.}

^{Apply}

^{this}

^{identity}

^{to}

## λ = (k + 1) ^{a}

^{.}

^{Then}

## λ ^{′} = a ^{k+1}

and

## s (k+1) ^{a} = det J ^{(k)}

^{with}

## J ^{(k)} = (e a+i−j ) 1≤i,j≤k+1 .

Now,speializethistosymmetrifuntionsinthe

## a+b

^{variables}

## V = (V 1 , . . . , V a+b )

where

## V i = − U i

^{for}

^{all}

## i

^{.}

^{By}

^{(5),}

^{the}

^{elementary}

^{symmetri}

^{funtions}

^{of}

^{the}

## V i

^{are}

## e i ( V ) = ω a−i

## ω a − 1 tω a

## χ i=a = − 1 tω a

## (χ i=a − tω a−i ) .

This shows that the matrix

## J ^{(k)}

^{oinides}

^{with}

## − (1 − tA ^{(k)} )/(tω a )

^{,}

^{so}

^{that}

## s λ ( V ) = ( − tω a ) ^{−(k+1)} F k+1 = ( − 1) ^{a(k+1)} s λ ( U ),

sine

## s _{λ}

^{is}homogeneous of degree

## a(k + 1)

^{.}

^{This}

^{gives}

^{the}

^{Shur}

^{expression}

^{of}

## F _{k+1}

^{.}

Seond proof via the kernel method. We adapt the step by step approah

of Setion 3 to ount exursions of height at most

## k

^{.}

^{Let}

## W ^{(k)} (t, u) ≡ W ^{(k)} (u)

be the generating funtion of non-negative walks of height at most

## k

^{.}

^{As}

^{before,}

weountthemby theirlength(variable

## t

^{)}

^{and}

^{nal}

^{height}

^{(}

## u

^{)}

^{with}multipliative weights

## ω _{s}

^{on}

^{the}

^{steps.}

^{We}

^{use}

^{notations}

^{similar}

^{to}

^{those}

^{of}

^{Setion}

^{3.}

^{When}

onstruting walks step by step, we must still avoid going below level0, but also

above level

## k

^{.}

^{This}

^{yields:}

## W ^{(k)} (u) = 1 + t X

### s∈S

## ω s u ^{s}

## !

## W ^{(k)} (u) − t X

### i∈S,j≥0 i+j>k

^{or}

### i+j<0

## ω i u ^{i+j} W _{j} ^{(k)} ,

or,with

## min S = − b

^{,}

## u ^{b} (1 − tP (u))W ^{(k)} (u) = u ^{b} − t

### k+a

## X

### h=k+1

## u ^{b+h} Z _{h} ^{(k)} − t

### b

## X

### h=1

## u ^{b−h} Z _{−h} ^{(k)} ,

^{(23)}

where

## Z _{h} ^{(k)} = X

### i∈S,j≥0 i+j=h

## ω i W _{j} ^{(k)} .

The series

## W ^{(k)} (u)

^{is}

^{now}

^{a}

^{polynomial}

^{in}

## u

^{(with}

^{oeients}

^{in}

^{the}

^{ring}

^{of}

^{power}

series in

## t

^{).}

^{This}

^{implies}

^{that}

^{any}

^{root}

## U i

^{of}

^{the}

^{kernel}

## K(u) = u ^{b} (1 − tP (u))

^{an}

be legally substituted for

## u

^{in}

^{(23).}

^{The}

^{right-hand}

^{side}

^{and}

^{the}

^{left-hand}

^{side}

then vanish, and provide a system of

## a + b

^{linear}

^{equations}

^{satised}

^{by}

^{the}

## Z h

^{:}

For

## U = U i

^{,}

^{with}

## 1 ≤ i ≤ a + b

^{,}

### k+a

## X

### h=k+1

## U ^{b+h} Z _{h} ^{(k)} +

### b

## X

### h=1

## U ^{b−h} Z _{−h} ^{(k)} = U ^{b} /t.

In matrix form,wehave

## M ^{(k)} Z ^{(k)} = C /t

^{,}

^{where}

## M ^{(k)}

^{is}

^{the}

^{square}

^{matrix}

^{of}

^{size}

## a + b

^{given}

^{by}

## M ^{(k)} =

##

##

##

##

##

## U _{1} ^{a+b+k} U _{1} ^{a+b+k−1} · · · U _{1} ^{b+k+1} U _{1} ^{b−1} U _{1} ^{b−2} · · · 1

## U _{2} ^{a+b+k} · · · · · · 1

.

.

.

.

.

.

## U _{a+b} ^{a+b+k} U _{a+b} ^{a+b+k−1} · · · U _{a+b} ^{b+k+1} U _{a+b} ^{b−1} U _{a+b} ^{b−2} · · · 1

##

##

##

##

## ,

## Z ^{(k)}

^{is}

^{the}

^{olumn}

^{vetor}

## (Z _{k+a} ^{(k)} , . . . , Z _{k+1} ^{(k)} , Z _{−1} ^{(k)} , . . . , Z _{−b} ^{(k)} )

^{,}

^{and}

## C

^{is}

^{the}

^{olumn}

vetor

## (U _{1} ^{b} , . . . , U _{a+b} ^{b} )

^{.}

^{We}

^{are}

^{espeially}

^{interested}

^{in}

^{the}

^{series}

## Z _{−b} ^{(k)} = ω −b E ^{(k)}

^{.}