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