Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question: Letting 2n be the number of points on a circle, prove that the number of ways to join these points, with non-intersecting lines, into pairs is equal to the Catalan numbers.

I'm having troubles understanding how to give a solid proof for this. When I think intuitively it makes sense. Any ideas on how to start the recurrence?

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

First of all, I need to remark that the current formulation of the question doesn't seem to be quite right, since the fact that you're working on a circle isn't really used. It also isn't very clear what you mean by "joining into pairs.

However, if I read this question in the following way, it seems to work: We choose $2n$ arbitrary points on a circle. How many ways are there of drawing $n$ lines between $2$ points, such that there are no intersections between these lines inside the circle?

How to prove this? It is easiest to follow what's going on by drawing a few examples and keeping these nearby while reading this. We will denote the number of possibilities given $n$ as $Q_n$.

Now suppose we have $n$ fixed, as well as $2n$ points on a circle. We will fix one point $p_1$ and then give names clockwise: the first point one encounters when walking along the circle, starting from $p_1$, is called $p_2$, etc. The first thing now is to consider to which points $p_1$ may be connected. We remark that if we draw a line between $p_1$ and $p_i$, this divides the remaining points in the sets $X_1=\{p_2,\ldots,p_{i-1}\}$ and $X_2=\{p_{i+1},\ldots,p_{2n}\}$, each corresponding to the points on one side of the line. Since no two lines may intersect within the circle, this imposes a restriction on the possible points $p_1$ may be connected to. Namely, this needs be done in such a way that both sets $X_i$ have an even number of points. That is, we may connect the point $p_1$ to each point $p_{2j}$ with $1\leq j \leq n$. This can easily be seen in a drawing.

Now, what happens when we join up the point $p_1$ with one such point? We have a set $X_1$ of $2n_1$ points lying on a circle that need to be pairwise connected in such a way that no lines intersect, while the same holds for the $2n_2$ points in $X_2$. We therefore notice that if we connect the point $p_1$ to $p_i$, the remaining number of possible line configurations becomes $Q_{n_1}Q_{n_2}$.

The result can now be obtained by adding the numbers of possible configurations corresponding to each line from $p_1$ to some $p_i$. What we get, is that $Q_n = Q_{n-1} + Q_1Q_{n-2}+...+Q_{n-2}Q_1+Q_{n-1}$. It is best to first write it this particular way to avoid any problems `in the middle' when $n$ is odd. If we define $Q_0$ as $1$ (one could argue that there is exactly one way not to draw any lines inside a circle at all), we can express every $Q_n$ by the recurrence relation

$Q_0=1,\qquad Q_n=\sum_{j=0}^{n-1}Q_jQ_{(n-1)-j}.$

I don't know how Catalan numbers have been defined in your case, but this recurrence relation describes them. If you don't know this yet, there must be plenty of sources out there to prove it for you.

share|improve this answer
    
Thanks for spending the time to write that! helped a lot. –  MITjanitor Jan 23 '13 at 8:21
add comment

I'll assume that you intended to ask about the number of ways to connect the points in pairs by non-intersecting line segments.

Pick one of the $2(n+1)$ points and consider all options for pairing it. In each case, the line segment divides the remaining points into two sets that need to be connected among themselves. That yields the recurrence

$$ C_{n+1}=\sum_{i=0}^nC_iC_{n-i} $$

satisfied by the Catalan numbers.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.