# An Intuitive Partition for the Catalan numbers

The nth Catalan number, $C(n)$ counts the number of binary strings with n $0$'s and n $1$'s such that any initial substring has at least as many $0$'s as $1$'s.

I know that the formula for the nth Catalan number is $C(n)=\frac{1}{n+1}\binom{2n}{n}$ and the formula for the number of binary strings with n $0$'s and n $1$'s is just $B(n)=\binom{2n}{n}$

Is there an natural way to partition the set of all binary strings with n $0$'s and n $1$'s into sets of size $n+1$ such that each partition contains exactly one string with the property that any initial substring contains at least as many $0$'s as $1$'s?

The answer is yes; it’s implicit in this proof that $C_n=\frac1{n+1}\binom{2n}n$. In the terminology there, start with any path whose exceedance is $0$, and reverse the algorithm to produce in succession paths with exceedance $k$ for $k=1,\dots,n$.
Consider the ${2n\choose n}$ possible lattice paths starting from the origin and consisting of $n$ upsteps $(1,1)$ and $n$ downsteps $(1,-1)$. It turns out, surprisingly, that the number of these paths with $i$ upsteps above the $x$-axis $(0\leq i\leq n)$ is the same, regardless of the value of $i$. Consequently, the number of paths with all $n$ upsteps above the $x$-axis must be ${2n\choose n}/(n+1)$.