Non-D-finite excursions in the quarter plane
From MaRDI portal
Publication:392804
DOI10.1016/J.JCTA.2013.09.005zbMATH Open1279.05003arXiv1205.3300OpenAlexW2066934281MaRDI QIDQ392804FDOQ392804
Authors: Alin Bostan, Kilian Raschel, Bruno Salvy 
Publication date: 15 January 2014
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Abstract: The number of excursions (finite paths starting and ending at the origin) having a given number of steps and obeying various geometric constraints is a classical topic of combinatorics and probability theory. We prove that the sequence of numbers of excursions in the quarter plane corresponding to a nonsingular step set with infinite group does not satisfy any nontrivial linear recurrence with polynomial coefficients. Accordingly, in those cases, the trivariate generating function of the numbers of walks with given length and prescribed ending point is not D-finite. Moreover, we display the asymptotics of .
Full work available at URL: https://arxiv.org/abs/1205.3300
Recommendations
Exact enumeration problems, generating functions (05A15) Sums of independent random variables; random walks (60G50)
Cites Work
- NIST handbook of mathematical functions
- Title not available (Why is that?)
- Analytic combinatorics
- Title not available (Why is that?)
- Random walk: A modern introduction
- Random Walks on Infinite Graphs and Groups
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random walks and diffusions on graphs and databases. An introduction.
- Classifying lattice walks restricted to the quarter plane
- Basic analytic combinatorics of directed lattice paths
- Walks confined in a quadrant are not always D-finite
- On the functions counting walks with small steps in the quarter plane
- Random walks in cones
- Rational values of the arccosine function
- Walks with small steps in the quarter plane
- On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane
- Automatic Classification of Restricted Lattice Walks
- Asymptotic Analysis of Random Walks
- Counting Walks in the Quarter Plane
- The complete generating function for Gessel walks is algebraic
- Walks in the quarter plane: Kreweras' algebraic model
- Explicit expression for the generating function counting Gessel's walks
- Two non-holonomic lattice walks in the quarter plane
- D-finite power series
- Approximate formulas for some functions of prime numbers
- Nilpotent connections and the monodromy theorem: Applications of a result of Turrittin
- Title not available (Why is that?)
- Random Walk in a Weyl Chamber
- Counting walks in a quadrant: a unified approach via boundary value problems
- Convergent solutions of ordinary linear homogeneous differential equations in the neighborhood of an irregular singular point
- Title not available (Why is that?)
- Title not available (Why is that?)
- Exit times from cones in \({\mathbb{R}}^ n\) of Brownian motion
- Proof of Ira Gessel's lattice path conjecture
- Title not available (Why is that?)
- \(G\)-functions and multisum versus holonomic sequences
- An Introduction to "G"-Functions. (AM-133)
- Analytic models and ambiguity of context-free languages
- Brownian motion in cones
- Gevrey series of arithmetic type. I: Purity and duality theorems
- A combinatorial understanding of lattice path asymptotics
- Random walks in the quarter-plane with zero drift: an explicit criterion for the finiteness of the associated group
- Some exact asymptotics in the counting of walks in the quarter plane
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the magnitude of the coefficients of the cyclotomic polynomial
- Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
Cited In (48)
- On walks avoiding a quadrant
- Walks avoiding a quadrant and the reflection principle
- Non-D-finite walks in a three-quadrant cone
- Stochastic processes under constraints. Abstracts from the workshop held September 27 -- October 3, 2020 (hybrid meeting)
- Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
- On the enumeration of plane bipolar posets and transversal structures
- On the critical exponents of generalized ballot sequences in three dimensions and large tandem walks
- Counting quadrant walks via Tutte's invariant method
- Combinatorics meets potential theory
- Asymptotic lattice path enumeration using diagonals
- Semi-Baxter and strong-Baxter permutations
- On 3-dimensional lattice walks confined to the positive octant
- Enumeration of corner polyhedra and 3-connected Schnyder labelings
- Enumeration of corner polyhedra and 3-connected Schnyder labelings
- Computation of Tight Enclosures for Laplacian Eigenvalues
- Two non-holonomic lattice walks in the quarter plane
- Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behavior
- An elementary solution of Gessel's walks in the quadrant
- Full asymptotic expansion for orbit-summable quadrant walks and discrete polyharmonic functions
- Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022
- Continued Classification of 3D Lattice Walks in the Positive Octant
- Lattice walks confined to an octant in dimension 3: (non-)rationality of the second critical exponent
- Square lattice walks avoiding a quadrant
- Infinite orders and non-\(D\)-finite property of 3-dimensional lattice walks
- A combinatorial understanding of lattice path asymptotics
- On the nature of the generating series of walks in the quarter plane
- Semi-Baxter and Strong-Baxter: Two Relatives of the Baxter Sequence
- 3D positive lattice walks and spherical triangles
- Permutations sortable by two stacks in parallel and quarter plane walks
- Asymptotics of lattice walks via analytic combinatorics in several variables
- Counting coloured planar maps: differential equations
- Walks with small steps in the 4D-orthant
- New steps in walks with small steps in the quarter plane: series expressions for the generating functions
- On the kernel curves associated with walks in the quarter plane
- Walks in the quarter plane: genus zero case
- Linear differential equations as a data structure
- The asymptotics of reflectable weighted walks in arbitrary dimension
- On differentially algebraic generating series for walks in the quarter plane
- Enumeration of three-quadrant walks via invariants: some diagonally symmetric models
- Quadrant walks starting outside the quadrant
- Lattice walks in the octant with infinite associated groups
- Discrete harmonic functions in the three-quarter plane
- Computer algebra in the service of enumerative combinatorics
- Singularity Analysis Via the Iterated Kernel Method
- Weighted lattice walks and universality classes
- Further bijections to pattern-avoiding valid hook configurations
- Counting walks with large steps in an orthant
- Words in linear groups, random walks, automata and P-recursiveness
Uses Software
This page was built for publication: Non-D-finite excursions in the quarter plane
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392804)
