1
$\begingroup$

Consider an arbitrarily large $N \times N$ grid graph. How can I express the number of closed walks starting from a reference vertex $v$ in terms of the length $L$ of the walk?

For example, for $L = 2$, there are 4 closed walks from $v$ to $v$. For $L = 4$, there are $36$ closed walks from $v$ to $v$.

2 Answers 2

2

If I understood the question well, it is ok to assume that the distance between $v$ and the border of the grid is smaller than $L$. Call $n_{u}$ the number of ups, $n_{d}$ the number of downs, $n_{l}$ the number of lefts and $n_{r}$ the number of rights. The number of closed walks is equal to the number of ways you can choose $L$ times between up, down,left,right in such a way that $n_{u}=n_{d}$ and $n_{l}=n_{r}$.

If you fix a value for $n_{u}$, there are $\frac{L!}{n_{u}!n_{u}!(\frac{L-2n_{u}}{2})!(\frac{L-2n_{u}}{2})!}$. Summing up for all possible values of $n_{u}$ from $0$ to $L/2$ you get that the number of paths is:

$\sum_{i=0}^{L/2}{\frac{L!}{i!i!(\frac{L-2i}{2})!(\frac{L-2i}{2})!}}$

  • 1
    Note that this simplifies to ${{L}\choose{\frac{L}{2}}}^2$ according to OEIS: http://oeis.org/search?q=4%2C36%2C400%2C4900&language=english&go=Search2012-06-27
1

Define your reference $\vec v= (0,0,\dots ,1,0,0,\dots ,0)^T\in \Bbb{N}^{N^2}$. Take the adjacency matrix of your $N\times N$ grid $A_{N\times N}$, calculate the $L$-th power of $A_{N\times N}$ and evaluate the scalar product with $\vec v$:

$ n_{\vec v}(L)=\vec v^T\cdot \left(A_{N\times N}^L \vec v\right), $ which expresses the number of closed walks starting from a reference vertex $v$ in terms of the length $L$ of the walk as recommended.