Posted 01/12/2017

----------------------
Previous    Next
----------------------

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.

----------------------

In this problem, we are interested in enumerating non-repeating closed walks on $\mathbb Z^2$.

A closed walk on $\mathbb Z^2$ of length $n$ is a walk using $E$ $(1,0)$, $W$ $(-1,0)$, $N$ $(0,1)$ and $S$ $(0,-1)$ as steps starting at $(0,0)$ and ending at $(0,0)$. Clearly, the length of a closed walk on $\mathbb Z^2$ has to be even. For example, $w=EEWNWS$ is a closed walk.

A non-repeating walk is a walk in which adjacent steps have to be different. For example, $w=EEWNWS$ is not a non-repeat walk while $u=EWSWEN$ is a non-repeating closed walk.


Suppose we let $a_{n}$ denote the number of non-repeating closed walks of length $2n$ on $\mathbb Z^2$.

Find $a_{n}$.


A more general question would be what is the number of non-repeating closed walks of length $n$ on $\mathbb Z^k$, for $k\geq 2$.