Number of walks on integer lattice with self-edge at zero

Question

Consider the graph with vertices $V=\mathbb Z$ and edges $$E=\{(n,n+1):n\in\mathbb Z\}\cup\{(0,0)\},$$ that is, the usual integer lattice with a self-edge at zero.

For some fixed parameters $a,b,n\in\mathbb N$, I am interested in counting the number of walks from $a$ to $b$ in $n$ steps. This is very easy in the case where there is no self edge, but unless I'm missing something obvious, this case seems eminently more complicated.

---

Note: Given that the adjacency matrix of this graph is quite simple, I tried computing the $(0,0)$ entry of successive powers of the adjacency matrix in hopes of getting inspiration on how to compute this case. Apparently, the only match in OEIS is this sequence, which is given by $$\sum_{k=0}^{\lfloor(n+1)/2\rfloor}\left({n\choose k}-{n\choose k-1}\right)F(n-2k+1),$$ where $F(\ell)$ stands for the Fibonacci number of order $\ell$. I'm not too surprised to see ${n\choose k}$ in there, especially given the similarity of the problem with counting random walks on the integer lattice without self-edge, but I am completely baffled to see the Fibonacci numbers.

---

Given the apparent simplicity of the problem, I would be surprised if this type of problem was never solved before, but I could not find any reference.

Answer 1

There are two types of paths from $a$ to $b$: those that do not visit the origin ($0$) and those that do visit it. I start with analyzing the second kind of paths.

Paths that visit the origin

A path that visits the origin consists of three parts: (i) a path from $a$ to $0$ that does not visit $0$ except at the end; (ii) looping at $0$ (either over the self-loop or longer loops of even length); (iii) a path from $0$ to $b$ that does not visit $0$ except at the beginning.

The number of parts (i) of length $\ell$ equals the coefficient of $x^{\ell}$ in $(x\cdot C(x^2))^{|a|}$, where $$C(x) = \frac{1-\sqrt{1-4x}}{2x}$$ is the generating function for Catalan numbers. Explicitly this number can be computed as $\binom{\ell}{\frac{\ell-|a|}{2}}\frac{2|a|}{|a|+\ell}$, and it is nonzero only if $a$ and $\ell$ are of the same parity.

The number of parts (iii) is computed similarly.

To compute the number of parts (ii) of length $\ell$, we notice that the number of irreducible loops at the origin (i.e., loops that that do not visit the origin except at the beginning and end) of length $m$ equals $1$ for $m=1$ and twice Catalan number $2C_{m/2-1}$ for even $m>0$ (the factor 2 stands for looping over positive or negative numbers). In other words, their g.f. is $x+2x^2C(x^2)$. Then summing over the number $k$ of irreducible loops, we get the following g.f. for the number of parts (ii): $$\sum_{k=0}^{\infty} (x+2x^2C(x^2))^k = \frac{1}{1-x-2x^2C(x^2)}.$$ This is also the g.f. for sequence https://oeis.org/A098615

Combining all together, we get the number of paths from $a$ to $b$ that visit the origin of length $\ell$ equals the coefficient of $x^\ell$ in $$\frac{(x\cdot C(x^2))^{|a|+|b|}}{1-x-2x^2\cdot C(x^2)}.$$

Paths that do not visit the origin

Without loss of generality, assume that both $a$ and $b$ are positive. Let $s>0$ be the smallest integer that is visited by a path from $a$ to $b$. Then by similar arguments to those we used above (using $s$ as a new "origin"), we get that the number of such paths of length $\ell$ equals the coefficient of $x^\ell$ in $$\frac{(x\cdot C(x^2))^{a+b-2s}}{1-x^2\cdot C(x^2)}.$$ It remains to sum up this g.f. over $s$ from $1$ to $\min\{a,b\}$.

UPDATE. Fedor Petrov's argument suggests that the number of such paths of length $\ell$ is $\binom{\ell}{\frac{\ell-|a-b|}{2}}-\binom{\ell}{\frac{\ell-(a+b)}{2}}$.