Enumeration of three-quadrant walks via invariants: some diagonally symmetric models

DOI10.4153/S0008414X22000487zbMATH Open1526.05007arXiv2112.05776MaRDI QIDQ6080109FDOQ6080109

Authors: Mireille Bousquet-Mélou 

Publication date: 30 October 2023

Published in: Canadian Journal of Mathematics (Search for Journal in Brave)

Abstract: In the past 20 years, the enumeration of plane lattice walks confined to a convex cone -- normalized into the first quadrant -- has received a lot of attention, stimulated the development of several original approaches, and led to a rich collection of results. Most of them deal with the nature of the associated generating function: for which models is it algebraic, D-finite, D-algebraic? By model, what we mean is a finite collection of allowed steps. More recently, similar questions have been raised for non-convex cones, typically the three-quadrant cone $C=(i,j):igeq0extorjgeq0$. They turn out to be more difficult than their quadrant counterparts. In this paper, we investigate a collection of eight models in $C$. This collection consists of diagonally symmetric models in ${-1,0,1}^{2}setminus(-1,1),(1,-1)$. Three of them are known not to be D-algebraic. We show that the remaining five can be solved in a uniform fashion using Tutte's notion of emph{invariants}, which has already proved useful for some quadrant models. Three models are found to be algebraic, one is (only) D-finite, and the last one is (only) D-algebraic. We also solve in the same fashion the diagonal model $earrow,warrow,swarrow,searrow$, which is D-finite. The three algebraic models are those of the Kreweras trilogy, $S=earrow,leftarrow,downarrow$, $S^{\prime }=ightarrow,uparrow,swarrow$, and $Scup{S}^{\prime }$. Our solutions take similar forms for all six models. Roughly speaking, the square of the generating function of three-quadrant walks with steps in $S$ is an explicit rational function in the quadrant generating function with steps in $(j-i,j):(i,j)inS$. We derive various corollaries, including an explicit algebraic description of the positive harmonic function in $C$ for the five models that are at least D-finite.

Full work available at URL: https://arxiv.org/abs/2112.05776

Recommendations

• Counting quadrant walks via Tutte's invariant method (extended abstract)
• Counting quadrant walks via Tutte's invariant method
• Walks in the quarter plane: Kreweras' algebraic model
• On walks avoiding a quadrant
• On the nature of four models of symmetric walks avoiding a quadrant

zbMATH Keywords

exact enumerationdiscrete harmonic functionslattice walksalgebraic and D-finite series

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05)

Cites Work

• Analytic combinatorics
• Classifying lattice walks restricted to the quarter plane
• On the functions counting walks with small steps in the quarter plane
• Random walks in cones
• Discrete harmonic functions on an orthant in \(\mathbb{Z}^d\)
• Walks with small steps in the quarter plane
• Singularity analysis via the iterated kernel method
• Non-D-finite excursions in the quarter plane
• The complete generating function for Gessel walks is algebraic
• Random walks in the quarter plane, discrete harmonic functions and conformal mappings
• Two non-holonomic lattice walks in the quarter plane
• An elementary solution of Gessel's walks in the quadrant
• Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
• Chromatic sums revisited
• On the nature of the generating series of walks in the quarter plane
• On the nature of four models of symmetric walks avoiding a quadrant
• Walks in the quarter plane: genus zero case
• Title not available (Why is that?)
• Harmonic functions of random walks in a semigroup via ladder heights
• On differentially algebraic generating series for walks in the quarter plane
• Square lattice walks avoiding a quadrant
• Enumeration of walks with small steps avoiding a quadrant
• Martin boundary of random walks in convex cones
• Counting walks with large steps in an orthant
• Winding of simple walks on the square lattice
• On walks avoiding a quadrant
• Non-D-finite walks in a three-quadrant cone
• Counting quadrant walks via Tutte's invariant method (extended abstract)
• Discrete harmonic functions in the three-quarter plane
• Discrete harmonic functions in Lipschitz domains
• Counting quadrant walks via Tutte's invariant method
• Counting lattice walks by winding angle

Cited In (4)

• Walks avoiding a quadrant and the reflection principle
• Full asymptotic expansion for orbit-summable quadrant walks and discrete polyharmonic functions
• Title not available (Why is that?)
• On the nature of four models of symmetric walks avoiding a quadrant

This page was built for publication: Enumeration of three-quadrant walks via invariants: some diagonally symmetric models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6080109)