=Paper=
{{Paper
|id=Vol-2113/paper6
|storemode=property
|title=Local time for lattice paths and the associated limit laws
|pdfUrl=https://ceur-ws.org/Vol-2113/paper6.pdf
|volume=Vol-2113
|authors=Cyril Banderier,Michael Wallner
|dblpUrl=https://dblp.org/rec/conf/gascom/BanderierW18
}}
==Local time for lattice paths and the associated limit laws==
https://ceur-ws.org/Vol-2113/paper6.pdf
Local time for lattice paths
and the associated limit laws
Cyril Banderier Michael Wallner
LIPN (UMR CNRS 7030) LaBRI (UMR CNRS 5800)
Université de Paris Nord, France Université de Bordeaux, France
http://lipn.fr/~banderier/ http://dmg.tuwien.ac.at/mwallner/
Abstract
For generalized Dyck paths (i.e., directed lattice paths with any finite
set of jumps), we analyse their local time at zero (i.e., the number of
times the path is touching or crossing the abscissa). As we are in a
discrete setting, the event we analyse here is “invisible” to the tools of
Brownian motion theory.
It is interesting that the key tool for analysing directed lattice paths,
which is the kernel method, is not directly applicable here. Therefore,
we introduce a variant of this kernel method to get the trivariate gen-
erating function (length, final altitude, local time): this leads to an
expression involving symmetric and algebraic functions.
We apply this analysis to different types of constrained lattice paths
(meanders, excursions, bridges, . . . ). Then, we illustrate this ap-
proach on “basketball walks” which are walks defined by the jumps
−2, −1, 0, +1, +2. We use singularity analysis to prove that the limit
laws for the local time are (depending on the drift and the type of
walk) the geometric distribution, the negative binomial distribution,
the Rayleigh distribution, or the half-normal distribution (a universal
distribution up to now rarely encountered in analytic combinatorics).
1 Introduction
This article continues our series of investigations on the enumeration, generation, and asymptotics of directed
lattice paths [ABBG18a,ABBG18b,BF02,BW14,BW17,BG06,BKKKKNW17a,Wal16]. Such lattice paths are a
fundamental combinatorial structure ubiquitous in computer science (evolution of a stack, bijections with trees,
permutations, . . . ), probability theory (linked with random walks or queuing theory), and statistical mechanics
(as basic building blocks for more general 2D models), to name a few.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at
http://ceur-ws.org
69
ending anywhere ending at 0
unconstrained
(on Z)
walk/path (W) bridge (B)
constrained
(on N)
meander (M) excursion (E)
Table 1: Four types of paths: walks, bridges, meanders, and excursions.
Let us give a definition of the lattice paths we consider:
Definition 1.1 (Jumps and lattice paths). A step set S ⊂ Z2 is a finite set of vectors {(x1 , y1 ), . . . , (xm , ym )}.
An n-step lattice path or walk is a sequence of vectors (v1 , . . . , vn ), such that vj is in S. Geometrically, it may
be interpreted as a sequence of points ω = (ω0 , ω1 , . . . , ωn ) where ωi ∈ Z2 , ω0 = (0, 0) (or another starting point)
and ωi − ωi−1 = vi for i = 1, . . . , n. The elements of S are called steps or jumps. The length |ω| of a lattice
path is its number n of jumps.
We restrict our attention to directed paths which are defined by the fact that, for each jump (x, y) ∈ S, one
must have x ≥ 0. Lattice paths can have different additional constraints shown in Table 1.
Note that it is possible to encode lattice paths in words. Then, the constrained lattice paths we consider can
be enumerated by context-free grammars [LY90, MRSV99, Duc00]. One drawback of the grammar approach is
that it is not easy to get universal asymptotic results from it, even if it is possible to establish generic results
on the associated critical exponents [BD15]. Also, the grammar approach quickly leads to heavy case-by-case
computations (resultants of equations of huge degree) as soon as the set of jumps S contains a large jump.
In this article, we show how to proceed for the enumeration and the asymptotics in these harder cases: our
techniques are relying on the “kernel method” which (contrary to the context-free grammar approach) offers
access to the generic structure of the final generating functions and the universality of their asymptotics via
singularity analysis [BF02, FS09].
The following convenient notation, a variant of the Omega operator of MacMahon, will be another of our
ingredients:
X X
{u>0 } := un [un ] and {u<0 } := un [un ]
n>0 n<0
where [un ]g(u) stands for the coefficient of un in a (Laurent) power series g(u) from C((u)) or C[u, 1/u][[z]].
MacMahon introduced this operator on rational functions, in order to get binomial identities or integer parti-
tion formulae [Mac15, Section VIII]. In the late 1990s, this operator experienced a strong revival, mostly by
work/packages of Andrews, Paule, Riese, and Han [APR01, Han03]. Another nice application of the Omega
operator is the proof of D-finiteness of some walks in the quarter plane by Bousquet-Mélou and Mishna [BM10].
In this article we make use of this operator, not on sums or products of rational functions (like it is the case
for integer partitions, or for quarter plane walks), but on the level of functional equations involving algebraic
functions.
70
2 Generating function for the local time at 0
The number of times the lattice path is exactly at altitude 0 is an easy parameter to catch via combinatorial
decompositions (see analysis of the number of returns to zero for excursions, via a decomposition into arches, by
Banderier and Flajolet [BF02]). In order to get the local time at 0 (as defined in Figure 1), it remains to capture
a more subtle parameter: the number of steps which are crossing the x-axis (without actually starting or ending
at altitude 0). For any family of lattice paths, let P (u) = 1/uc + · · · + ud be the Laurent polynomial encoding
the jumps allowed at each step. For example, the “basketball walks” which we considered in [BKKKKNW17a]
are walks with jumps in the set {−2, −1, 0, +1, +2}, and we get P (u) := 1/u2 + 1/u + 1 + u + u2 . More generally,
each jump i may get a weight pi , which gives
d
X
P (u) = pi ui .
i=−c
Feller [Fel68, Fel71], Czáki and Vincze [CV61] and Jain [Jai66], considered P (u) = u/2 + (1/2)u, Wall-
ner [Wal16] considered P (u) = p−1 /u + p0 + p1 u, and we show here which new method is needed to tackle more
general P (u).
Figure 1: We consider the number of times a lattice path is touching or crossing the x-axis. The local time
at altitude h of a path ((x0 , y0 ), . . . , (xn , yn )) is #{0 < t < n such that (yt > h and yt+1 < h) or (yt < h and
yt+1 > h) or (yt = h)}. The same set without the last condition for h = 0 defines x-axis crossings. In the figure
above, the local time at zero is 7, the number of returns to zero is 5 (large red vertices), and the number of
x-axis crossings is 2 (red line segments). In this article, we show how to capture the local time at 0; it is then
straightforward to do it at any other altitude.
Figure 1 illustrates that
local time at zero = number of returns to zero + number of x-axis crossings.
As the generating function of the returns to zero, and the corresponding limit laws are known (see [BF02,Wal16]),
we can now focus on the number of x-axis crossings.
Theorem 2.1 (Generating function for number of x-axis crossings). Let wn,k,j be the number of walks of length
n which end at altitude k, and have j crossings of the x-axis. Then the generating function
X X
W (z, u, q) = wn,k,j z n uk q j = Wk (z, q)uk
n,j≥0,k∈Z k∈Z
is algebraic and expressible in terms of the roots ui (z) of 1 − zP (u) = 0.
Proof (Sketch). A step by step decomposition of the walk gives the following functional equation (where we write
Wk for Wk (z, q) for readability, and where q encodes the x-axis crossings):
−1 c−1
!
X X
>0 k <0 k
W (z, u, q) = 1 + zP (u)W (z, u, q) − z {u }(P (u)u )Wk + {u }(P (u)u )Wk
k=−d+1 k=1
−1 c−1
!
X X
>0 k <0 k
+ zq {u }(P (u)u )Wk + {u }(P (u)u )Wk .
k=−d+1 k=1
71
This equation can be read as “W = empty walk or the walk is at some altitude encoded by uk and multiply by
P (u) to do all the jumps, then we remove the ones crossing the x-axis, and re-add them with a marker q.” This
is conveniently rewritten as
−1
! c−1
!
X X X
k >0 k <0 k
(1 − zP (u)) Wk u = 1 − z(1 − q) {u }(P (u)u )Wk + {u }(P (u)u )Wk .
k∈Z k=−d+1 k=1
Here, one may think that we could apply the classical kernel method (see e.g. [BF02]): one substitutes u by
any root u(z) of 1 − zP (u), as this will cancel the left-hand side, and thus doing that for all roots will lead to a
system of c + d unknowns, with c + d independent relations. Hence, bingo, solving this system gives a closed-form
formula for W (z, u, q)!? Unfortunately, this is not working: indeed, in such an equation, if one substitutes a
variable by another expression, one has to take care to stay in the ringP of formal power series (in order to avoid
non-trivial zero divisors, as exemplified by the phenomenon (1 − u) k∈Z uk = 0). In our equation, F belongs
to C[u, 1/u][q][[z]]. As the exponents of u range from −∞ to +∞, it is not legitimate to substitute u by our
Puiseux series u(z), because this would lead to arbitrary negative and positive powers of z. We need to adapt
the kernel method and to transform it into what we call a “bilateral kernel method”:
1. Extract the positive part {u>0 }. This gives the following equation
∞ −1
!
X X
>0 k
{u } (1 − zP (u)) Wk u = −z(1 − q) {u>0 }(P (u)uk )Wk
k=−d+1 k=−d+1
which can be rewritten as
∞ −1 c
!
X X X
k >0 k >0 k
(1 − zP (u)) Wk u = −z(1 − q) {u }(P (u)u )Wk − {u } (1 − zP (u)) Wk u .
k=c+1 k=−d+1 k=−d+1
In this expression, it is legitimate to substitute u by the c roots ui (z) of 1 − zP (u) such that ui (z) ∼ 0 for
z ∼ 0. Thus we get c new equations:
−1 c
!
X X
>0 k >0 >0 k
0 = zq {u } P (u)u Wk + z{u } P (u) W0 − {u } (1 − zP (u))u Wk .
k=−d+1 k=1 |u=ui (z)
2. Extract the negative part {u<0 }. This leads to an equation in which it is legitimate to substitute u by the
d roots vi (z) of 1 − zP (u) such that |vi (z)| ∼ ∞ for z ∼ 0. Thus we get d new equations:
−1
c−1
!
X X
<0 k <0 <0 k
0 = zq {u } P (u)u Wk + z{u } P (u) W0 − {u } (1 − zP (u))u Wk .
k=1 k=−d |u=vi (z)
3. Extract [u0 ]. It gives one additional equation:
c
!!
X
0 k
[u ] (1 − zP (u)) Wk u = 1.
k=−d
All these equations involve (a subset of) of the yet unknown c + d + 1 auxiliary functions W−d , . . . , Wc . This
system fully allows to reconstruct the initial equation: W (the linear combination of the Wk ’s) is also a solution
of the initial functional equation, which was a contraction in the space of formal power series C[q, u, 1/u][[z]],
therefore this functional equation had a unique solution in this ring, which we thus identified as being W , the
only candidate for it. This explains why the system of equations is of full rank: it has unique power series
solutions Wk , all of them expressible as a quotient of polynomials having the roots as variable. (We say more
on this shape in the full version of this article: it requires an excursion (sic) via the Schur function world!) So,
in all cases, one gets a closed form for the generating function W (and the Wk ’s) in terms of the roots of the
kernel.
72
Now, the local analysis of these roots at their branching points, as done in [BF02] allows to get the Puiseux
behaviour of the functions W (z, u, 1) and W0 (z, u) near their dominant singularity (for any fixed value of u, this
dominant singularity is still the same ρ as in [BF02]). It allows to rewrite locally these functions (for z ∼ ρ) in
the framework of the schemes developed in [Wal16], on which we comment more in the next section.
Let us now illustrate this approach on basketball walks (walks with jumps −2, −1, 0, +1, +2,
see [BKKKKNW17a]). This leads to the simple linear system:
W0 = 1 + z(W−1 + W−2 + W0 + W1 + W2 )
qzW−1 + (zu1 + z) W0 + zu1 2 + zu1 + z − 1 W1 + zu1 3 + zu1 2 + zu1 + z − u1 W2 = 0
qzW−1 + (zu2 + z) W0 + zu2 2 + zu2 + z − 1 W1 + zu2 3 + zu2 2 + zu2 + z − u2 W2 = 0
qzW1 v1 3 + (v1 + 1) zW0 v1 2 + (z − 1)v1 2 + zv1 + z v1 W−1 + zv1 3 + (z − 1)v1 2 + zv1 + z W−2 = 0
qzW v 3 + (v + 1) zW v 2 + (z − 1)v 2 + zv + z v W + zv 3 + (z − 1)v 2 + zv + z W = 0
1 2 2 0 2 2 2 2 −1 2 2 2 −2
Solving it gives a closed form expression for W (z, u, q) lengthy to write. If one sets u = 1, the Ferrari–Bombelli
formula can be used and gives the following closed form for the generating functions of the walks:
2 √ √ √ √
z (z + 1) (q − 1) 4 q 2 z 2 − 3 qz 2 − 6 qz + 4 z 2 + q z − 1 q 2 − 1 4 z − 1 z C − DE A
W (z, 1, q) = √ + √ 3/4
−
2B 5 z − 1 2B (5 z − 1) 2B
p
where E := (5z − 1)(z − 1) and
A :=5 q 2 + 1 4q 2 − 3q + 4 z 4 + 2q 4 − 49q 3 + 24q 2 − 49q + 2 z 3 − 8q 4 + 11q 3 − 20q 2 + 11q + 8 z 2
+ 2q 4 + 13q 3 + 16q 2 + 13q + 2 z − 2q(q + 1)2 ,
B := 31q 4 + q 3 + 61q 2 + q + 31 z 5 − 8q 4 + 83q 3 + 18q 2 + 83q + 8 z 4 − 2 7q 4 + 3q 3 − 15q 2 + 3q + 7 z 3
+ 2 4q 4 + 17q 3 + 20q 2 + 17q + 4 z 2 − q 4 + 11q 3 + 19q 2 + 11q + 1 z + q 3 + 2q 2 + q,
C :=(z − 1)(5z − 1)(z + 1) 44q 4 − 26q 3 + 89q 2 − 26q + 44 z 5 + 4q 4 − 126q 3 + 44q 2 − 126q + 4 z 4
+ −20q 4 − 14q 3 + 58q 2 − 14q − 20 z 3 + 4q 4 + 46q 3 + 24q 2 + 46q + 4 z 2 + −8q 3 − 27q 2 − 8q z + 4q 2 ,
D :=5 34q 4 − 6q 3 + 69q 2 − 6q + 34 z 7 + 2 22q 4 − 243q 3 + 67q 2 − 243q + 22 z 6
− 132q 4 + 196q 3 − 81q 2 + 196q + 132 z 5 − 4 2q 4 − 81q 3 − 42q 2 − 81q + 2 z 4
+ 26q 4 + 58q 3 − 125q 2 + 58q + 26 z 3 − 2 2q 4 + 31q 3 + 29q 2 + 31q + 2 z 2 + q 8q 2 + 35q + 8 z − 4q 2 .
Note that the Cardan/Ferrari–Bombelli formulas are perhaps nice for the eyes (arguably!), but they are not
the right way to handle these generating functions from a computer algebra point of view. It is indeed better
to work directly with symmetric functions of the roots ui ’s (and this advantageously also allows to handle the
cases of degree > 4): this is an efficient algorithmic way to use the Newton relations/Vieta’s formulas between
the roots of the kernel. Using the expression with the small roots is also the way to follow the Puiseux behaviour
of these symmetric functions, as we detail in the forthcoming full version.
What is more, the above linear system shows that it is now routine to get in a few minutes thousands of
coefficients of our generating functions (e.g. via Newton iteration, in any computer algebra software). Here are
the first terms of the generating functions of x-axis crossings for walks:
W (z, 1, q) =1 + 5 z + (2 q + 23) z 2 + 2 q 2 + 14 q + 109 z 3 +
2 q 3 + 16 q 2 + 88 q + 519 z 4 + 2 q 4 + 18 q 3 + 112 q 2 + 504 q + 2489 z 5 +
2 q 5 + 20 q 4 + 138 q 3 + 700 q 2 + 2776 q + 11989 z 6 +
2 q 6 + 22 q 5 + 166 q 4 + 930 q 3 + 4150 q 2 + 14896 q + 57959 z 7 +
2 q 7 + 24 q 6 + 196 q 5 + 1196 q 4 + 5878 q 3 + 23720 q 2 + 78614 q + 280995 z 8 +
2 q 8 + 26 q 7 + 228 q 6 + 1500 q 5 + 8004 q 4 + 35518 q 3 + 132264 q 2 + 410046 q + 1365537 z 9 + O z 10 .
What is the asymptotic behaviour of these polynomials in q? This is what we present in the next section.
73
3 Limit laws
Theorem 3.1 (Limit law for the local time at 0). For a walk with step set encoded by P (u), the limit laws for
the local time at 0 depend on the drift P 0 (1) of the walk (see Table 2):
Type of the walk Limit law
Excursion Negative binomial distribution
Meander with drift < 0 Negative binomial distribution
Meander with drift ≥ 0 Geometric distribution
Walk with non-zero drift Geometric distribution
Walk with zero drift Half-normal distribution H(λ)
Bridge Rayleigh distribution R(λ)
The parametersp of these distributions are given in the proof and in Tablep 2: E.g. for bridges, the parameter
of R(λ) is λ = P 00 (1)/P (1), for walks, the parameter of H(λ) is λ = τ /2 P (1)/P 00 (1), where τ is the unique
real positive value such that P 0 (τ ) = 0.
What is more, if defined, the limit laws for the the number of x-axis crossings are the same as the ones of the
local time (with an appropriate new value for the distribution parameters).
Proof (Sketch). Thanks to the Puiseux expansions following from Theorem 2.1 and [BF02], it is possible to
derive the limit laws: we then get a shape on which we can apply the results of Drmota and Soria [DS97] on
the Rayleigh and Gaussian distributions, and of [Wal16] on the half-normal distribution. These distributions are
depicted in Table 2. Details are omitted in this extended abstract.
In the cases of excursions and meanders the local time is equal to the number of returns to zero. The results
for excursions were derived by Banderier and Flajolet in [BF02, Theorem 5]. What is more, all ingredients for
the case of meanders are also given in this paper, and the result follows the same lines. However, due to the
drift dependent number of meanders (compare [BF02, Theorem 4]) three regimes need to be considered, leading
to two different limit laws: negative binomial and geometric.
Geometric Negative binomial Half-normal Rayleigh
Geom(p) NB(m, p) H(λ) R(λ)
Support k ∈ {0, 1, . . .} k ∈ {0, 1, . . .} x ∈ R≥0 x ∈ R≥0
q
m+k−1 2 x2 x x2
PDF (1 − p)k p k (1 − p)k pm πλ2 exp − 2λ2 λ2 exp − 2λ2
q
1−p m(1−p)
λ π2
pπ
Mean p p λ 2
1−p m(1−p) 2
λ2 2 − π2
Variance p2 p2 λ2 1 − π
Table 2: A comparison of the geometric, negative binomial, half-normal, and Rayleigh distribution. They are
the four distributions occurring for the local time of generalized Dyck paths. Feller [Fel68, Chapter 3] did the
analysis for the simplest case of walks with jumps −1, +1, our article shows how to tackle the more difficult
situation involving any set of jumps of amplitude ≥ 1.
74
For the cases of walks and bridges the local time is equal to the number of returns to zero and the number
of x-axis crossings. The results for the number of returns to zero of walks were derived by Wallner in [Wal16,
Theorem 4.2] leading to a geometric or a half-normal distribution, depending whether the drift P 0 (1) is non-zero
or zero, respectively. As above, the result for the case of returns to zeros in bridges, follows also the same lines
as the previous one and we omit the details in this extended abstract. In this case one uses the limit law of
Drmota and Soria [DS97, Theorem 1] to prove the existence of a Rayleigh distribution.
It remains to consider the laws of x-axis crossings in the cases of bridges and walks. The proof of Theorem 2.1
gives access to closed forms of W0 (z, q) and W (z, 1, q), which are the generating functions of bridges and walks
where crossings of the x-axis are marked by q. In order to treat both at the same time we abbreviate them
until the end of this proof by F (z, q). We want to apply either [DS97, Theorem 1] or [Wal16, Theorem 2.1].
Note that the technical conditions of these theorems are satisfied due to the closed forms in terms of small and
large branches, and the fact, that due to the Weierstrass Preparation Theorem, the branches u1 (z) and v1 (z)
(which are the real positive branches for z > 0 in the vicinity of 0, see Figure 2) satisfy the necessary conditions
(compare the derivations in [Wal16]). In particular, as proven in [BF02], they satisfy a square root behaviour
with the following expansion at z = ρ:
s
P (τ ) p
u1 (z) = τ − 2 00 1 − z/ρ + . . . ,
P (τ )
s
P (τ ) p
v1 (z) = τ + 2 00 1 − z/ρ + . . . .
P (τ )
Due to the methods derived in [BW17], we may assume without loss of generality, that our model is aperiodic.
For such aperiodic models (like e.g. Motzkin and basketball walks) there exists a unique singularity ρ > 0 of
F (z, 1).
Now, the key fact is that our generating functions F have locally the following behaviour
1 p
= g(z, q) + h(z, q) 1 − z/ρ,
F (z, q)
for |q − 1| < ε and |z − ρ| < ε with arg(z − ρ) 6= 0 where ε > 0 is some fixed real number, and g(z, q) and
h(z, q) are analytic functions. Additionally, one has here that g(ρ, 1) = 0. Finally, in the case of bridges we
get gq (ρ, 1) < 0 and h(ρ, 1) 6= 0 yielding a Rayleigh law. Whereas, in the case of walks with zero drift we
get gq (ρ, 1) = gqq (ρ, 1) = 0 and h(ρ, 1) = 0, but gz (ρ, 1) 6= 0 and hq (ρ, 1) 6= 1 giving a half-normal law. The
respective parameters depend on the chosen step set.
Figure 2: The root u1 and v1 of the kernel 1 − zP (u) are crossing at z = ρ with a square root behaviour. This
implies the Puiseux expansions with a square root used in the proof above.
75
Figure 3: Distribution of Xn , the local time at 0 for bridges of length n. (Left: n = 200. Right: n = 4000. Step
set S = [−2, −1, 0, 1, 2]). One quickly observes a nearly perfect match of the distribution (in red) of Xn with
the Rayleigh limit law (in green). This fast convergence is well explained by the error terms we get via analytic
combinatorics.
Figure 4: Distribution of Xn , the local time at 0 for walks of length n. (Left: n = 200. Right: n = 4000. Step
set S = [−2, −1, 0, 1, 2]). One quickly observes a nearly perfect match of the distribution (in red) of Xn with the
half-normal limit law (in green). Here again, this fast convergence is well explained by the error terms we get
via analytic combinatorics.
76
4 Conclusion
In this article we showed how to derive the generating function for the local time at 0 of directed lattice paths. It
completes the work of Banderier and Flajolet [BF02], who just handled the case of returns to zero of excursions.
It is also extending the work of Feller [Fel68] and later Wallner [Wal16], who did the Dyck and Motzkin cases
(for meanders/walks).
In order to solve the generating functions in the more general case, we used a mixture of the Omega operator
and the kernel method. This leads to expressions from which we showed how to derive the limit law of the local
time, for several models of constrained lattice paths. In the full version of this article, we give more closed form
formulas, and we show that other parameters (like the number of “changes of signs”, or the number of jumps
from positive to negative altitude) can also be analysed using our approach, and that they satisfy similar limit
laws.
These parameters are very natural for discrete random walks, it is interesting that it is not possible to analyse
them via a Brownian √ motion approach: indeed a Brownian motion can be seen as the limit after a rescaling of
the amplitude by n and the length by n (see [Mar03]). This rescaling implies that (discrete) jumps crossing
the abscissa would be of amplitude 0, and are therefore completely erased. It is therefore nice that analytic
combinatorics can get the asymptotics of this “discrete local time”, and the corresponding universal limit laws,
while there are “invisible” via a Brownian motion approach. In a forthcoming article, we tackle further analysis
of the height of discrete lattice paths; this allows to get the connection with the Brownian local time.
Acknowledgements
This work was started via collaboration funded by the SFB project F50 “Algorithmic and Enumerative Combina-
torics” and the Franco-Austrian PHC “Amadeus”, and ended during the postdoctoral position of Michael Wallner
at the University of Paris Nord, in September-December 2017, thanks to a MathStic funding. Michael Wallner
is currently supported by the Erwin Schrödinger Fellowship of the Austrian Science Fund (FWF): J 4162-N35.
References
[APR01] G. E. Andrews, P. Paule and A. Riese. MacMahon’s partition analysis: the Omega package. Euro-
pean Journal of Combinatorics, 22(7):887–904, 2001.
[ABBG18a] A. Asinowski, A. Bacher, C. Banderier and B. Gittenberger. Analytic combinatorics of lattice paths
with forbidden patterns: asymptotic aspects. AofA proceedings (Analysis of Algorithms), 2018.
[ABBG18b] A. Asinowski, A. Bacher, C. Banderier and B. Gittenberger. Analytic combinatorics of lattice paths
with forbidden patterns: enumerative aspects. LATA proceedings (Language and Automata Theory
and Applications), 2018.
[BD15] C. Banderier and M. Drmota. Formulae and Asymptotics for Coefficients of Algebraic Functions.
Combinatorics Probability and Computing, 24:1–53, 2015.
[BF02] C. Banderier and P. Flajolet. Basic analytic combinatorics of directed lattice paths. Theoretical
Computer Science, 281(1-2):37–80, 2002.
[BG06] C. Banderier and B. Gittenberger. Analytic combinatorics of lattice paths: enumeration and asymp-
totics for the area. Discrete Mathematics and Theoretical Computer Science Proceedings, AG:345–
355, 2006.
[BKKKKNW17a] C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen and M.
Wallner. Explicit formulas for enumeration of lattice paths: basketball and the kernel method. In:
Lattice paths combinatorics and applications, Developments in Mathematics Series. Springer, 2017.
To appear.
[BW14] C. Banderier and M. Wallner. Some reflections on lattice paths. AofA 2014, Paris, 2014.
[BW17] C. Banderier and M. Wallner. The kernel method for lattice paths below a rational slope. In:
Lattice path combinatorics and applications, Developments in Mathematics Series. Springer, 2017.
To appear.
77
[BM10] M. Bousquet-Mélou and M. Mishna. Walks with small steps in the quarter plane. In: Algorith-
mic probability and combinatorics, volume 520 of Contemp. Math., pp. 1–39. Amer. Math. Soc.,
Providence, RI, 2010.
[CV61] E. Csáki and I. Vincze. On some problems connected with the Galton-test. Matematikai Kutato
Intezetenek Kozlemenyei. Magyar Tudomanyos Akademia, 6:97–109, 1961.
[DS97] M. Drmota and M. Soria. Images and preimages in random mappings. SIAM Journal on Discrete
Mathematics, 10(2):246–269, 1997.
[Duc00] P. Duchon. On the enumeration and generation of generalized Dyck words. Discrete Mathematics,
225(1-3):121–135, 2000.
[Fel68] W. Feller. An introduction to probability theory and its applications. Vol. I. Third edition. Wiley &
Sons, New York, 1968.
[Fel71] W. Feller. An introduction to probability theory and its applications. Vol. II. Second edition. John
Wiley & Sons, Inc., New York-London-Sydney, 1971.
[FS09] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.
[Han03] G.-N. Han. A general algorithm for the MacMahon omega operator. Annals of Combinatorics,
7(4):467–480, 2003.
[Jai66] G. C. Jain. Joint distribution of intersections, (±) waves and (±) steps. I. Proceedings of the
National Institute of Sciences of India. Part A, Physical sciences, 32:460–471, 1966.
[LY90] J. Labelle and Y.-N. Yeh. Generalized Dyck paths. Discrete Mathematics, 82(1):1–6, 1990.
[Mac15] P. A. MacMahon. Combinatory analysis. Volume 2. Cambridge: Univ. Press, 1915.
[Mar03] P. Marchal. Constructing a sequence of random walks strongly converging to Brownian motion.
Discrete Mathematics and Theoretical Computer Science Proceedings, AC:181–190, 2003.
[MRSV99] D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri. Underdiagonal lattice paths with unre-
stricted steps. Discrete Applied Mathematics, 91(1-3):197–213, 1999.
[Wal16] M. Wallner. A half-normal distribution scheme for generating functions. At
https://arxiv.org/abs/1610.00541, 2016.
78