Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
Thanks for the clear and concise explanation. –  tatterdemalion Jun 26 '12 at 22:51
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.