Walks confined in a quadrant are not always D-finite
From MaRDI portal
Publication:1885016
DOI10.1016/S0304-3975(03)00219-6zbMATH Open1070.68112arXivmath/0211432OpenAlexW2081302100MaRDI QIDQ1885016FDOQ1885016
Authors: Mireille Bousquet-Mélou, Marko Petkovšek 
Publication date: 27 October 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: We consider planar lattice walks that start from a prescribed position, take their steps in a given finite subset of Z^2, and always stay in the quadrant x >= 0, y >= 0. We first give a criterion which guarantees that the length generating function of these walks is D-finite, that is, satisfies a linear differential equation with polynomial coefficients. This criterion applies, among others, to the ordinary square lattice walks. Then, we prove that walks that start from (1,1), take their steps in {(2,-1), (-1,2)} and stay in the first quadrant have a non-D-finite generating function. Our proof relies on a functional equation satisfied by this generating function, and on elementary complex analysis.
Full work available at URL: https://arxiv.org/abs/math/0211432
Recommendations
Cites Work
- A problem of arrangements
- Differentiably finite power series
- Intersections of random walks.
- Mahler functions and transcendence
- Title not available (Why is that?)
- Title not available (Why is that?)
- Generating functions for generating trees
- Linear recurrences with constant coefficients: The multivariate case
- On the enumeration and generation of generalized Dyck words
- Basic analytic combinatorics of directed lattice paths
- Counting Walks in the Quarter Plane
- Walks in the quarter plane: Kreweras' algebraic model
- D-finite power series
- Random Walk in a Weyl Chamber
- Title not available (Why is that?)
- A probabilistic method for lattice path enumeration
- The diagonal of a D-finite power series is D-finite
- Lattice paths between diagonal boundaries
- Analytic models and ambiguity of context-free languages
- Random walk in an alcove of an affine Weyl group, and non-colliding random walks on an interval
- Title not available (Why is that?)
- Generalized Dyck paths
- Walks on the slit plane
- Walks on the slit plane: Other approaches
- The ballot problem with three candidates
- Underdiagonal lattice paths with unrestricted steps
- Hypertranscendency of meromorphic solutions of a linear functional equation
- A Gap Theorem for Power Series Solutions of Algebraic Differential Equations
- Title not available (Why is that?)
- A class of hypertranscendental functions
- Title not available (Why is that?)
- A bijection for some paths on the slit plane
Cited In (39)
- Counting Walks in the Quarter Plane
- Harmonic functions for singular quadrant walks
- Non-D-finite walks in a three-quadrant cone
- Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
- The complete generating function for Gessel walks is algebraic
- Title not available (Why is that?)
- The quasi-holonomic ansatz and restricted lattice walks
- Combinatorics meets potential theory
- Non-D-finite excursions in the quarter plane
- Counting elements and geodesics in Thompson's group \(F\).
- On 3-dimensional lattice walks confined to the positive octant
- On some problems about ternary paths: a linear algebra approach
- Walks in the quarter plane: Kreweras' algebraic model
- Counting ternary trees according to the number of middle edges and factorizing into (3/2)-ary trees
- The research and progress of the enumeration of lattice paths
- Explicit expression for the generating function counting Gessel's walks
- In-depth comparison of the Berlekamp-Massey-Sakata and the Scalar-FGLM algorithms: the adaptive variants
- Two non-holonomic lattice walks in the quarter plane
- Classifying lattice walks restricted to the quarter plane
- An elementary solution of Gessel's walks in the quadrant
- Square lattice walks avoiding a quadrant
- Encoding algebraic power series
- Partially directed paths in a wedge
- Singularity analysis via the iterated kernel method
- Asymptotics of lattice walks via analytic combinatorics in several variables
- On the functions counting walks with small steps in the quarter plane
- New steps in walks with small steps in the quarter plane: series expressions for the generating functions
- Guessing Gröbner bases of structured ideals of relations of sequences
- Walks obeying two-step rules on the square lattice: full, half and quarter planes
- Higher dimensional lattice walks: connecting combinatorial and analytic behavior
- Quadrant walks starting outside the quadrant
- Computer algebra in the service of enumerative combinatorics
- On the tiling system recognizability of various classes of convex polyominoes
- Families of prudent self-avoiding walks
- Counting walks in a quadrant: a unified approach via boundary value problems
- Weighted lattice walks and universality classes
- A human proof of Gessel's lattice path conjecture
- Counting walks with large steps in an orthant
- Words in linear groups, random walks, automata and P-recursiveness
This page was built for publication: Walks confined in a quadrant are not always D-finite
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1885016)
