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