Combinatorics problem in walking left and right

Question

In this game, there will be $n$ turns. For the sake of clarity, let us say $n = 4$.

We have three options in this game: we can either stay in place ($O$), we can step to the left ($L$), or we can step to the right ($R$). However, the ability to step left only occurs on the the odd numbered turns, and the ability to step right only occurs on the even numbered turns. You may always choose to stay in place.

The goal of the game is to end up where you started. For example, this will work: $OOOO$, which represents always staying in place for each of the $n =4$ turns.

This will also work $LRLR$, as you will end up where you started with. Other examples are $ORLO$.

Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns.

Is there a way to find out (a) how many ways there are to do this?, (b) what is the distribution of these ways, labelled by the number of $L$ steps in total?

Observations:

1. There must be the same number of $L$'s and $R$'s in your sequence.
2. For $n$ odd, there must be an odd number of $O$'s.
3. For $n$ even, there must be an even number of $O$'s.

Does anyone have any ideas? Is this a game anyone has played anywhere else before?

Answer 1

I am assuming $n$ is even in the below.
You need the same number of $L$ moves as $R$ moves. There are $\frac n2$ odd turns where you might move left. If you move left $k$ times, there are ${n/2 \choose k}$ ways to choose the moves for left and similarly for the ways to choose the moves for right, so the total number of ways to wind up at the beginning is to sum over $k$ and get $$\sum_{k=0}^{n/2}{n/2 \choose k}^2$$ Alpha tells me this is $$n \choose n/2$$ and there is a neat combinatorial proof. Choose $n/2$ of the $n$ moves. For all the chosen moves make an $L$ for odd moves and an $O$ for even moves. For the non-chosen moves make an $O$ for odd moves and an $R$ for even moves. We have a bijection between the selections of $n/2$ and the strings that return you to the origin because the number of selected odd moves matches the number of non-selected even moves.

Answer 2

The count of sequences is the count of ways to select $k$ from $\lfloor n/2\rfloor$ places for R and to select $k$ from $\lceil n/2\rceil$ places for L, for every $k$ that is an integer in $\{0,..,\lfloor n/2\rfloor\}$.

$$X_n~{=\sum_{k=0}^{\lfloor n/2\rfloor}\dbinom {\lfloor n/2\rfloor}k\dbinom{\lceil n/2\rceil}k\\ =\sum_{k=0}^{\lfloor n/2\rfloor}\dbinom {\lfloor n/2\rfloor}{\lfloor n/2\rfloor-k}\dbinom{\lceil n/2\rceil}k\\=\binom{n}{\lfloor n/2\rfloor}}$$

(since $\lfloor n/2\rfloor+\lceil n/2\rceil=n$)

---

Vandemonde's Identity: for any positive integers $p,q,r$: $$\sum_{k=0}^r \dbinom pk\dbinom q{r-k}=\dbinom{p+q}r$$

Answer 3

The number of ways is $\binom{n}{\lfloor n/2 \rfloor}$. Imagine a player that tries to move as far as possible to the right; on odd turns, they stay put, and on even turns, they move right. After $n$ turns, their position will be $\lfloor n/2\rfloor$. In order to change their behavior so that they end at the origin, you need to select exactly $\lfloor n/2\rfloor$ of their turns and command them to do the opposite action on each selected turn.

You asked about the distribution of the number of left steps as well. The number of ways to end up at the start having taken exactly $\ell$ left steps is $$ \binom{\lceil n/2 \rceil}{\ell}\binom{\lfloor n/2 \rfloor}{\ell} $$ Dividing by the total number of ways, $\binom{n}{\lfloor n/2 \rfloor}$, the above defines a probability distribution known as the hypergeometric distribution. This arises when you have a population of $n$ people, $m$ of whom are considered special, and you sample $k$ of these people without replacement. The hypergeometric distribution governs the number of special people in your sample. This distribution is bell-shaped, and approaches a normal distribution as $n$ gets large.