• 検索結果がありません。

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

N/A
N/A
Protected

シェア "The generating funtion E (k) (t)of Dykpaths of height at mostk is E (k"

Copied!
23
0
0

(1)

DISCRETE EXCURSIONS

MIREILLE BOUSQUET-MÉLOU

Abstrat. Itis wellknown thatthelengthgenerating funtion

### E(t)

of Dyk

paths(exursions with steps

) satises

. The generating

funtion

### E (k) (t)

of Dykpaths of height at most

is

, where

the

### F k

are polynomials in

given by

and

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

.

Thismeansthat thegeneratingfuntion of thesepolynomialsis

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

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

and of height at most

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

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

. The exursion generatingfuntion

isalge-

braiandsatises

(while

).

If

and

,thepolynomials

and

### N (t, z)

anbetaken

toberespetivelyofdegree

and

in

### z

. Thesedegreesare

ingeneraloptimal: forinstane,when

with

and

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,

## /(n + 1)

, isthe set of Dyk paths. These are one-dimensional walksthatstart andendat

,takesteps

## ± 1

,and alwaysremainatanon-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:

## C n t 2n .

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

(2)

## 3 2 1

Figure1. Left: A Dyk pathof length

## 16

and height4. 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 heightat most

:

and for

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

This reursionan beused toprovethat

## E (k)

isrational,andmore preisely, that

where

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

isknown

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

satisfyalinearreurrenerelation? Ofwhatorder? Howanone determine

this reursion? Notethat any linear reursion of order

, of the form

(1)

with

## a i ∈ Q[t]

, gives a non-linearreursion of order

for the series

,

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

(2)

and, by taking the limit

## k → ∞

, an algebrai equation of degree

satised by

:

## 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

(3)

and

## max S = a

. Thenthe exursiongeneratingfuntion

## E

is algebraiof degreeatmost

## d a,b :=

### a+b a

. The degree is exatly

## d a,b

in the generi ase (to be dened), but also

when

with

and

## b

oprime. Computing a polynomial of degree

thatannihilates

## E

boilsdown toomputingthe elementaryplethysms

onan

alphabet with

letters,for

## 0 ≤ k ≤ d a,b

.

Thegeneratingfuntion

## E (k)

ounting exursionsof heightatmost

## k

isrational

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

. Moreover,

## 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

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

. Thisisequivalenttoomputingthe generat-

ing funtion of retangular Shur funtions

, 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

,taketheirstepsinanite

set

## S ⊂ Z

, and always remain at a non-negative level. More formally, a (non- negative)walk oflength

willbeasequene

suhthatforall

## i ≤ n

, the partial sum

## s 1 + · · · + s i

isnon-negative. The nal level of this walk is

,anditsheightis

## max i s 1 + · · · +s i

. Anexursionisanon-negativewalk endingat level 0 (Figure1). Weare interested inthe enumeration of exursions.

Thegeneratingfuntionsweonsider arefairlygeneral,inthateverystep

## s ∈ S

is weighted by an element

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

## t

, transendental over

## K

. In partiular,

(4)

the generating funtion of exursions is

## ω 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

with oeients in

## K

. In one oasion (Example 2), we will then speialize

the indeterminates

## ω s

intopolynomials in

. The series

## E

beomesa well-dened

powerseries in

.

If

and

, we assume that

and

are non-zero. If

## d

divides all the elements of

## S

, the exursion generating funtion is unhanged if

we replaeeah

by

## s/d

(up toa renaming of the weights

## ω s

). Thus we an

always assumethat the elementsof

## S

are relativelyprime. Also,if

is anexursion,

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

isalso anexursion, with steps in

## −S

. Thus

the exursion series obtained for

and

## −S

oinide, up to a renaming of the

weights

## ω s

.

Theweightingofthewalksthatwehavedeneddependsonthelistofstepsthat

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

## Z

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

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

:

(3)

where

## u

isanewindeterminate. ThisisaLaurentpolynomialin

withoeients

in

. If

, we dene

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

(4)

This isnowapolynomialin

withoeientsin

. If

, thispolyno-

mialhas degree

in

. It has

## a + b

roots, whih are frational Laurent series

(Puiseuxseries)in

withoeientsin

## K

,analgebrailosureof

## K

. (Wereferthe

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

in

.) Exatly

## b

of these roots, say

, are nite at

## t = 0

. These roots

are atually formal power series in

## t 1/b

, and the rst term of

is

,

where

isa

## b

throotof unity. Inpartiular, these

## b

series are distint,and vanish

at

## t = 0

. We all them the small roots of

. The

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

, forsome

. Note that

fators as

## (u − U i ) ,

so thatthe elementary symmetrifuntions of the

'sare:

(5)

(5)

with

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

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

of

degree at most

## d a,b = a+ba

. It an be written as:

(6)

where

(respetively

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

) are the small (respetively large) roots of the polynomial

## K(u)

given by (4). The quantity dened by

(7)

with

and

## U i ,

is a polynomial in

and

with oeients in

, of degree

in

, satisfying

## D(t, E) = 0

.

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

deed,theseondexpressionof

showsthat

## D(t, E ) = 0

. Moreover, theexpression

of

## D(t, z)

is symmetriin the roots

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

, sothat its oeientsbelongto

## K(t)

. More preisely, the form (5) of the elementary symmetri funtions of the

's shows that

## D(t, z)

is a Laurent polynomial in

## t

. But the valuation of

in

is atleast

## − 1/a

,and this impliesthat

## D(t, z)

is a polynomialin

## t

.

Clearly,thedegreeof

in

is

## d a,b = a+ba

. Thusthe exursiongenerating

funtion

## E

has degree atmost

## d a,b

. WeproveinSetion 6that

## D(t, z)

isatually

irreduible inthe two following ases:

and

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

are independentindeter-

(6)

with

and

and

## b

oprime(two-stepexursions).

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

and

## z

that vanishes for

## z = E

. However, itsexpression (7)involves the series

## U i

,

while one would prefer to obtain an expliit polynomial in

and

. 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

and the weights

## ω s

are indeterminates,

## K(u)

is the general polynomial of degree

in

## u

, and the problem an be

rephrased asfollows: Take

variables

## u 1 , . . . , u n

,and expand thepolyno-

mial

## (1 − zu I )

(8)

in the basis of elementary symmetri funtions of

## u 1 , . . . , u n

. For instane, for

and

,

while for

,

## 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

## ( − z) k e k [e a ].

This shows that, inthe generiase, the problemof expressing

asa poly-

nomial in

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

and

## a

, all the elementary

symmetri funtions of the

## U i

's vanish, apart from

,

and

## e a+b ( U )

. It

would be a shame to ompute the general expansion of

## e k [e a ]

in the elementary

1

(7)

basis,andthenspeializemostofthe

to

## 0

. Theplatypusalgorithmdiretlygives

the expansion of

## e k [e a ]

modulo the ideal generated by the

, for

.

Forinstane, when

and

,

while for

and

,

and for

and

,

## + 3z 14 e 107 − z 15 e 5 e 107 + 2z 16 e 25 e 107 − z 21 e 157 .

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

ientof

in

## Q(z)

isalwaysa monomialin the

## e i

. Goingbak to the polynomial

, and given that

and

## ,

this would mean that the oeient of

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

and

,the oeient of

in

ontains

and

## e 83 e 38

.

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

polynomial

ofdegree

## n

withonstantterm1,anddene

impliitly

by

## (1 − zU k ).

The algorithmgivesa polynomialexpression of

with

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 aseries expansion

via

## = Φ a (p 1 , . . . , p a )

(10)

for some polynomial

## Φ a

. The rest of the alulation also uses series expansions, and goes asfollows:

ompute

for

using

,

(8)

ompute

## log Q(z)

up to the oeient of

using

(11)

ompute

## Q(z)

up tothe oeient of

using

.

Sine

has degree

## d

, the alulation is omplete. The identity (11) follows

from(10) and

## i e a (U 1i , . . . , U ni ).

Given a set of steps

, with

## max S = a

, one obtainsapolynomialexpression of

## D(t, z)

by applying the platypus algorithmto

## .

If the output of the algorithm is the polynomial

, 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

and

## ω a = ω −b = 1

. Wealways assume that

and

are

oprime.

If

## b = 1

,Proposition1gives

,where

## U

istheonlypowerseriessatisfying

. Equivalently,

## E = 1+t a+1 E a+1

. Thisequationanbeunderstood

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

.

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 forinstane[15,21,22,24℄. Itwouldbeinterestingtoworkout thepreise

## U i

. Toompareboth

types of results, take

and

## b = 2

. On the one hand, it is shown in [15℄ that

## E

is the rst omponent of the solutionof

## R 2 = tE L 3 = tE.

On the other hand, Proposition1 gives

,where

are the small

rootsof

## u 2 = t(1 + u 5 )

. The platypus algorithmgives

with

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

(12)

This polynomial isirreduible. Similarly,for

and

,

with

## + z 35 t 35 .

(13)

(9)

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+ba

.

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 = ω 1 = 1

, and then speializing

## ω = t

. Observe

thatthesmallrootsof

## u 2 = t(ω+u+u 3 +ωu 4 )

,involvedinProposition1,speialize into the smallroots

and

of

when

isset to

. We

obtain

## E = − U 1 U 2 /t 2

. The platypus algorithmyields

(14)

where

## 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:

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)

isdue tothesymmetry ofthe setof steps. Foreah

set

suhthat

andweights

suhthat

,the polynomial

## P (u)

given by(3)issymmetriin

and

. Inpartiular,

## a = b

. Thisimpliesthatthe

smallandlargerootsof

## 1 − tP (u)

anbegroupedbypairs:

## 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

atleast

),this explains

the fator

ourring in

## D(t, z)

. More generally, we prove in Setion 7

that if

## S

is symmetri, with symmetri weights, then the degree of

is at most

, 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

. Theseare walks onanite diretedgraph, sothatthe lassialtransfer-matrix method applies

2

. The verties of the graph are

## 0, 1, . . . , k

, and there is an edge

from

to

if

## j − i ∈ S

. The adjaenymatrix of this graph is

with

if

## 0

otherwise. (16)

2

In language theoreti terms, the words of

### S ∗

that enode these bounded exursions are

(10)

By onsidering the

thpower of

## A (k)

, it is easy to see [29, Ch. 4℄ that the series

## E (k)

ounting exursions of height at most

is the entry

in

## (1 − tA (k) ) −1

.

The translational invarianeof our step system gives

where

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

,where

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

variables

. Let

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

. For any integer partition

with at most

parts,

with

,

with

## a µ = det x µij

### 1≤i,j≤n .

(17)

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

is

where

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

is the olletion of roots of the polynomial

given

by (4), and

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

is a rational

funtion of

and

## z

.

Proposition 3. The generating funtion of the polynomials

is rational, and

an be written as

where

## D(t, z)

isgivenby (7), and

has degree

in

. Moreover,

and

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

In other words, the sequene

## F k

satises a linear reurrene relation of the

form (1), of order

, valid for

(with

for

## i < 0

). This proposition follows fromProposition 4 (Setion 5),whih deals with

(11)

the generating funtion of retangularShur funtions of height

: forsymmetri

funtions in

variables,

(19)

where

## Q(z)

is given by (8)and has degree

,while

has degree

## − n

.

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

set

, the polynomial

## D(t, z)

an be omputed via the platypus algorithm. One

way to determine the numerator

is to ompute

## F k

expliitly (e.g. as the

determinant of

) for

## − a − b

, and then to ompute

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

### k F k z k

up tothe oeientof

## 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

, for

## − 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

. For

instane, for

,

where

## Q(z)

is given by (9). More values of

## P (z)

are given in Setion7.2. Let us

nowrevisit the examples of Setion2.1.

Example1: Twostepexursions. When

,onehas

. Thepolynomials

## F k

satisfythereursion

## 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 asthegenerating funtionoftrivialheaps ofsegments

oflength

ontheline

## J0, kK

,eahsegmentbeingweightedby

. Thereursion

is valid for

, with

and

for

## i < 0

. The generating funtion of

the

's is

When

and

## b = 2

, the minimalpolynomialof the exursion series

## E

is given

by (12) and the generating funtion of the polynomials

is found to be

For

and

## b = 3

, we refer to (13) for the minimal polynomial

of

,

and

(12)

with

,

## (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, omparingto(14) shows that

and

havea

fator

## (1 + t 2 z)

inommon. Asimilar phenomenon ours for

with

for all

. In this ase,

## (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

isthe seond fator ofthe denominator,and

and

have afator

## (1 + tz)

inommon.

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

is weighted by

:

We often denote

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

, and use the notation

## W h

for the generating

funtion of walks of

endingat height

:

where

## ω s 1 · · · ω s n t n .

A non-empty walk of

## W

is obtained by addinga step of

## S

at the end of another

walk of

## i

toa walkending atheight

,

if

. This gives

(13)

Let

## min S = − b

. Rewrite the above equation so as to involve only non-negative powers of

:

(20)

with

Theoeientof

isthekernel

## K(u)

oftheequation,

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

(respetively

) the

roots of

## K(u)

that are nite (respetively innite) at

. For

, the

series

## W (U i )

iswell-dened (itisaformalpowerseries in

## t 1/b

). The left-handside

of (20) vanishes for

, with

## i ≤ b

, and so the right-hand side vanishes too.

Butthe right-handside isapolynomialin

,ofdegree

it vanishesat

. This gives

Asthe oeientof

inthe kernel is

, setting

## u = 0

inthe aboveequation

gives the generating funtion of exursions:

## 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

in

## u

. This variant will be

useful in the enumeration of bounded exursions. Write

## ω i W j ,

so thatthe right-handside of (20) reads

## u b−h Z −h .

This term vanishesfor

. Hene the

series

## Z −1 , . . . , Z −b

satisfy the

following system of

## b

linearequations: For

,with

,

## U b−h Z −h = U b /t.

(14)

Inmatrix form,we have

,where

## M

isthesquare matrixof size

given

by

.

.

.

.

.

.

## Z

is the olumn vetor

, and

## C

is the olumn vetor

## (U 1b , . . . , U bb )

.

The determinant of

## M

is the Vandermonde in

## U 1 , . . . , U b

, and it is non-zero be-

ausethe

## U i

aredistint. Weareespeiallyinterestedintheunknown

## Z −b = ω −b E

.

Applying Cramer's rule to solve the above system yields

## .

The two determinantsoinide, up toa fator

## U 1 . . . U b

,and wenally obtain

## U 1 · · · U b .

4. Enumeration of bounded exursions

AsarguedinSetion2.2,thegeneratingfuntionofexursions ofheightatmost

is

(22)

where

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 JaobiTrudi

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

(given that

## F 0 = 1

).

First proof via the JaobiTrudi identity. The dual JaobiTrudi identity

## e i

[30, Cor. 7.16.2℄: forany partition

,

where

isthe onjugateof

## λ

. Applythisidentityto

. Then

and

with

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

Now,speializethistosymmetrifuntionsinthe

variables

where

forall

## i

. By(5),the elementarysymmetrifuntions ofthe

are

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

(15)

This shows that the matrix

oinides with

, so that

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

. 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

) andnalheight(

## u

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

. This yields:

or

or,with

,

(23)

where

The series

## W (k) (u)

isnowapolynomialin

## u

(withoeientsinthering of power

series in

## t

). This impliesthat any root

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

:

For

, with

,

## U b−h Z −h(k) = U b /t.

In matrix form,wehave

,where

## M (k)

isthe square matrix of size

given by

.

.

.

.

.

.

## Z (k)

is the olumn vetor

, and

is the olumn

vetor

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

. We are espeially interested in the series

## Z −b(k) = ω −b E (k)

.

Now it makes sense to ask if the curve x(s) has a tangent at the limit point x 0 ; this is exactly the formulation of the gradient conjecture in the Riemannian case.. By the

[3] Chen Guowang and L¨ u Shengguan, Initial boundary value problem for three dimensional Ginzburg-Landau model equation in population problems, (Chi- nese) Acta Mathematicae

Kilbas; Conditions of the existence of a classical solution of a Cauchy type problem for the diffusion equation with the Riemann-Liouville partial derivative, Differential Equations,

By the algorithm in [1] for drawing framed link descriptions of branched covers of Seifert surfaces, a half circle should be drawn in each 1–handle, and then these eight half

Then it follows immediately from a suitable version of “Hensel’s Lemma” [cf., e.g., the argument of [4], Lemma 2.1] that S may be obtained, as the notation suggests, as the m A

We will give a different proof of a slightly weaker result, and then prove Theorem 7.3 below, which sharpens both results considerably; in both cases f denotes the canonical

Applying the representation theory of the supergroupGL(m | n) and the supergroup analogue of Schur-Weyl Duality it becomes straightforward to calculate the combinatorial effect

We provide an efficient formula for the colored Jones function of the simplest hyperbolic non-2-bridge knot, and using this formula, we provide numerical evidence for the