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](https://oeis.org/A098615) 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.



Number of walks on integer lattice with self-edge at zero
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}}$.


