[Math] Prove that number of non-cross partitions of a set is Catalan number

Question

The title should be clear, how to prove that number of non-cross partitions of a set is Catalan number?

For example, if we have a set S = {1,2,3,4}, the number of non-cross partitions is 14, because of all the 15 possible partitions S, {{1,3},{2,4}} are excluded.

Answer 1

The Catalan numbers are defined by the recurrence \begin{align*} C_0 &= 1 \\ C_{n+1} &= \sum_{j=0}^n C_j C_{n-j} \text{ for } n \ge 0 \end{align*} Therefore, if $f(n)$ is the number of non-cross partitions of $\{1,2,\ldots, n\}$, we just need to show that $f(n)$ satisfies the above.

There is one non-cross partition of the empty set (the partition with no parts). So $f(0) = 1$.

Now, consider a non-cross partition of $\{1,2,3,\ldots,n+1\}$. To count how many such partitions there are, we do casework on the minimum value of the set in the partition containing $n+1$ (call this set $S$). If $S$ has minimum value equal to $k$, then:

• $k$ and $n+1$ are connected, so $\{1,2,3,..,k-1\}$ must be split into a non-crossing partition on their own. There are $f(k-1)$ ways to form this partition.
• The numbers $k$ through $n$ can form any non-crossing partition between themselves, because from that partition we can then connect $k$ to $n+1$ without causing any crosses. Thus there are $f(n+1-k)$ ways to partition the values $k$ through $n+1$.

$k$ can be anything between $1$ and $n+1$, so we have $$ f(n+1) = \sum_{k=1}^{n+1} f(k-1)f(n+1-k) = \sum_{j=0}^n f(j)f(n-j) $$

Thus $f$ and $C$ satisfy the same recurrence and initial value, so (by induction, if you like) $f(n) = C_n$ for all $n$.