The generating funtion E (k) (t)of Dykpaths of height at mostk is E (k

(1)

DISCRETE EXCURSIONS

MIREILLE BOUSQUET-MÉLOU

Abstrat. Itis wellknown thatthelengthgenerating funtion

E(t)

^of ^Dyk

paths(exursions with steps

± 1

⁾ ^satises

1 − E + t ² E ² = 0

^. ^The ^generating

funtion

E ^(k) (t)

ôf ^Dyk^paths ôf ^height ât ^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 ² F k−1

^.

Thismeansthat thegeneratingfuntion of thesepolynomialsis

P

k≥0 F k z ^k = 1/(1 − z + t ² z ² )

^. ^We^note^that ^thedenominator 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

ând ôf ^height ât ^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

^,^thepolynomials

D(t, z)

^and

N (t, z)

^an^be^taken

toberespetivelyofdegree

d a,b = ^a+b _a

and

d a,b − a − b

ⁱⁿ

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 = ²ⁿ _n

/(n + 1)

^, îs^the ^set ôf ^Dyk ^paths. ^These âre one-dimensional walksthatstart andendat

0

^,^take^steps

± 1

^,ând âlways^remainâtânon-negative level (Figure1,left). Byfatoring suhwalksat their rst returnto 0,one easily

proves that their length generating funtion

E ≡ E(t)

îs âlgebrai, ând ^satises

E = 1 + t ² E ² .

This immediatelyyields:

E = 1 − √

1 − 4t ²

2t ² = X

n≥0

C n t ²ⁿ .

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

(2)

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)

ôunting ^Dyk ^paths ôf ^heightât ^most

k

^:

E ⁽⁰⁾ = 1

^and ^for

k ≥ 1, E ^(k) = 1 + t ² 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 ² 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â^linear^reurrene^relation? Ôf^whatôrder? ^Howânône ^determine

this reursion? Notethat any linear reursion of order

d

^, ^of ^the ^form

d

X

i=0

a i F k−i = 0

⁽¹⁾

with

a _i ∈ Q[t]

^, ^gives â ^non-linear^reursion ôf ôrder

d

^for ^the ^series

E ^(k)

^,

d

X

i=0

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

⁽²⁾

and, by taking the limit

k → ∞

^, ân âlgebrai êquation ôf ^degree

d

^satised ^by

E = lim k E ^(k)

^:

d

X

i=0

a i E ⁱ = 0.

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

sequene

F k

^and ^the algebraiity of

E

^. ^The ônnetion ^between ⁽¹⁾ ând ⁽²⁾ îs

entralinthe reent paper[2℄dealing with exursions with steps

± 1, ± 2

^.

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

(3)

summaryofouranswerstotheabovequestions. Assume

min S = − b

^and

max S = a

^. ^Then^the ^exursion^generating^funtion

E

îs âlgebraiôf ^degreeât^most

d a,b :=

a+b a

. The degree is exatly

d _a,b

ⁱⁿ ^the ^generi ^ase ^(to ^be ^dened), ^but ^also

when

S = {− b, a }

^with

a

^and

b

ôprime. ^Computing â ^polynomial ôf ^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)

ôunting êxursionsôf ^heightât^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

ân^beêxpressed âsâ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 ⁱⁿ ^[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îsêquivalent^toômputing^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ⁱⁿ^a^nite

set

S ⊂ Z

^, ând âlways ^remain ât â non-negative level. More formally, a (non- negative)walk oflength

n

^will^be^a^sequene

(s ₁ , s ₂ , . . . , s _n ) ∈ S ⁿ

^suh^that^for^all

i ≤ n

^, ^the ^partial ^sum

s 1 + · · · + s i

^isnon-negative. The nal level of this walk is

s ₁ + · · · +s _n

^,ândîts^heightîs

max _i s ₁ + · · · +s _i

^. Ânêxursionîsâ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 ôf ^the ^walks îs ^taken înto

aount by an additional indeterminate

t

^, transendental over

K

^. ^In ^partiular,

(4)

the generating funtion of exursions is

E := X

ω s 1 · · · ω s n t ⁿ ,

where the sum runs over all exursions

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

^. ^This ^is ^a ^power ^series ⁱⁿ

t

^with ^oeients ⁱⁿ

K

^. În ône ôasion ^(Example ^2), ^we ^will ^then ^speialize

the indeterminates

ω s

^intopolynomials 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 êxursion ^generating ^funtion îs ûnhanged îf

we replaeeah

s ∈ S

^by

s/d

^(up ^to^a ^renaming ^of ^the ^weights

ω _s

^). ^Thus ^we ^an

always assumethat the elementsof

S

âre ^relatively^prime. Âlso,îf

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

is anexursion,

( − s _n , . . . , − s ₂ , − s ₁ )

îsâlso ânêxursion, ^with ^steps ⁱⁿ

−S

^. ^Thus

the exursion series obtained for

S

^and

−S

ôinide, ûp ^to â ^renaming ôf ^the

weights

ω s

^.

Theweightingofthewalksthatwehavedeneddependsonthelistofstepsthat

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

Z

^. ^Fôr înstane, ^we ânnot

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 ,

⁽³⁾

where

u

^is^a^newindeterminate. ThisisaLaurentpolynomialin

u

^with^oeients

in

K

^. ^If

min S = − b

^, ^we ^dene

K(u) = u ^b (1 − tP (u)) .

⁽⁴⁾

This isnowapolynomialin

u

^with^oeientsⁱⁿ

K [t]

^. ^If

max S = a

^, ^this^polyno-

mialhas degree

a + b

ⁱⁿ

u

^. ^It ^has

a + b

^roots, ^whih ^are ^frational ^Laurent ^series

(Puiseuxseries)in

t

^with^oeientsⁱⁿ

K

^,ânâlgebrai^losureôf

K

^. ^(We^refer^the

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

in

K[t]

^.) ^Exatly

b

^of ^these ^roots, ^say

U ₁ , . . . , 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

ξ ⁱ (tω −b ) ^1/b

^,

where

ξ

^is^a

b

^th^rootôf ûnity^. În^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 ⁱⁿ

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) ⁱ ω 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 symmetri 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

^, ând ôn â ^related fatorization of formal power series. The expression 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 ⁱⁿ ⁽⁶⁾ ^below. ^We ^repeat ⁱⁿ ^Setion ³ ^the ^proof ^of ⁽⁶⁾

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

,

⁽⁶⁾

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 ) ,

⁽⁷⁾

with

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

^and

U I = Y

i∈I

U i ,

is a polynomial in

t

^and

z

^with ^oeients ⁱⁿ

K

^, ^of ^degree

d a,b

ⁱⁿ

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ⁱⁿ ^the ^roots

U ₁ , . . . , U _a+b

^, ^so^that ^its ^oeients^belong^to

K(t)

^. ^More ^preisely^, ^the ^form ⁽⁵⁾ ôf ^the êlementary ^symmetri ^funtions ôf ^the

U i

^'s ^shows ^that

D(t, z)

^is ^a ^Laurent ^polynomial ⁱⁿ

t

^. ^But ^the ^valuation ^of

U i

ⁱⁿ

t

is atleast

− 1/a

^,^and ^this ^implies^that

D(t, z)

^is ^a ^polynomialⁱⁿ

t

^.

Clearly,thedegreeof

D(t, z)

ⁱⁿ

z

^is

d a,b = ^a+b _a

. Thusthe exursiongenerating

funtion

E

^has ^degree ^at^most

d a,b

^. ^We^proveⁱⁿ^Setion ⁶^that

D(t, z)

^is^atually

irreduible inthe two following ases:

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

^and

ω −b , . . . , ω a

^are independentindeter-

(6)

• S = {− b, a }

^with

ω −b = ω a = 1

^and

a

^and

b

^oprime^(two-stepexursions).

As shown by Example2 below,

D(t, z)

^is ^not ^always irreduible.

An algebrai equation for

E

^. Âs ârgued âbove,

D(t, z)

^is ^a ^polynomial ⁱⁿ

t

and

z

^that ^vanishes ^for

z = E

^. ^However, îtsêxpression ⁽⁷⁾învolves ^the ^series

U i

^,

while one would prefer to obtain an expliit polynomial in

t

^and

z

^. ^Reall ^that

the series

U i

âre ônly ^known ^via ^their êlementary ^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

ⁱⁿ

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 )

⁽⁸⁾

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 ² (u ² ₁ u 2 u 3 + u 1 u ² ₂ u 3 + u 1 u 2 u ² ₃ ) − z ³ (u 1 u 2 u 3 ) ²

= 1 − ze 2 + z ² e 3,1 − z ³ e 3,3 ,

while for

a = b = 2

^,

Q(z) = 1 − ze ₂ +z ² (e _3,1 − e ₄ ) − z ³ (e _3,3 +e _4,1,1 − 2e _4,2 )+z ⁴ e ₄ (e _3,1 − e ₄ ) − z ⁵ e _4,4,2 +z ⁶ 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

îs êquivalent ^to êxpanding ^the ^plethysms

e k [e a ]

ⁱⁿ ^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 ]

ⁱⁿ ^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 ]

ⁱⁿ ^the ^elementary

1

(7)

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 ³ e ² ₃ ,

while for

a = 2

^and

b = 3

^,

Q(z) ≡ 1 − ze 2 − 2z ⁵ e ² ₅ + z ⁶ e 2 e ² ₅ − z ⁷ e ² ₂ e ² ₅ + z ¹⁰ e ⁴ ₅ .

and for

a = 5

^and

b = 2

^,

Q(z) ≡ 1 − ze 5 − 3z ⁷ e ⁵ ₇ + 2z ⁸ e 5 e ⁵ ₇ − 2z ⁹ e ² ₅ e ⁵ ₇ + z ¹⁰ e ³ ₅ e ⁵ ₇ − z ¹¹ e ⁴ ₅ e ⁵ ₇

+ 3z ¹⁴ e ¹⁰ ₇ − z ¹⁵ e ₅ e ¹⁰ ₇ + 2z ¹⁶ e ² ₅ e ¹⁰ ₇ − z ²¹ e ¹⁵ ₇ .

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

ientof

z ^k

ⁱⁿ

Q(z)

îsâlwaysâ ^monomialⁱⁿ ^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

ⁱⁿ

D(t, z)

îs âlways â ^monomial ⁱⁿ

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 ¹⁶

ⁱⁿ

Q(z)

^ontains

e ⁶ ₈

^and

e ⁸ ₃ e ³ ₈

^.

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 = ⁿ _a

and

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

^. ^The ônly ^general îdentity ^that îs ^needed îs

the expansion of

e a

ⁱⁿ ^power ^sums. ^This ân ^be ôbtained ^from â^series êxpansion

via

e _a = [z ^a ] exp − X

i≥1

( − z) ⁱ i p _i

!

= Φ _a (p ₁ , . . . , p _a )

⁽¹⁰⁾

for some polynomial

Φ a

^. ^The ^rest ôf ^the âlulation âlso ûses ^series expansions, and goes asfollows:

•

^ompute

p i ( U )

^for

1 ≤ i ≤ ad

^using

p i ( U ) = i[z ⁱ ] log(1/L(z))

^,

(8)

•

^ompute

log Q(z)

ûp ^to ^the ôeient ôf

z ^d

^using

log Q(z) = − X

i≥1

z ⁱ

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

⁽¹¹⁾

•

^ompute

Q(z)

ûp ^to^the ôeient ôf

z ^d

^using

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

^.

Sine

Q(z)

^has ^degree

d

^, ^the âlulation îs ômplete. ^The îdentity ⁽¹¹⁾ ^follows

from(10) and

log Q(z) = − X

i≥1

z ⁱ i

X

|I|=a

U _I ⁱ = − X

i≥1

z ⁱ

i e a (U ₁ ⁱ , . . . , U _n ⁱ ).

Given a set of steps

S

^, ^with

max S = a

^, ône ôbtainsâ^polynomialêxpression ôf

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êquationân^beûnderstood

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

^, ît îs ^still ^possible, ^but ^more ^diult, ^to ^write ^diretly â ^system ôf

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

E

^. ^See ^for^instane^[15,^21,^22,^24℄. ^It^would^beinterestingtoworkout thepreise

linkbetween theomponentsof thesesystemsand theseries

U i

^. ^T^o^ompare^both

types of results, take

a = 3

^and

b = 2

^. Ôn ^the ône ^hand, ît îs ^shown ⁱⁿ ^[15℄ ^that

E

îs ^the ^rst ômponent ôf ^the ^solutionôf







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 ² = t(1 + u ⁵ )

^. ^The ^platypus ^algorithm^gives

D(t, E) = 0

^with

D(t, z) = 1 − z + t ⁵ z ⁵ (2 − z + z ² ) + t ¹⁰ z ¹⁰ .

⁽¹²⁾

This polynomial isirreduible. Similarly,for

a = 4

^and

b = 3

^,

D(t, E) = 0

^with

D(t, z) = 1 − z + t ⁷ z ⁷ 5 − 4 z + z ² + 3 z ³ − z ⁵ + z ⁶

+ t ¹⁴ z ¹⁴ 10 − 6 z + 3 z ² + 5 z ³ − z ⁴ + z ⁵ + t ²¹ z ²¹ 10 − 4 z + 3 z ² + z ³ − z ⁴

+ t ²⁸ z ²⁸ 5 − z + z ² − z ³

+ z ³⁵ t ³⁵ .

⁽¹³⁾

(9)

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

D(t, z)

îs âlways îrre-

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

ω ₋₂ = ω ₂ = ω

^and

ω ₋₁ = ω ₁ = 1

^, ^and ^then speializing

ω = t

^. ^Observe

thatthesmallrootsof

u ² = t(ω+u+u ³ +ωu ⁴ )

^,^involvedⁱⁿProposition1,speialize into the smallroots

U ₁

^and

U ₂

^of

u ² = t(t + u + u ³ + tu ⁴ )

^when

ω

^is^set ^to

t

^. ^W^e

obtain

E = − U 1 U 2 /t ²

^. ^The ^platypus ^algorithm^yields

D(t, z ) = ¯ D(t, z)(1 + t ² z) ² ,

⁽¹⁴⁾

where

D(t, z) = ¯ t ⁸ z ⁴ − t ⁴ 1 + 2 t ²

z ³ + t ² 3 + 2 t ²

z ² − 1 + 2 t ²

z + 1

⁽¹⁵⁾

is the minimal polynomial of

E

^. ^This fatorization is an interesting phenomenon, whih is not related to the unequal lengths of the steps. Indeed, the same

phenomenon ours when

S = {± 1, ± 2 }

ând âll ^weights âre ^1. În ^this âse, ône

nds:

D(t, z) = ¯ D(t, z)(1 + tz) ²

with

D(t, z) = ¯ t ⁴ z ⁴ − t ² (2t + 1)z ³ + t(3t + 2)z ² − (2t + 1)z + 1,

so thatthe exursiongenerating funtion has degree 4 again.

Thefatorization of

D(t, z)

îs^due ^to^the^symmetry ôf^the ^setôf ^steps. ^Forêah

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 ⁽⁷⁾ ^ontains ^the

fator

(1 + tω a z)

^at^least

_a/2 ^a

times. Inthe basket-ballase (

a = 2

^),^this ^explains

the fator

(1 + tz) ²

^ourring ⁱⁿ

D(t, z)

^. ^More ^generally, ^we ^prove ⁱⁿ ^Setion ⁷

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âre ^walks ônâ^nite ^direted^graph, ^so^that^the ^lassialtransfer-matrix method applies

2

. The verties of the graph are

0, 1, . . . , k

^, ând ^there îs ân êdge

from

i

^to

j

^if

j − i ∈ S

^. ^The âdjaeny^matrix ôf ^this ^graph îs

A ^(k) = (A _i,j ) _0≤i,j≤k

with

A i,j =

ω _j−i

^if

j − i ∈ S ,

0

^otherwise. ⁽¹⁶⁾

2

In language theoreti terms, the words of

S ^∗

^that ênode ^these ^bounded êxursions âre

(10)

By onsidering the

n

^th^power ^of

A ^(k)

^, ît îs êasy ^to ^see ^[29, ^Ch. ^4℄ ^that ^the ^series

E ^(k)

ôunting êxursions ôf ^height ât ^most

k

^is ^the ^entry

(0, 0)

ⁱⁿ

(1 − tA ^(k) ) ⁻¹

^.

The translational invarianeof our step system gives

E ^(k) = F _k F k+1

where

F ₀ = 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ôr âny înteger ^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 .

⁽¹⁷⁾

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 )

îs ^the ôlle^tion ôf ^roots ôf ^the ^polynomial

K(u)

^given

by (4), and

F k+1 = det(1 − tA ^(k) )

^where

A ^(k)

îs ^the âdjaeny ^matrix ^(16). În

partiular,

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

⁽¹⁸⁾

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

ⁱⁿ

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

(11)

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)

⁽¹⁹⁾

where

Q(z)

^is ^given ^by ⁽⁸⁾^and ^has ^degree

ⁿ _a

,while

P (z)

^has ^degree

ⁿ _a

− n

^.

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

set

S

^, ^the ^polynomial

D(t, z)

ân ^be ômputed ^via ^the ^platypus âlgorithm. Ône

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

ûp ^to^the ôeientôf

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)

ⁱⁿ ^terms ^of ^the ^elementary

symmetrifuntions. In order to determine

P (z)

^, ^we ^express ^the ^Shur ^funtions

s _k ^a

^, ^for

k ≤ δ := ⁿ _a

− n

^, ⁱⁿ ^the êlementary ^basis. ^This ân ^be ^done ûsing ^the

dualJaobiTrudiidentity(see Setion5fordetails). Onenallyobtains

P (z)

^by

expanding the produt

Q(z) P

k s k ^a z ^k

ⁱⁿ ^the êlementary ^basis ûp ^to ôrder

δ

^. ^F^or

instane, for

a = b = 2

^,

X

k≥0

s k ^a z ^k = 1 − z ² e 4

Q(z) ,

where

Q(z)

^is ^given ^by ^(9). ^More ^values ^of

P (z)

^are ^given ⁱⁿ ^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

^. ^Thepolynomials

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

âppears âs^the^generating ^funtionôf^trivial^heaps ôf^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 ₀ = 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 ⁵ z ⁵

1 − z + t ⁵ z ⁵ (2 − z + z ² ) + t ¹⁰ z ¹⁰ .

For

a = 4

^and

b = 3

^, ^we ^refer ^to ⁽¹³⁾ ^for ^the ^minimal ^polynomial

D(t, z)

^of

E

^,

and

X

k≥0

F k z ^k = 1 + t ⁷ z ⁷ (4 + z ³ + z ⁴ ) + t ¹⁴ z ¹⁴ (6 + z ³ ) + 4 t ²¹ z ²¹ + t ²⁸ z ²⁸

D(t, z) .

(12)

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 ² z

(1 + t ² z) (1 − z(1 + 2t ² ) + z ² t ² (3 + 2t ² ) − z ³ t ⁴ (1 + 2 t ² ) + z ⁴ t ⁸ ) .

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

of

E

^,^see ^(15). ^Moreover, ^omparing^to⁽¹⁴⁾ ^shows ^that

N (t, z )

^and

D(t, z)

^have^a

fator

(1 + t ² z)

ⁱⁿômmon. Â^similar ^phenomenon ôurs ^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 ² − t ² (1 + 2 t) z ³ + z ⁴ t ⁴ ) .

Again, the minimalpolynomialof

E

^is^the ^seond ^fator ^of^the denominator,and

N (t, z)

^and

D(t, z)

^have ^a^fator

(1 + tz)

ⁱⁿ^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

^, ând ôn ^the ^so-alled ^kernel ^method. ^This ^type ôf ârgument îs ^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 ⁱⁿ

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

ôunts ^the ^nal ^height, ând êah

step

s ∈ S

^is ^weighted ^by

ω s

^:

W (t, u) = X

(s ¹ ,s ² ,...,s n )∈W

ω s 1 · · · ω s n t ⁿ u ^s ¹ ^+···+s ⁿ .

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 ⁿ .

A non-empty walk of

W

îs ôbtained ^by âddingâ ^step ôf

S

ât ^the ênd ôf ânother

walk of

W

^. ^However, ^we^must âvoidâddingâ^step

i

^toâ ^walkênding ât^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 .

(13)

Let

min S = − b

^. ^Rewrite ^the âbove êquation ^so âs ^to învolve ônly 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 ,

⁽²⁰⁾

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 ₁ , . . . , 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 )

îs^well-dened ^(itîsâ^formal^power^series ⁱⁿ

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 ⁰

ⁱⁿ^the ^kernel ^is

− tω −b

^, ^setting

u = 0

ⁱⁿ^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 ₁ · · · U _a+b = ( − 1) ^a+b ω _−b /ω _a

⁽²¹⁾

(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

ⁱⁿ

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 ₁ , . . . , U _b

^. ^Hene ^the

b

^series

Z ₋₁ , . . . , 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.

(14)

Inmatrix form,we have

MZ = C /t

^,^where

M

^is^the^square ^matrix^of ^size

b

^given

by

M =







U ₁ ^b−1 U ₁ ^b−2 · · · U ₁ ¹ 1 U ₂ ^b−1 U ₂ ^b−2 · · · U ₂ ¹ 1

.

U _b ^b−1 U _b ^b−2 · · · U _b ¹ 1





 ,

Z

^is ^the ^olumn ^vetor

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

^, ^and

C

(U ₁ ^b , . . . , U _b ^b )

^.

The determinant of

M

^is ^the ^V^andermonde ⁱⁿ

U 1 , . . . , U b

^, ând ît îs ^non-zero ^be-

ausethe

U i

âre^distint. ^Weâreêspeiallyînterestedⁱⁿ^theûnknown

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 ₁ · · · U _b .

4. Enumeration of bounded exursions

AsarguedinSetion2.2,thegeneratingfuntionofexursions ofheightatmost

k

^is

E ^(k) = F k

F k+1

,

⁽²²⁾

where

F k+1 = det(1 − tA ^(k) )

^and

A ^(k)

^is ^the ^adjaeny ^matrix ⁽¹⁶⁾ ^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)

ⁱⁿ ^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≤λ ¹ ,

where

λ ^′

îs^the ônjugateôf

λ

^. ^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 ) .

(15)

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

⁾^withmultipliative weights

ω _s

ôn ^the ^steps. ^We ûse ^notations ^similar ^to ^those ôf ^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) ,

⁽²³⁾

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ⁱⁿ

u

^(with^oeientsⁱⁿ^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

ⁱⁿ ^(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 ₁ ^a+b+k U ₁ ^a+b+k−1 · · · U ₁ ^b+k+1 U ₁ ^b−1 U ₁ ^b−2 · · · 1

U ₂ ^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

The generating funtion E (k) (t)of Dykpaths of height at mostk is E (k

E(t)

± 1

1 − E + t 2 E 2 = 0

E (k) (t)

k

E (k) = F k /F k+1

F k

t

F 0 = F 1 = 1

F k+1 = F k − t 2 F k−1

P

k≥0 F k z k = 1/(1 − z + t 2 z 2 )

E(t)

S

E (k) (t)

S

k

F k /F k+1

Q [t]

P

k≥0 F k z k = N(t, z)/D(t, z)

E(t)

D(t, E(t)) = 0

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

max S = a

min S = b

D(t, z)

N (t, z)

d a,b = a+b a

d a,b − a − b

z

S = { a, − b }

a

b

D(t, z)

E(t)

C n = 2n n

/(n + 1)

0

± 1

E ≡ E(t)

E = 1 + t 2 E 2 .

E = 1 − √

1 − 4t 2

2t 2 = X

n≥0

C n t 2n .

4 5 6 7 8

3 2 1

4 5 6 7 8

3 2 1

16

8

S = {− 3, 5 }

E (k) ≡ E (k) (t)

k

E (0) = 1

k ≥ 1, E (k) = 1 + t 2 E (k−1) E (k) .

E (k)

E (k) = F k

F k+1

,

F 0 = F 1 = 1

F k+1 = F k − t 2 F k−1 .

S ⊂ Z

E

E (k)

F k /F k+1

F k

(F k ) k

d

d

X

i=0

a i F k−i = 0

a i ∈ Q[t]

d

E (k)

d

1 − E + t ² E ² = 0

E ^(k) (t)

E ^(k) = F k /F k+1

F k+1 = F k − t ² F k−1

k≥0 F k z ^k = 1/(1 − z + t ² z ² )

E ^(k) (t)

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

d a,b = ^a+b _a

C _n = ²ⁿ _n

E = 1 + t ² E ² .

1 − 4t ²

2t ² = X

C n t ²ⁿ .

E ^(k) ≡ E ^(k) (t)

E ⁽⁰⁾ = 1

k ≥ 1, E ^(k) = 1 + t ² E ^(k−1) E ^(k) .

E ^(k)

E ^(k) = F _k

F k+1 = F k − t ² F k−1 .

E ^(k)

a _i ∈ Q[t]

E ^(k)

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

E = lim k E ^(k)

a i E ⁱ = 0.

d _a,b

d _a,b

0 ≤ k ≤ d _a,b

E ^(k)

k F k z ^k

k s k ^a z ^k

(s ₁ , s ₂ , . . . , s _n ) ∈ S ⁿ

s ₁ + · · · +s _n

max _i s ₁ + · · · +s _i

ω s 1 · · · ω s n t ⁿ ,