# Number of non-cross partitions of a set is the $n$th Catalan number

How can we prove that the number of non-crossing partitions of a set of $$n$$ elements is the $$n$$th 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, only $$\{\{1,3\},\{2,4\}\}$$ is excluded.

• If anyone else is unsure what is meant by "non-cross partitions", after searching I believe it means this Commented Jan 6, 2014 at 7:16

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$.

The most straightforward way of proving that the number of noncrossing partitions is given by the Catalan number is introducing a bijection between the set of noncrossing partitions of $[n]$ and the set of balanced parentheses or any other well-known set whose cardinality is characterized by the Catalan number. This notes (http://www.maths.usyd.edu.au/u/kooc/catalan/cat46conv2.pdf) provides an algorithm of finding noncrossing partition of $[n]$ from a sequence of balanced parentheses; checking that the algorithm is a bijection is not hard.

Murasaki diagrams are closely related if you are interested: http://www.maths.usyd.edu.au/u/kooc/catalan/cat58mura.pdf