Using "Guess and Check" to Enumerate Walks in the Three-Quarter Plane

By Manuel Kauers and Doron Zeilberger

.pdf   .ps   .tex  
Written: July 2021.
In a fascinating recent talk (at the CIRM conference on Lattice Paths, June 2021) Mireille Bousquet-Melou showed how to use the fancy kernel method in order to enumerate lattice walks in the three-quarter plane x ≥ 0 OR y ≥ 0. They turn out to be much harder than the corresponding problem in the quarter plane x ≥ 0 AND y ≥ 0. Here we show that the these can also be hanlded by the simple-minded , yet rigorous, "guess and check" method, that, being simple people, we personally prefer to the fancy kernel method.

Mathematica Packages

  • Coming Up

    Maple Package

  • ThreeQuarterPlane.txt

    Sample Input and Output for the Maple package ThreeQuarterPlane.txt

    • To get a comparative study, showing why walks in the three-quarter plane are harder to enumerate than those in the quarter-plane, using the Kreweras' steps {[-1,0],[0,-1],[1,1]} as case-study
      the input produces the output

    • To get see the recurrence for the number of Kreweras walks (i.e. using the steps {[-1,0],[0,-1],[1,1]}) in the QUARTER-PLANE with 3*(n+76)-2 steps, from the origin terminating at the point [53,141] (being a point fairly far from the origin, in order to being able to predict the ultimate order and degree of the operator OPE(i,j,n,S_n) annihilating the number of walks from [0,0] to [i,j]
      the input produces the output

      As you can see it gives a good indication to the operator found in 2007 .

    • Alas, trying to do the same for the THREE-QUARTER PLANE, nothing was found with DEGREE+ORDER ≤ 40. So we need a bigger computer (and/or more efficient implementation) to even found the recurrence for the number of walks from (0,0) to [53,141] with 3*(n-77)-2 steps (since 141+53 is 2 (mod 3) and it only starts being non-zero at time 3*77-2.) Indeed
      the input produced the output
    Doron Zeilberger's List of Papers

    Doron Zeilberger's Home Page