4
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ Let $a(n)$ denote the number of walks from $0$ to $0$ in $n$ steps. Is there a simple reason why $a(2n+1)=5^n$? $\endgroup$ Jun 24, 2016 at 8:19
  • $\begingroup$ @JohannCigler: Let $f(x)$ be the g.f. for A098615. One can easily verify that $\frac{f(x)-f(-x)}{2}=\frac{x}{1-5x^2}=x+5x^3+5^2x^5+5^3x^7+\dots$. $\endgroup$ Jun 26, 2016 at 14:16
  • 1
    $\begingroup$ @MaxAlekseyev: Yes I know this. But I want to know if there is a simple direct argument in terms of walks. $\endgroup$ Jun 26, 2016 at 15:59

1 Answer 1

4
$\begingroup$

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}}$.

$\endgroup$
5
  • 2
    $\begingroup$ Paths of first type are generalized Catalan numbers: the number of them equals $0$ if $ab\leq 0$ and equals (number of all usual paths from $a$ to $b$)-(number of all usual paths from $a$ to $-b$) otherwise. $\endgroup$ Jun 24, 2016 at 15:46
  • $\begingroup$ @FedorPetrov: Indeed, this is a nice argument that simplifies computation. $\endgroup$ Jun 24, 2016 at 15:57
  • $\begingroup$ This is a very nice argument. But I do not see how one gets $\sum_{k=0}^{\lfloor(n+1)/2\rfloor}\left({n\choose k}-{n\choose k-1}\right)F(n-2k+1)$ from the generating function $1/(1-x-2x^2 C(x^2))$. $\endgroup$ Jun 25, 2016 at 13:14
  • 1
    $\begingroup$ @JohannCigler: First, the g.f. given in A098615. Second, directly this can be proved as follows. The sum equals the coefficient of $x^{n+1}$ in $(1-x^2)(1+x^2)^n\frac{x}{1-x-x^2}$. From here, one can get its g.f. using Lagrange inversion -- e.g., see mathoverflow.net/q/32188 $\endgroup$ Jun 26, 2016 at 14:08
  • $\begingroup$ @MaxAlekseyev: Thank you. This is a nice proof. $\endgroup$ Jun 27, 2016 at 13:25

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.