Number of ways to join the points Ok, now consider joining $2n$ points on a circle using $n$ nonintersection chords. 
How do I prove that the number of ways to join the points equals then $n$-th Catalan number $C_n$?
Thanks!
 A: André has sketched one of the two natural approaches. Here’s one of the more straightforward versions of the other. 
If you know that $C_n$ is the number of strings of $n$ pairs of correctly matched parentheses, you can try to find a bijection between ways of joining your $2n$ points and correctly matched strings of $n$ pairs of parentheses. 
Label the points $1,2,\dots,2n$ clockwise around the circle. Each chord then corresponds to a pair of distinct numbers in $\{1,\dots,2n\}$. Use the chords to lay out a row of $2n$ parentheses, $p_1,p_2,\dots,p_{2n}$, according to the following rule. If the points $k$ and $\ell$ are connected by a chord, and $k<\ell$, make $p_k$ a left parenthesis and $p_\ell$ a right parenthesis.


*

*Show that the resulting string of parentheses is correctly matched. (The fact that the chords don’t cross one another is important here.)

*Show that the proceduce is reversible: given a correctly matched string of $n$ pairs of parentheses, there’s a way to reconstruct a set of non-intersecting chords that give rise to it.
A: The most direct approach is to use the recurrence relation $C_{n+1}=\sum_0^n C_iC_{n-i}$ for the Catalan numbers. 
Let $S_n$ be the number of ways to do your division. If you can show that the sequence $(S_n)$ satisfies the same recurrence as $(C_n)$, and the same initial condition, then you will have proved that $(S_n)=(C_n)$ for all $n$.
Getting the recurrence for the sequence $(S_n)$ is geometrically quite natural. You may want to look at the Wikipedia article on the Catalan numbers. Working directly with the closed form formula $C_n=\frac{1}{n+1}\binom{2n}{n}$ would be more difficult than using the recurrence suggested above. 
