I've invented a thought experiment for myself, which is defined below:
A robot walks on a 1-dimensional number line, with stride length 1. In any instant, he may stay put (+0), walk left (-1), or walk right (+1). For $n$ movements of the robot, enumerate the possible walks $W$ which result in the robot returning to where he started.
So far, I've found the following:
- For $n=1$, $|W|=1$
- For $n=2$, $|W|=3$
- For $n=3$, $|W|=7$
For $n \geq 4$, enumeration becomes more difficult as now 2 pairs of "switch-backs" are possible instead of just 1.
Any ideas? Is there a general solution?
Let's treat a walk as a sequence of letters L,S,R where L represents moving to the left, S represents saying put, and R represents a move to the right. For a walk $w$, define: $|w|_L, |w|_S, |w|_R$ to be the number of times $L$, $S$, and $R$ appear in the walk respectively. Obviously, you have $|w|_L+|w|_S+|w|_R = |w| = n$. But, you also have $|w|_L=|w|_R$ because every left move requires a right move to "undo" it and every right move requires a left move to "undo" it.
Let $a,b\in \mathbb{N}$. Define $W_{a,b} = \{w: |w|_L = |w|_R= a, |w|_S = b\}$.
It is easy to calculate $|W_{a,b}|$ since it is the number of permutations of the multiset $\{L\cdot a, S\cdot b, R\cdot a\}$ which is $\dfrac{(2a+b)!}{(a!)^2b!}$
So, you are looking for:
$$|W|_n = \sum_{k=0}^{\left\lfloor \dfrac{n}{2}\right\rfloor} \left|W_{k,n-2k}\right| = \sum_{k=0}^{\left\lfloor \dfrac{n}{2}\right\rfloor} \dfrac{n!}{(k!)^2(n-2k)!}$$
Example:
$$|W|_4 = \sum_{k=0}^2 \dfrac{4!}{(k!)^2(n-2k)!} = \dfrac{4!}{4!}+\dfrac{4!}{(1!)^2(2!)}+\dfrac{4!}{(2!)^2(0!)} = 1+12+6=19$$
In terms of hypergeometrics, you have:
$$|W|_n = {_2}F_1\left(\dfrac{1-n}{2},-\dfrac{n}{2};1;4\right) = 3^n\cdot {_2}F_1\left(\dfrac{1}{2},-n;1;\dfrac{4}{3} \right)$$
Here is Wolframalpha calculating the first 20 terms of the sequence.
More information on this sequence can be found Here