Enumerating 1-dimensional walks

Question

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?

I haven't though about it yet. But one initial thought is from any walk $w$ in $n-1$ returning to starting point, you can get a walk in $n$ by adding "stay put" (+0) before or after any of the steps in $w$. Similarly, any walk in $n-2$ can be used to recover a walk in $n$ by adding a $(-1)$ somewhere and a $(+1)$ somewhere. Not sure if these will lead you to any substantial solution — NazimJ, Oct 30 '19 at 21:01
After writing a Python script, I have a few more results for analysis: $n = 4$, $|W| = 19$
$n = 5$, $|W| = 51$

$n = 6$, $|W| = 141$ — Benjamin Crawford Ctrl-Alt-Tut, Oct 30 '19 at 21:01
@InterstellarProbe Unfortunately, $n=4$ gives 19, so it breaks that pattern. — Benjamin Crawford Ctrl-Alt-Tut, Oct 30 '19 at 21:03
There are other things you could potentially use to exploit parity. The fact that $(+0)$ is equivalent to any pair of $(+1)$ and $(-1)$. Or that steps to the left and to the right must occur in equal numbers. Probably you have to break it up into cases when $n$ even and when $n$ odd — NazimJ, Oct 30 '19 at 21:05
(This comment got sniped by the previous one, but may be useful as method.) A useful resource for such problems is the Online Encyclopedia of Integer Sequences. Your sequence evidently proceeds as 1,3,7,19,51,141..., which yields two possible hits. If we look at the first entry in the search A002426, then one indeed finds this problem listed as an application (see Emeric Deutsch's second comment) — Semiclassical, Oct 30 '19 at 21:28

SlipEternal · Accepted Answer · 2019-10-30T21:27:22.220

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

Enumerating 1-dimensional walks

1 Answers1