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