Catalan numbers: why is there a division by $(n+1)$

Question

There are many interpretations of the Catalan numbers. The one I relate to most readily is the number of paths from the bottom-left to the top-right of an $n \times n$ grid which don't cross the main diagonal. The number of ways to do this is:

$$C_n = \frac{2n \choose n}{n+1} = {2n \choose n} - {2n \choose n-1}$$

The second expression in the equation above has a very neat, intuitive explanation which is described in the answer by @Marcus M here which involves mapping the undesirable paths (that do cross the main diagonal) to a smaller grid. That explanation, I understand.

However, there must also be a way to directly interpret the first expression. The total paths in the grid are $2n \choose n$. and the number of paths that don't cross the main diagonal are a very specific fraction of the total paths: $\frac{2n \choose n}{n+1}$. What is the intuitive reason that for every $n+1$ paths in the grid, one of them doesn't cross the main diagonal?

When I ask this question to people who haven't heard of it before, their first instinct is to say half the paths should not cross the main diagonal. I know one of the things that makes them way off is that towards the end of the path, the probability that you'll cross the main diagonal becomes quite high. Is there a more concrete line of attack?

Answer 1

I think there’s an easier way to see this than the third proof on Wikipedia, modulo one detail I haven’t fully justified (marked with * below).

Each of the $2n\choose n$ paths from $(0,0)$ to $(n,n)$ can be identified with an $n+1$-tuple, where the $i$-th entry is the number of vertical steps taken at $x=i$. For example, this image shows the vertical portions of the $n=7$ path with $8$-tuple $(0,2,0,1,3,0,0,1)$.

Now, if you look at the paths corresponding to all $n+1$ cyclic permutations (rotations) of the tuple (these are all distinct, because the sum of the entries, $n$ is relatively prime to $n+1$), exactly one of the paths stays below the diagonal*.

Here are the $8$ paths for the tuple $(0,2,0,1,3,0,0,1)$ and the $8$ paths for the tuple $(1,1,3,0,0,2,0,0)$, again with just the vertical segments shown.

Thus $1\over n+1$ of the $2n\choose n$ paths stays below the diagonal.

These groups of paths (corresponding to the rotations of a single tuple) are the same groups of paths given in the Wikipedia proof, but not in the same order.