cat(n) = (2n:n) / (n+1)
The numerator is the binomial coefficient 2n choose n.
These numbers pop up in many applications. For instance, there are cat(n) ways to arrange n pairs of parentheses, so that they are nested properly. We demonstrated this in the previous section. Here is another example, involving polygons.
Let f(x) be the generating function that describes the number of triangulations of a labeled s-gon. Here s = n+2. Thus an is based on the number of triangles, rather than the number of sides in the polygon.
Vertex 1, at the top of the polygon, may have no incident cords, or its first (clockwise) incident cord could join vertex j.
If it has no incident chords, then the two adjacent vertices are joined by a chord. Below this chord lies a polygon with one less edge and vertex. Therefore one component of an is an-1.
If vertex 1 is connected to vertex j, the chord creates to polygons, one with j edges and the other with s+2-j edges. How many ways can these two polygons be triangulated? You might think the answer is aj-2×as-j, and you'd almost be right.
The second polygon is unconstrained, but in the first polygon, 1 cannot be connected to anything other than 2 and j. We said j was the lowest vertex connected to 1. So 2 and j are connected to each other, and the number of triangulations is aj-3.
Take the sum of aj-3an+2-j as j runs from 3 to n+1. Reindex, so that j starts at 0, and write it this way.
an = ∑(j=0,n-2) ajan-1-j
Remember, when there were no chords incident to vertex 1, we had a term of an-1. Since a0 = 1, this is the same as an-1a0. Bring this in and get the following equation.
an = ∑(j=0,n-1) ajan-1-j
Finally, we need to start the series off with a0 = 1. With this in place, a1 = 1, which is what we want. The triangle is already triangulated.
Put this all together and get the following equation for f(x).
f = xf2 + 1
This is the same equation we saw earlier, when counting strings of nested parentheses. The result is the same:
an = cat(n) = (2n:n)/(n+1)
Now assume we are interested in the triangulations of an unlabeled s-gon. This may remind you of another problem we solved before. Place red yellow and blue beads in a circle, forming a necklace. But two necklaces are really the same if one can be rotated to coincide with the other. We aren't looking for individual color patterns, we are looking for orbits, a color pattern and all its distinct rotations. This is where the burnside polya theorem comes into play.
The group is the rotations of the vertices, denoted Zs. For each rotation, we need to identify the triangulations that are fixed by that rotation. For instance, a rotation of 0 causes the vertices to stay put, and every triangulation is valid. Thus χ(0) = cat(n).
Let the length of a chord be the number of vertices, traveling around the shorter side of the polygon, to get from one end of the chord to the other. The shortest possible chord has length 2 and the longest possible chord has length s/2.
Let j be the length of the longest chord. If j is less than s/3, then the chords inscribe a new polygon inside our original polygon, and this polygon has more than three sides. The shape is not fully triangulated. Therefore j is at least s/3.
If there is one chord of length j, and a rotation fixes the pattern, it has to fix this chord. It must exchange the two ends. Thus the chord is a diameter, j = s/2, and the rotation is 180 degrees.
If there are two chords of length j, j is less than s/2, else the two chords would cross. A rotation cannot swap the two ends of a chord, so if it is to fix the pattern, it must exchange the two chords. This is a rotation of order 2, i.e. 180 degrees. The two chords define a rectangle that is rotated onto itself. There is no way to connect a vertex of the polygon at one end of the rectangle to a vertex at the other, for that would make a chord longer than j. And if we don't make these connections, we have at least a rectangle in the middle, and the shape is not fully triangulated. Thus two chords of length j means the pattern is not fixed by any rotation.
Finally, let thre chords have length j. To avoid crossing edges, these chords must make an equilateral triangle. Thus j = s/3. This triangle is fixed by rotations of 120 and 240 degrees.
In summary, the only valid rotations are 0, 120, 180, and 240 degrees. Let's look at the 180 degree rotation. The number of patterns fixed by this rotation is the possible lines of symmetry, s/2 of them, times the valid triangulations of half the shape, which has s/2+1 vertices. Thus χ(180°) = s/2×cat(s/2-1).
Using similar reasoning, χ(120°) = χ(240°) = s/3×cat(s/3-1). Put this all together to get the following equation. Remember, the second term is only valid if s is even, and the third term is only valid if s is divisible by 3.
triangulations(s) = ( cat(s-2) + s/2×cat(s/2-1) + 2s/3×cat(s/3-1) ) / s
Set s = 12 to find 1410 distinct triangulations of the dodecagon.