Prove that number of non-cross partitions of a set is Catalan number 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.
 A: 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
A: 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$.
