Catalan Structures

I learned about the Catalan Numbers in college, and they seem to come up again and again. So let's jump into them.

Balanced Parentheses

Let's start with what to me seems like the easiest example. I give you $n$ opening and closing parentheses. You have to come up with all strings of these parentheses which are perfectly balanced. More precisely, each closing parenthesis has to have a corresponding opening parenthesis earlier in the sequence. Obviously, we have to start with an opening parenthesis, and end with a closing parenthesis. But what happens in the middle?

As it turns out, this is our first Catalan structure. For one pair, we have the trivial string "()". For two, we can do either "()()" or "(())". For three, it starts to get more interesting. Here they are:

()()()

()(())

(())()

((()))

(()())

For four pairs of parentheses, we get the following set of 14:

In general, let's set up this little applet which cycles through the 16796 possible parentheses of length 20 (so 10 left- and 10 right-parentheses)

Catalan Numbers

In general, each string of nested parentheses above can be expressed uniquely with the formula "(a₁)a₂", where both a₁ and a₂ are valid nested parentheses themselves, possibly of length 0. Knowing that the zero-length string of balanced parentheses is trivially "", we now have a method to generate all of the possible strings. We recognize that the formula already uses one pair of parentheses, so we need to loop over the possible lengths of a₁, and then substitute in all of the valid strings for a₂. Thus, if we have $n$ parentheses, then a₁ can contain $i = 0 \dots (n - 1)$ pairs of parentheses; and then a₂ will use $j = n - i$ parentheses.

This also leads us to a recursive expression for the Catalan number $C_{n}$ . We know that $C_{0} = C_{1} = 1$ , and we have the recurrence $C_{n} = \sum_{i = 0}^{n - 1} C_{i} C_{n - i - 1}$ . This produces this table of Catalan numbers:

$n$	$C_{n}$
{{n}}	{{catalanNumber(n)}}

Circle Chords

Suppose we have a circle with $2 n$ points, spaced equally around that circle. We want to connect these points in pairs with chords, without them intersecting. How do we enumerate all of the possibilities? Yet again, the Catalan Numbers are relevant, and this becomes our second Catalan Structure.

We can trivially translate from the parenthesis representation to another, equivalent representation that is more fitting to the circle chords case. We enumerate the notches on the circle from $1$ to $2 n$ . Then using our parenthesis representation, indexing the first position with 1, second with 2, etc, we pair up the indices of the opening and corresponding closing parenthesis. Then the parenthesis representation "()()(())()" becomes "12-34-58-67-9A". For clarity, I use the hexadecimal representation for values above 9. I also display the chords using chord diagram arc segments that meet the cricle perpendicularly, for aesthetic purposes.

Circle with 10 pairs of non-intersecting chords, corresponding to the integer representation '12-34-58-67-9A'

Just as above, let's list all of the cases for $C_{3}$ :

And $C_{4}$ :

Let's also cycle through the chords of $C_{10}$ :

Lattice Paths

Suppose we consider the set of lattice paths on an n x n grid, from one corner to the other, which do not cross the diagonal. We can stick to showing only the upper-triangular section of this grid, placing the diagonal horizontally at the bottom. Taking inspiration from the balanced parenthesis notation, whenever we have an opening parenthesis "(", we move upwards, otherwise we move downwards. Naturally, we would only cross the diagonal if an only if our string contains an unbalanced closing parenthesis.

Lattice paths on an 10 x 10 square, not crossing the diagonal, corresponding to the parenthesis representation '()(())(())'

Yet again, we'll cycle through the structures for $C_{10}$ :

Non-intersecting partitions

This took me a while to figure out. Space $n$ points around a circle, and see how many ways you can partition these points without the lines intersecting. One way to think about this is to go back to the circle chords structures (which space $2 n$ points around the circle), and designate each pair of adjacent points as one of the $n$ points for this case. Now, partition the points into sets based on if any two points don't have a chord in between them. It makes more sense to use straight-line chords.

One non-intersecting partition of 5 points on a circle (highlighted in red), corresponding to the numerical notation '1A23495867' {{numericalToPartition("1A23495867")}}

Just as above, let's list all of the cases for $C_{3}$ . For convenience, I don't color the subsets of size one, I let them just be.

And $C_{4}$ :

And finally, cycling through the $C_{10}$ :

{{generateIterativeCatalanParentheses(10,i)}}
{{numericalToPartition(generateIterativeCatalanNumerical(10,i))}}