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 . Now, starting at this point, label the rest of the points by proceeding in a clockwise direction. First, we will choose the point to which will be “connected” via a chord.
Is it really possible to choose any of the points to connect with ? No, because say for example we choose . Then we observe the phenomenon above occuring, that is, and can no longer be joined, since intersections are disallowed. So we arrive at the conclusion that the only valid choices to join to are , that is, for any .
Now, say we’ve joined with . Notice that we have now divided the circle into two regions, one of which is made up of unpaired points, and the other made up of points.
Let us denote (and my use of notation here is of course no coincidence) the solution to the problem in the case of points by . Then by the above argument, we note that we can choose any . With this chosen, obtain one subproblem of size and another of size . So the total number of ways, then, to solve the original problem is, in words:
(number of ways to solve subproblem 1 when is chosen) * (number of ways to solve subproblem 2 when is chosen) + … + (number of ways to solve subproblem 1 when is chosen) * (number of ways to solve subproblem 2 when is chosen).
This is expressed in summation notation as
This is the Catalan recurrence. Putting , 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 into nonempty, disjoint subsets, each containing 2 elements. I will examine the possibility of extending this reasoning to partitions of the set into nonempty, disjoint subsets, each containing m elements, and perhaps generalize the Catalan sequence in this manner.