Basic analytic combinatorics of directed lattice paths

DOI10.1016/S0304-3975(02)00007-5zbMath0996.68126MaRDI QIDQ1603684

Cyril Banderier, Philippe Flajolet

Publication date: 15 July 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

kernel methodlattice pathCatalan numberssingularity analysisanalytic combinatoricsgeneralized ballot problem

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Related Items (90)

Combinatorics meets potential theory ⋮ Walks confined in a quadrant are not always D-finite ⋮ Counting quadrant walks via Tutte's invariant method ⋮ Two non-holonomic lattice walks in the quarter plane ⋮ Arithmetics properties of substitutions and infinite automata ⋮ Algebraic diagonals and walks: algorithms, bounds, complexity ⋮ Skew Dyck Paths With Catastrophes ⋮ Complexity of anticipated rejection algorithms and the Darling-Mandelbrot distribution ⋮ On moment sequences and mixed Poisson distributions ⋮ Multicritical scaling in a lattice model of vesicles ⋮ An elementary solution of Gessel's walks in the quadrant ⋮ From steady-state TASEP model with open boundaries to 1D Ising model at negative fugacity ⋮ Between Broadway and the Hudson: A Bijection of Corridor Paths ⋮ Singularity Analysis Via the Iterated Kernel Method ⋮ Colored Motzkin Paths of Higher Order ⋮ Ascents in Non-Negative Lattice Paths ⋮ Counting lattice paths taking steps in infinitely many directions under special access restrictions ⋮ Weighted lattice walks and universality classes ⋮ A combinatorial understanding of lattice path asymptotics ⋮ The vectorial kernel method for walks with longer steps ⋮ A half-normal distribution scheme for generating functions ⋮ Continous analogues for the binomial coefficients and the Catalan numbers ⋮ The asymptotics of reflectable weighted walks in arbitrary dimension ⋮ Non-D-finite excursions in the quarter plane ⋮ Spitzer's identity for discrete random walks ⋮ Down-step statistics in generalized Dyck paths ⋮ Fast Algorithms for Discrete Differential Equations ⋮ Taming reluctant random walks in the positive quadrant ⋮ Lattice paths with catastrophes ⋮ In-depth comparison of the Berlekamp-Massey-Sakata and the Scalar-FGLM algorithms: the adaptive variants ⋮ S-Motzkin paths with catastrophes and air pockets ⋮ Unnamed Item ⋮ Lattice Paths and Branched Continued Fractions: An Infinite Sequence of Generalizations of the Stieltjes–Rogers and Thron–Rogers Polynomials, with Coefficientwise Hankel-Total Positivity ⋮ Universal asymptotic properties of positive functional equations with one catalytic variable ⋮ Symmetries of statistics on lattice paths between two boundaries ⋮ On directed lattice paths with vertical steps ⋮ On card guessing games: limit law for no feedback one-time riffle shuffle ⋮ Partially directed snake polyominoes ⋮ The continuous weak order ⋮ Counting lattice paths by using difference equations with non-constant coefficients ⋮ Point sets with many non-crossing perfect matchings ⋮ The research and progress of the enumeration of lattice paths ⋮ Generating functions for lattice paths with several forbidden patterns ⋮ The site-perimeter of bargraphs ⋮ Diagonal Asymptotics for Products of Combinatorial Classes ⋮ Formulae and Asymptotics for Coefficients of Algebraic Functions ⋮ Unnamed Item ⋮ The representation of the symmetric group on \(m\)-Tamari intervals ⋮ Stieltjes moment sequences for pattern-avoiding permutations ⋮ Linear functional equations with a catalytic variable and area limit laws for lattice paths and polygons ⋮ Unnamed Item ⋮ ALGEBRAIC AND GEOMETRIC PROPERTIES OF LATTICE WALKS WITH STEPS OF EQUAL LENGTH ⋮ Fast computation of special resultants ⋮ Stochastic processes under constraints. Abstracts from the workshop held September 27 -- October 3, 2020 (hybrid meeting) ⋮ Asymptotic Enumeration of Constellations and Related Families of Maps on Orientable Surfaces ⋮ On the nature of four models of symmetric walks avoiding a quadrant ⋮ On differentially algebraic generating series for walks in the quarter plane ⋮ Bounded affine permutations I. Pattern avoidance and enumeration ⋮ On 3-dimensional lattice walks confined to the positive octant ⋮ Analysis of bidirectional ballot sequences and random walks ending in their maximum ⋮ On the Lagrange inversion formula ⋮ On the area under lattice paths associated with triangular diminishing urn models ⋮ Enumeration and asymptotics of restricted compositions having the same number of parts ⋮ Bijections for a class of labeled plane trees ⋮ Seven (lattice) paths to log-convexity ⋮ Unnamed Item ⋮ Lattice path counting and the theory of queues ⋮ A history and a survey of lattice path enumeration ⋮ On the number of walks in a triangular domain ⋮ Walks in the quarter plane: Kreweras' algebraic model ⋮ Continued Classification of 3D Lattice Walks in the Positive Octant ⋮ Asymptotics of lattice walks via analytic combinatorics in several variables ⋮ Polynomial equations with one catalytic variable, algebraic series and map enumeration ⋮ Counting colored planar maps: algebraicity results ⋮ On \(q\)-functional equations and excursion moments ⋮ First passage problems for upwards skip-free random walks via the scale functions paradigm ⋮ Counting walks with large steps in an orthant ⋮ Classifying lattice walks restricted to the quarter plane ⋮ Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata ⋮ The generating function of planar Eulerian orientations ⋮ 3D positive lattice walks and spherical triangles ⋮ Inhomogeneous restricted lattice walks ⋮ Parity properties and terminal points for lattice walks with steps of equal length ⋮ Exactly Solved Models ⋮ Walks obeying two-step rules on the square lattice: full, half and quarter planes ⋮ Exchange relations, Dyck paths and copolymer adsorption ⋮ Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behavior ⋮ Why Delannoy numbers? ⋮ Lattices of lattice paths ⋮ Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models

Uses Software

• gfun
• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dyck paths of knight moves
• Reconstructing convex polyominoes from horizontal and vertical projections
• Generalized Dyck paths
• Analytic models and ambiguity of context-free languages
• Combinatorial aspects of continued fractions
• Underdiagonal lattice paths with unrestricted steps
• Asymptotic properties of some underdiagonal walks generation algorithms
• Brownian motion, bridge excursion, and meander characterized by sampling at independent uniform times
• Asymptotic distributions and a multivariate Darboux method in enumeration problems
• The random generation of directed animals
• Tiling figures of the plane with two bars
• Generating functions for generating trees
• Algebraic languages and polyominoes enumeration
• Networks and queues: Probabilistic methods
• Linear recurrences with constant coefficients: The multivariate case
• On the enumeration and generation of generalized Dyck words
• The number of convex polyominoes reconstructible from their orthogonal projections
• Calcul pratique des coefficients de Taylor d'une fonction algébrique
• Algebraic functions over finite fields
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Singularity Analysis of Generating Functions
• An analysis of (h, k, 1)-Shellsort
• Sequence of operations analysis for dynamic data structures
• An Analysis of a Memory Allocation Scheme for Implementing Stacks
• A Noncommutative Generalization and q-Analog of the Lagrange Inversion Formula
• On the Altitude of Nodes in Random Trees
• Two coupled processors: The reduction to a Riemann-Hilbert problem
• Images and Preimages in Random Mappings
• GFUN
• The formal theory of birth-and-death processes, lattice path combinatorics and continued fractions
• Functional Composition Patterns and Power Series Reversion
• On a functional-difference equation of Runyon, Morrison, Carlitz, and Riordan
• Reconstruction of lattice sets from their horizontal, vertical and diagonal \(X\)-rays

This page was built for publication: Basic analytic combinatorics of directed lattice paths