Given this question, what about the special case when the start point and end point are the same? I ask it here instead because I am looking for the mathematical solution to counting these different paths.
Another change in my case is that we must move at every step. How many such different paths can be found and what would be the most efficient approach? I guess this would be a random walk of some sort?
My thinking so far is, since we must always return to our starting point, thinking about $n/2$ might be easier. Then at every step, except at step $n/2$, we have 6 choices to move. At $n/2$ we have a different amount of choices depending on if $n$ is even or odd. We also have a different amount of choices depending on where we are (what previous choices we made). For example if $n$ is even and we went straight out, we only have one choice at $n/2$, going back. But if $n$ is even and we didn't go straight out, we have more choices.
It is all the cases at this turning point that I have trouble getting straight.
Am I on the right track?
To be clear, I just want to count the paths. So I guess we are looking for some conditioned permutation?
Each step is in one of the six directions 0º, 60º, 120º, 180º, 240º, 300º. Let $n_i$ be the number of steps in the direction $60i$ degrees. You can show that a path will return to its start if and only if $$ n_0-n_3 =n_2-n_5=n_4-n_1\tag1 $$ Of the $6^n$ possible walks, you must count the number of walks which satisfy the above condition. The following sum which computes this: $$ \sum_{k=-\lfloor{n/3}\rfloor}^{\lfloor{n/3}\rfloor}\sum_{a+b+c=n}\binom{n}{a,b,c}\binom{a}{\frac{k+a}{2}}\binom{b}{\frac{k+b}{2}}\binom{c}{\frac{k+c}{2}} $$ The above is correct as long as you use the convention that $\binom{m}{i}$ is zero whenever $i$ is not a nonnegative integer. Essentially, $a$ corresponds to $n_0+n_3$, $b$ to $n_2+n_5$ and $c$ to $n_0+n_3$, while $k$ is the common value of $(1)$.
Edit: Another way to express the above summation is $$ \sum_{k=-\lfloor{n/3}\rfloor}^{\lfloor{n/3}\rfloor}\sum_{a=0}^n\sum_{b=0}^{n-a}\binom{n}{a,b,c}\binom{a}{\frac{k+a}{2}}\binom{b}{\frac{k+b}{2}}\binom{n-a-b}{\frac{k+n-a-b}{2}} $$