# A combinatorial problem of counting closed walks on grid

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

-

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})!}}$$

-
Thanks for the clear and concise explanation. –  tatterdemalion Jun 26 '12 at 22:51
Note that this simplifies to ${{L}\choose{\frac{L}{2}}}^2$ according to OEIS: oeis.org/… –  jp26 Jun 27 '12 at 13:52

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.

-