Nonintersecting chords of a circle

By trying small cases, we recognize the pattern of $1, 2, 5, 14, 42$ gives us the Catalan numbers.

We will prove that the number of ways to arrange these $2n$ points is given by $C_n = \frac{1}{n+1} { 2n \choose n }$ , by setting up a bijection with the number of "mountain ranges" which are formed by $n$ upstrokes and $n$ downstrokes that all stay above the $x-$ axis.

Given any set of non-intersecting chords, we will construct a mountain range in the following manner:

Starting from vertex 1, if the vertex is connected to a vertex of larger index, then we move up the mountain range. Otherwise, we will move down the mountain range. Let's see why this gives us " $n$ upstrokes and $n$ downstrokes that do not go below the $x-$ axis".

• Each chord connects a smaller vertex to a larger index, so we will have $n$ upstrokes and $n$ downstrokes.
• Let's consider the height of the mountain range at vertex $k$ . Consider the chords that involve vertices 1 to $k$ (and their partners). Let's ignore the chords that connect 2 vertices from 1 to $k$ , since they do not affect the height of the mountain range (we move up and then move down). We are left with vertices that can only connect to higher numbers (since there are no lower numbers). This tells us that the mountain has a non-negative height, so we do not go below the $x-$ axis.
• This map is injective, since the up-down strokes are determined by the chords.

The correspondence is demonstrated below:

Note: In this map, we did not use the fact that the chords are non-intersecting! In fact, there are intersecting chord diagrams that would give us the same mountain range. For example, if the vertices $1-3, 2-4, 5-6$ were paired up, we will get the same mountain range as depicted in the first pair.

Now, let's find a map from the mountain ranges to the non-intersecting chords. As hinted in the previous paragraph, the potential difficulty is to ensure that the chords do not intersect.

Given any mountain range, we label the points $1$ to $2n$ . If the path goes up, we denote the vertex with a $+$ . If it goes down, we denote the vertex with a $-$ . We then connect up the lines in the following manner:

Starting from vertex 1, look for a consecutive pair of vertices that are of the form + then -. If so, we connect these up with a chord, and then ignore them. We resume looking for consecutive pairs of vertices that are of the form + then -. Let's see why this leads to $n$ chords that do not intersect.

• First, it's obvious that at each step, we can find a pair of vertices and remove them, thus this process will eventually end.
• Each chord connects a + with a -. Since there are $n$ + and $n$ -, thus there are $n$ chords (when the process ends).
• The act of "removing vertices" ensures that we do not have chords which will intersect these previously drawn chords.
• This map is injective due to the sequence of steps that we took.

The correspondence is demonstrated below:

Finally, since we have 2 injective maps, we have established that the sizes of these sets are the same.

---

I believe that these maps form a bijection, but it's not immediately obvious to me. Any thoughts would be welcome.

Suppose $r_n$ is the number of ways to connect the points in pairs with no intersecting cords, with no point left unconnected.

The main idea of my solution is to find a relation among the $r$ 's. Pick a random starting point and connect it to the point on its immediate left. The number of ways to connect the rest is $r_{n-2}$ . Move the endpoint two points to the left. Since the chords cannot intersect each other, we now have two subproblems: number of ways to connect two points and number of ways to connect the remaining $n-4$ points. This idea goes on until the endpoint coincides with the starting point.

To final answer is to sum all the values we found. Mathematically, the recurrence relation is $r_n = r_0 r_{n-2} + r_2 r_{n-4} + \dots + r_n r_0 = \sum_{i=0} ^ {n / 2} r_{2i} r_{n-2i}$ with the base cases $r_0 = 1$ . What we left to do is to slowly build up $r_n$ to find the value of $r_{10}$ .

It is nth catalan number.

If $\large n$ = no. of points = $2m$

then the no. of nonintersecting chords = $\large \frac{n \choose m} {(m+1)} = \large \frac{10 \choose 5} {(6)} = 42$