5
$\begingroup$

One of the approaches to "Special" meanders led (in particular) to the following question:

What is the number $a_{m,n}(\ell)$ of $\ell$-step paths from $(1,1)$ to $(m,n)$ using the following four kinds of steps: $(i,j)\mapsto$ $(i+1,j)$, $(i+1,j-1)$, $(i,j+1)$ or $(i-1,j+1)$ and with the restriction that $i$ and $j$ stay positive at each step?

The only thing I managed to find out is sort of a trivial reformulation of the definition: the polynomials $$ P_\ell(x,y):=\sum_{m,n\geqslant1}a_{m,n}(\ell)x^my^n $$ satisfy a recurrence: since $P_\ell(x,0)=P_\ell(0,y)=0$, each $F_\ell(x,y):=(x+y+x/y+y/x)P_\ell(x,y)$ is a polynomial, and we have $$ P_{\ell+1}(x,y)=F_\ell(x,y)-F_\ell(x,0)-F_\ell(0,y). $$

In a way of example - here is the table of the $a_{m,n}(7)$: $$ \begin{array}{cccccccc} 0 & 1 & 21 & 80 & 125 & 85 & 21 & 1 \\ 1 & 28 & 139 & 254 & 210 & 76 & 7 & 0 \\ 21 & 139 & 306 & 308 & 140 & 21 & 0 & 0 \\ 80 & 254 & 308 & 168 & 35 & 0 & 0 & 0 \\ 125 & 210 & 140 & 35 & 0 & 0 & 0 & 0 \\ 85 & 76 & 21 & 0 & 0 & 0 & 0 & 0 \\ 21 & 7 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} $$

As literature on the subject of lattice paths is way too vast for me to handle, this is mostly a reference request: I believe that working hardly enough I could find at least a generating function, but I also believe it must be done somewhere already.

In fact a more (or less?) specific question in this direction is whether there is some kind of searchable database of combinatorial objects where I could find such things. There is a question Combinatorial Databases here on MO but I could not find anything about path enumeration in the answers. The closest I could get is the Dyck path enumeration on FindStat

$\endgroup$
8
$\begingroup$

It seems the first solution to this problem appeared in Theorem 4 of

Raschel, Kilian, Counting walks in a quadrant: a unified approach via boundary value problems, J. Eur. Math. Soc. (JEMS) 14, No. 3, 749-777 (2012). ZBL1238.05014.

Notice that the walk corresponds to the fourth singular walk of Figure 2. The kernel $K(x,y;z)$ of the walk is given by $$K(x,y;z) = x y z(x +x/y +y +y/x -1/z).$$ Let $X_0(y) = X_0(y;z)$ (resp. $Y_0(x)=Y_0(x;z)$) be one of the solutions $x$ (resp. $y$) to $K(x,y;z) = 0$. Then Theorem 4 states that $$Q(x,y;z) = \sum_{m,n\geq 1} x^{m-1}y^{n-1} \sum_{\ell\geq 0} z^l a_{m,n}(\ell) $$ satisfies $$ Q(x,y;z) = \frac{1}{K(x,y;z)}\left(z x^2Q(x,0;z)+z y^2 Q(0,y;z)-xy\right)$$ with $$ Q(x,0;z) = \frac{1}{zx^2} \sum_{p\geq 0} Y_0 \circ (X_0\circ Y_0)^{\circ p}(x;z)\,\left[ (X_0\circ Y_0)^{\circ p}(x;z) - (X_0\circ Y_0)^{\circ (p+1)}(x;z) \right].$$ Here $f^{\circ p}$ means $f\circ \cdots \circ f$ with $p$ occurrences of $f$. Notice that by symmetry $Q(0,y;z) = Q(y,0;z)$.

A quick check with Mathematica reproduces the table for $\ell=7$:

k = x y z (x + x/y + y + y/x - 1/z);
x0[y_] = x /. Solve[k == 0, x][[1]] // FullSimplify[#, y > 0 && x > 0] &;
y0[x_] = y /. Solve[k == 0, y][[1]] // FullSimplify[#, y > 0 && x > 0] &;
Series[SeriesCoefficient[1/k (Sum[y0[xp] (xp - x0[y0[xp]]) /. 
   xp -> Nest[x0[y0[#]] &, x, p], {p, 0, 2}] 
   // -x y + # + (# /. x -> y) &), {z, 0, 7}], {x, 0, 7}, {y, 0, 7}]

yields the output

$$\left(y+21 y^2+80 y^3+125 y^4+85 y^5+21 y^6+y^7+O\left(y^8\right)\right)+x \left(1+28 y+139 y^2+254 y^3+210 y^4+76 y^5+7 y^6+O\left(y^8\right)\right)+x^2 \left(21+139 y+306 y^2+308 y^3+140 y^4+21 y^5+O\left(y^8\right)\right)+x^3 \left(80+254 y+308 y^2+168 y^3+35 y^4+O\left(y^8\right)\right)+x^4 \left(125+210 y+140 y^2+35 y^3+O\left(y^8\right)\right)+x^5 \left(85+76 y+21 y^2+O\left(y^8\right)\right)+x^6 \left(21+7 y+O\left(y^8\right)\right)+x^7+O\left(x^8\right)$$

$\endgroup$
1
$\begingroup$

Bousquet-Melou's work might be pertinent. See https://arxiv.org/abs/1708.06192 Figure 4 there seems to be your lattice walk.

$\endgroup$
  • $\begingroup$ I meant for the answer above to be a comment. Sorry. $\endgroup$ – user61318 Jan 9 at 13:48

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.