6
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for spending the time to write that! helped a lot. $\endgroup$
    – MITjanitor
    Jan 23 '13 at 8:21
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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