Combinatorics proof for number of paths starting from the origin and returning to the origin only at step $2n$.

Question

I have a (one dimensional) random walker, that at each time-step can either step to the right or left, starting from the origin. I wanted to compute the number of paths that this walker can go through to return to the origin for the first time after exactly $2n$ steps. I have done so by solving a recursive algebraic equation involving paths going through the origin at any time in between, and I have arrived at the following answer: $$ \frac{1}{2n-1}{2n \choose n}. $$

My question is if there is a simple combinatorics proof for this answer.

The term ${2n \choose n}$ is clearly the number of paths of length $2n$ that start and end at the origin. So the term $1/(2n-1)$ should be the fraction of such paths that do not cross the origin at any time in between. Is there a simple explanation for this that does not require any algebra?

Answer 1

It's twice $C_{n-1}$, the $(n-1)$st Catalan number. Now use a combinatorial argument for the formula for Catalan numbers, e.g. the second proof in https://en.wikipedia.org/wiki/Catalan_number.

Answer 2

I can give a combinatorial explanation, let's see it if it is satisfying to you.

Paths of length $2n$ come in two varieties; the first and last steps are either opposite directions, or they are the same direction. If these steps are the same direction, then the path must touch the origin sometime in between. Therefore, your question can be broken down into two problems:

1. How many paths start and end with steps in different directions?

2. Of those paths, how many never return to the origin?

For question $(1)$, the number of paths is $$ \frac{n}{2n-1}\binom{2n}n $$ For a probabilistic proof, note that if the first step is to the right, then the probability that the the path ends with a leftward step is $\frac{n}{2n-1}$, since there are $2n-1$ steps remaining to distribute, $n$ of which are right steps.

For question $(2)$, we can show that the proportion of paths in $(1)$ which never return to the origin is $$ \frac1n $$ You prove this by dealing with the paths start with a right step separately from the paths which start to the left. We can partition the paths which start to the right into groups of size $n$ where exactly one path in each group never touches the origin. For a proof, see the proof of the Catalan number formula by equi-partition in the Wikipedia page for Catalan numbers.