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$
9
$\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$
  • $\begingroup$ Indeed, I've corrected it. $\endgroup$ – Timothy Budd Jan 9 '19 at 20:32
2
$\begingroup$

This is an extension of the accepted answer. Using it, and ideas from some other papers, I managed to obtain an alternative expression for the generating function which I find interesting.

As explained in that answer, the problem reduces to finding $Q(x,0,z):=\sum_{i,\ell}a_{n,1}(\ell)x^nz^\ell$.

Let $z=\frac1{q+q^{-1}}$ and $x=-\frac{(1-q) (1-q^2) t}{(1-t) (1-q t)q}$. Then, $$ x^2zQ(x,0,z)=-x+\frac{1-4z^2}{z^2}\sum _{k=1}^\infty \frac{(-1)^kq^kt}{\left(1-q^kt\right)^2}. $$

The series $\sum _{k=1}^\infty \frac{(-1)^kq^kt}{\left(1-q^kt\right)^2}$ seems to be related to elliptic functions, Jacobi forms and such stuff, but I cannot figure out how exactly. Maybe I will ask a separate question about it.

Few words about the proof. The expression for the generating function in the other answer can be equivalently described as follows. Suppose $x$, $y$ satisfy $(x^2+y^2+x^2y+xy^2)z=xy$. Then, $$ (*)\qquad\qquad\qquad\qquad\qquad\qquad x^2zQ(x,0,z)=xy-y^2zQ(y,0,z).\qquad\qquad\qquad\qquad\qquad\qquad $$ Now the curve $(x^2+y^2+x^2y+xy^2)z=xy$ admits rational parametrizations $x(t)$, $y(t)$; moreover it is possible to choose such parametrization that satisfies $y(t)=x(qt)$, with $z=\frac1{q+q^{-1}}$ and $x(t)=-\frac{(1-q) (1-q^2) t}{(1-t) (1-q t)q}$. Then, denoting $F(t,q)=\frac{x(t)^2}{q+q^{-1}}Q\left(x(t),0,\frac1{q+q^{-1}}\right)$, we get from $(*)$ above the following functional equation for $F$: $$ F(t,q)=\frac{(1-q)^2 \left(1-q^2\right)^2 t^2}{(1-t) (1-q t)^2 \left(1-q^2 t\right)q}-F(qt,q). $$ This leads more or less straightforwardly to the claimed equality.

Update

Expression in terms of "original" variables can be also derived from this. Although less pretty, it is, I believe, still more explicit than the one in terms of iterated radicals.

We have $$ x^2zQ(x,0,z)=-x+\frac{1-4z^2}{z^2}\sum _{k=1}^\infty\frac{(-1)^k}{A(x,z)T_k\left(\frac{1}{2 z}\right)+B(x,z)U_{k-1}\left(\frac{1}{2 z}\right)-2}, $$ where $T$ and $U$ are the Chebyshev polynomials, while $A(x,z)$ and $B(x,z)$ are quadratic irrationalities determined by $$ \begin{aligned} A+\frac{2z}{1+2z}B&=2\left(1-\frac{1-2 z}{x z}\right),\\ A^2-\frac{4z^2}{1-4z^2}B^2&=4 \end{aligned} $$

$\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 '19 at 13:48
  • $\begingroup$ Only now I noticed, sorry - that case is different: it is (NE,SW,S,E) while this one is (NW,SE,N,E); since we are confined to the NE quadrant, the behaviour differs essentially - for example, in our situation we can never return to the origin while in that case one may revisit the origin arbitrarily often $\endgroup$ – მამუკა ჯიბლაძე Feb 9 '19 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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