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

Bousquet-Mélou, Mireille 

Canadian journal of mathematics, Tome 75 (2023) no. 5, pp. 1566-1632

Résumé

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 these results 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 nonconvex cones, typically the three-quadrant cone $\mathcal {C} = \{ (i,j) : i \geq 0 \text { or } j \geq 0 \}$. They turn out to be more difficult than their quadrant counterparts. In this paper, we investigate a collection of eight models in $\mathcal {C}$, which can be seen as the first level of difficulty beyond quadrant problems. 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 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 $\{ \nearrow , \nwarrow , \swarrow , \searrow \}$, which is D-finite. The three algebraic models are those of the Kreweras trilogy, $\mathcal S=\{\nearrow , \leftarrow , \downarrow \}$, $\mathcal S^*=\{\rightarrow , \uparrow , \swarrow \}$, and $\mathcal S\cup \mathcal S^*$.Our solutions take similar forms for all six models. Roughly speaking, the square of the generating function of three-quadrant walks with steps in $\mathcal S$ is an explicit rational function in the quadrant generating function with steps in $\mathscr S:= \{(j-i,j): (i,j) \in \mathcal S\}$. We derive various exact or asymptotic corollaries, including an explicit algebraic description of a positive harmonic function in $\mathcal C$ for the (reverses of the) five models that are at least D-finite.

Détail

DOI : 10.4153/S0008414X22000487

Mots-clés : Lattice walks, exact enumeration, algebraic and D-finite series, discrete harmonic functions