2n points on a circle: Episode 1

Recently I came across a problem that asked:

Say we have a circle with 2n points. In how many different ways can we connect these 2n points by n chords, so that no two chords intersect?

This is interesting, and the answer turns out to be given by a sequence of special combinatorial significance known as the Catalan numbers (1, 1, 2, 5, 14, 42, and so on). My approach for proving this is as follows. Pick, at your will, any arbitrary point lying on this circle. Call this point p_1. Now, starting at this point, label the rest of the points p_2, p_3, \ldots, p_{2n} by proceeding in a clockwise direction. First, we will choose the point to which p_1 will be “connected” via a chord.

On the left, a legal choice for a chord. On the right, an illegal choice - note how the remaining two points cannot be joined without intersecting the black chord!

Is it really possible to choose any of the points p_2, p_3, \ldots, p_{2n} to connect with p_1? No, because say for example we choose p_3. Then we observe the phenomenon above occuring, that is, p_2 and p_4 can no longer be joined, since intersections are disallowed. So we arrive at the conclusion that the only valid choices to join p_1 to are p_2, p_4, \ldots, p_{2n}, that is, p_{2i} for any i \in \{ 1, \ldots, n \}.

Now, say we’ve joined p_1 with p_{2i}. Notice that we have now divided the circle into two regions, one of which is made up of 2i - 2 = 2(i-1) unpaired points, and the other made up of 2n - 2i = 2(n-i) points.

Let us denote (and my use of notation here is of course no coincidence) the solution to the problem in the case of 2n points by C_n. Then by the above argument, we note that we can choose any i \in \{ 1, \ldots, n \}. With this i chosen, obtain one subproblem of size 2(i-1) and another of size 2(n-i). So the total number of ways, then, to solve the original problem is, in words:

(number of ways to solve subproblem 1 when i=1 is chosen) * (number of ways to solve subproblem 2 when i=1 is chosen) + … + (number of ways to solve subproblem 1 when i=n is chosen) * (number of ways to solve subproblem 2 when i=n is chosen).

This is expressed in summation notation as
C_n = \sum\limits_{i=1}^n C_{i-1} C_{n-i}

This is the Catalan recurrence. Putting C_0 = C_1 = 1, which seem to be the natural choices for the base cases, we obtain the Catalan numbers!

In my next post: I will examine what I believe to be the more abstract underpinnings of what is going on here. The idea is that this problem concerns partitions of the set \{ 1, \ldots, 2n \} into nonempty, disjoint subsets, each containing 2 elements. I will examine the possibility of extending this reasoning to partitions of the set \{ 1, \ldots, mn \} into nonempty, disjoint subsets, each containing m elements, and perhaps generalize the Catalan sequence in this manner.

Advertisements

About mlbaker

just another guy trying to make the diagrams commute.
This entry was posted in combinatorics and tagged , , . Bookmark the permalink.

One Response to 2n points on a circle: Episode 1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s