Walks confined in a quadrant are not always D-finite
From MaRDI portal
(Redirected from Publication:1885016)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3712896 (Why is no real title available?)
- scientific article; zbMATH DE number 572073 (Why is no real title available?)
- scientific article; zbMATH DE number 3803442 (Why is no real title available?)
- scientific article; zbMATH DE number 3270295 (Why is no real title available?)
- scientific article; zbMATH DE number 3194856 (Why is no real title available?)
- scientific article; zbMATH DE number 3059214 (Why is no real title available?)
- A Gap Theorem for Power Series Solutions of Algebraic Differential Equations
- A bijection for some paths on the slit plane
- A class of hypertranscendental functions
- A probabilistic method for lattice path enumeration
- A problem of arrangements
- Analytic models and ambiguity of context-free languages
- Basic analytic combinatorics of directed lattice paths
- Counting Walks in the Quarter Plane
- D-finite power series
- Differentiably finite power series
- Generalized Dyck paths
- Generating functions for generating trees
- Hypertranscendency of meromorphic solutions of a linear functional equation
- Intersections of random walks.
- Lattice paths between diagonal boundaries
- Linear recurrences with constant coefficients: The multivariate case
- Mahler functions and transcendence
- On the enumeration and generation of generalized Dyck words
- Random Walk in a Weyl Chamber
- Random walk in an alcove of an affine Weyl group, and non-colliding random walks on an interval
- The ballot problem with three candidates
- The diagonal of a D-finite power series is D-finite
- Underdiagonal lattice paths with unrestricted steps
- Walks in the quarter plane: Kreweras' algebraic model
- Walks on the slit plane
- Walks on the slit plane: Other approaches
Cited in
(39)- Counting Walks in the Quarter Plane
- Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
- Non-D-finite walks in a three-quadrant cone
- Harmonic functions for singular quadrant walks
- The complete generating function for Gessel walks is algebraic
- Combinatorics meets potential theory
- scientific article; zbMATH DE number 7651047 (Why is no real title available?)
- The quasi-holonomic ansatz and restricted lattice walks
- 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
- Explicit expression for the generating function counting Gessel's walks
- The research and progress of the enumeration of lattice paths
- In-depth comparison of the Berlekamp-Massey-Sakata and the Scalar-FGLM algorithms: the adaptive variants
- Counting ternary trees according to the number of middle edges and factorizing into (3/2)-ary trees
- 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
- 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
- Asymptotics of lattice walks via analytic combinatorics in several variables
- 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
- On the tiling system recognizability of various classes of convex polyominoes
- Computer algebra in the service of enumerative combinatorics
- 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)
