д ьь ш п × з жщш ж

Lattie walks everywhere
j
m
b2
c1
a0
b1
jf
c1
b1
if
m
Mireille Bousquet-Mélou, CNRS, LaBRI, U. Bordeaux 1, Frane
i
1. Continued frations [1980℄
1
1 − c0 −
1 − c1 −
a1 b2
1 −···
b1
a0
2. A storage alloation sheme [1986℄
p
size
b2
c1
a0 b1
c1
b1
j
m
m
p
2(p + q) = 1
q
q
jf
!!!
if
m
i
3. A paking problem [1998℄, with Comann, Flatto and Hofri
Two papers
1. Basi analyti ombinatoris of direted lattie paths (with C. Banderier,
2002)
2. The enumeration of prudent polygons by area and its unusual asymptotis
(with N. Beaton and T. Guttmann, 2011)
spei problems
general solutions
I. Basi analyti ombinatoris
of direted lattie paths
(with C. Banderier, 2002)
The problem
Let S ⊂ Z be a nite subset of steps.
Consider walks on Z, starting from 0, that take
their steps in S .
•
The problem
Let S ⊂ Z be a nite subsets of steps.
Consider walks on Z, starting from 0, that take
their steps in S .
•
What is the generating funtion of...
general walks?
bridges?
•
W (z, u)
z:
meanders?
11111111111
00000000000
00000000
11111111
00000000000 11111111
11111111111
00000000
B(z)
the number of steps, or length;
exursions?
E(z)
u:
M (z, u)
the height of the nal point
Results
1. Exat expressions of the series [Gessel 80℄
+ [MBM-Petkov²ek 00℄, [Banderier, MBM, Denise, Flajolet, Gardy, Gouyou-Beauhamps 02℄
2. Uniform asymptoti results
2. Uniform limit laws
general walks
W (z, u)
bridges
B(z)
exursions
meanders
11111111111
00000000000
00000000
11111111
00000000000 11111111
11111111111
00000000
E(z)
M (z, u)
Exat expressions of the series: general walks and bridges
Let −m = min S and M = max S , and let
P (u) =
X
i∈S
ωiui =
M
X
ωiui
i=−m
be the generating polynomial of (possibly weighted) steps.
•
The generating funtion of general walks is
1
.
W (z, u) =
1 − zP (u)
Exat expressions of the series: general walks and bridges
Let −m = min S and M = max S , and let
P (u) =
X
i∈S
ωiui =
M
X
ωiui
i=−m
be the generating polynomial of (possibly weighted) steps.
•
The generating funtion of general walks is
1
.
W (z, u) =
1 − zP (u)
The oeient of u0 in W (z, u) ounts bridges. It an be obtained from a
partial fration expansion in u:
•
m U ′(z)
X
i
,
B(z) = z
i=1 Ui(z)
where U1(z), . . . , Um(z) are the m solutions of 1 − zP (U ) = 0 that are nite at
z = 0.
Exat expressions of the series: exursions and meanders
•
The generating funtion of exursions is
m
(−1)m−1 Y
Ui(z)
E(z) =
zω−m i=1
where U1(z), . . . , Um(z) are the m solutions of 1 − zP (U ) = 0 that are nite at
z = 0.
•
More generally, the generating funtion of meanders is
Qm
(u − Ui(z))
.
M (z, u) = i=1
m
u (1 − zP (u))
Proof: a funtional equation and the kernel method
•
Step-by-step onstrution of meanders: If S = {−2, 3}, then
M (z, u)
=
1
+
3
z(u + u
−2
)M (z, u)
−
z M0(z)u
−2
+ M1(z)u
add an arbitrary step...
... but if the nal level is
0
or
1
one should not add a down step
−1
Proof: a funtional equation and the kernel method
Equivalently,
u
2
3
1 − z(u + u
−2
) M (z, u) = u2 − zM0(z) − zM1(z)u
The left-hand side vanishes when u = U1(z) and u = U2(z), where U1 and U2
are the two roots of
•
that are nite when z = 0.
1 − z(u3 + u−2) = 0
The right-hand side is a polynomial in u of degree 2, leading oeient 1,
that anels when u = U1(z) and u = U2(z). Hene
•
u
2
3
1 − z(u + u
and the expression
−2
) M (z, u) = (u − U1(z))(u − U2(z))
M (z, u) =
follows.
(u − U1(z))(u − U2(z))
u2(1 − z(u3 + u−2))
Two stowaways
•
A bijetion shows that
Hene
E ′(z)
B(z) = 1 + z
.
E(z)
m U ′(z)
X
i
B(z) = z
i=1 Ui(z)
⇒
E(z) =
(The onstant is the easily determined using
st
m
Y
z i=1
E(0) = 1.)
Ui(z).
Two stowaways
•
A bijetion shows that
Hene
E ′(z)
B(z) = 1 + z
.
E(z)
m U ′(z)
X
i
B(z) = z
i=1 Ui(z)
⇒
E(z) =
(The onstant is the easily determined using
st
m
Y
z i=1
E(0) = 1.)
Ui(z).
An algorithm, based on symmetri funtions manipulations, omputes an algebrai equation for the
exursion generating funtion
•
m
(−1)m−1 Y
E(z) =
Ui(z)
z
i=1
In plethysti notation, it expresses the symmetri funtions ej [em] in terms of the ei's.
The platypus algorithm
Asymptotis for bridges and exursions
Theorem. Let τ > 0 be the unique solution of P ′(τ ) = 0, where P is the
generating polynomial of steps.
Then the numbers of bridges and exursions of length n behave asymptotially
as
b1
n
−1/2
+ ···
Bn = P (τ ) n
b0 +
n
e
En = P (τ )n n−3/2 e0 + 1 + · · ·
n
Proof: the saddle-point method for bridges, sine
1
du
Bn =
P (u)n
2iπ C
u
Z
As a by-produt, this ditates the singular behaviour of the series Ui(z), from
whih one derives the singular behaviour of E(z).
Asymptotis for general walks and meanders
Theorem. Let τ > 0 be the unique solution of P ′(τ ) = 0, where P is the
generating polynomial of steps.
•
The numbers of walks is
Wn = P (1)n
The asymptoti behaviour of the number of meanders (= non-negative walks)
depends on the drift
•
δ = P ′(1)
⋆
If δ > 0, a positive fration of walks are meanders:
m1
n
n
−3/2
m0 +
+ ···
Mn = κP (1) + P (τ ) n
n
⋆
If δ < 0,
m1
n −3/2
Mn = P (τ ) n
m0 +
+ ···
n
m
Mn = P (τ )n n−1/2 m0 + 1 + · · ·
n
⋆
If δ = 0,
Limit laws for basi parameters
•
The number of ontats of an exursion with the x-axis (disrete limit law)
•
The position Yn of the endpoint of a meander
⋆
If δ > 0,
Yn − µn
→ Gaussian
√
n
⋆
If δ < 0, disrete limit law
⋆
If δ = 0,
Yn
√ → Rayleigh
n
II. The enumeration of prudent polygons by area,
and its unusual asymptotis
(with N. Beaton and T. Guttmann, 2011)
Self-avoiding polygons
Self-avoiding polygons
•
Awfully hard to ount
•
Conjetured asymptotis: for polygons of area n,
pn ∼ κµnn0,
where the exponent depends only on the dimension
An easier family: 3-sided prudent polygons
Prudent walks: a step never points towards a vertex it has already visited
Prudent walk
Prudent polygon
[Turban-Debierre 86℄, [Préa 97℄, [Santra-Seitz-Klein 01℄, [Duhi 05℄, [Dethridge, Guttmann, Jensen 07℄, [mbm 08℄, [Beara, Friedli, Velenik 10℄...
An easier family: 3-sided prudent polygons
Prudent walks: a step never points towards a vertex it has already visited
Prudent polygon
An easier family: 3-sided prudent polygons
Prudent walks: a step never points towards a vertex it has already visited
Prudent polygon
Three-sided prudent polygon
An easier family: 3-sided prudent polygons
Three-sided prudent polygons deompose into bars, bargraphs, and separating
ells [...℄ and their area generating funtion is
2q(3 − 10q + 9q 2 − q 3)
+
P (q) =
2
(1 − 2q) (1 − q)
m−1
Y 1 − q − q k + q k+1 − q k+2
2q 3(1 − q)2 X
(−1)m+1q 2m
(1 − 2q)2 m≥1 (1 − 2q)m(1 − q − q m+1) k=1
1 − q − q k+1
Asymptotis
•
The series:
2q(3 − 10q + 9q 2 − q 3)
+
P (q) =
2
(1 − 2q) (1 − q)
m−1
Y 1 − q − q k + q k+1 − q k+2
2q 3(1 − q)2 X
(−1)m+1q 2m
(1 − 2q)2 m≥1 (1 − 2q)m(1 − q − q m+1) k=1
1 − q − q k+1
A beautiful singularity analysis yields a very unusual asymptoti behaviour in
the study of lattie models:
•
Pn = (κ0 + κ(log2 n))2n nγ + O(log n 2nnγ−1)
where the exponent γ is irrational
γ = log2 3
and κ(x) is a (small) periodi funtion of x.
Remark. Similar to (but more omplex than) the analysis of the expeted
longest run in a random binary sequene, where the key series is
qk
(1 − q)
.
k+1
1 − 2q + q
k≥0
X