Catalan Structures

I learned about the Catalan Numbers in college, and they seem to come up again and again in my hobby coding projects. So let's explore!

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 "(x)y", where both x and y are valid nested parentheses themselves, possibly of length 0. Knowing that the zero-length string of balanced parentheses is trivially the empty string "", 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 x, and then substitute in all of the valid strings for y. Thus, if we have $n$ parentheses, then x can contain $i = 0 \dots (n - 1)$ pairs of parentheses; and then y 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 (or notches), 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 circle perpendicularly, for aesthetic purposes.

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

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}$ :

Chord Rotations

A curious side effect of the Circle Chord representation is that these circles can be rotated, producing a mapping between elements. Formally, the rotation operator ↷ is defined by remapping the notches incrementally by one, with wraparound. So a chord between notches 1 and 2 would now map between notches 2 and 3, after the application of the ↷ operator, while the last notch would be mapped onto notch 1, etc.

Since rotations eventually end up where they began, after completing a full 360°, and often even sooner, we can partition the set of all Circle Chord representations of a certain Catalan number $C_{n}$ into equivalence classes under repeated application of the rotation operator, and we can use one element from each partition as a canonical representative. The cardinality of this subset is of importance, as it has to divide $n$ .

To make the computation easier, notice that the rotation operator when applied to the parenthesis notation of a Catalan structure follows the rule x(y) ↷ (x)y.

Lattice Paths

Random Walk in 1D

Suppose we want to take a random walk on the whole number line with steps of length one, starting and ending at 0, but never dipping below 0. The number of such walks of length $2 n$ follows directly from the parenthesis example above. Each open parenthesis ( is a step in the positive direction, and each closing parenthesis ) is a move in the negative direction. To dip below 0, we'd have to hit an unbalanced closing parenthesis, which is forbidden!

In fact, another name for the parenthesis notation is that of a Dyck word, or more specifically, Dyck-1. By replacing parentheses with other characters, we can get other interpretations of the same structure. One is that of a Ballot Sequence. There is an election between two candidates A and B, with a total of $2 n$ votes (no abstentions) that finishes in a tie. What is the number of voting sequences (sequences in which each vote is announced), such that candidate A would never trail behild candidate B during any moment of reading the sequence? Again, an open parenthesis stands in for a vote for candidate A, a closed parenthesis stands in for candidate B.

Now let's take the random walk idea, but visualize it in two dimensions, with the whole number line placed vertically, and the time increment displayed horizontally. A step in the positive direction corresponds with movement in the direction (1,1), a step in the negative direction corresponds with movement in the direciton (1, -1). We end up with a lattice path on an n x n grid, flipped on its diagonal, spanning from one corner to the opposite one, such that no path dips below this diagonal.

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

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

Random Walks in 2D

This idea can cleverly be extended to random walks on the 2D lattice. Let's say we can move one step in any of the four cardinal directions, with these constraints:

The walk has to be of length $n - 1$
The walk has to end on the X-axis (the end position must be $y = 0$ )
The walk can never dip below the X-axis ( $y \geq 0$ )

For example, the five such walks of $C_{3}$ are as follows:

←←

←→

→←

→→

↑↓

This is somewhat surprising, at first! How do we translate from the 1D random walk to 2D? And why does the length of the walk go from $2 n$ to $n - 1$ ?

The conversion from the parenthesis notation is as follows:

Remove the first and last parentheses. The sequence is guaranteed to start with an opening parenthesis, and end with a closing parenthesis, so we're not "losing" any information.
Group the remaining characters in pairs
Convert from the character tuples to cardinal directions:
- ((
  :
  ↑
- ))
  :
  ↓
- ()
  :
  ←
- )(
  :
  →

Here is a loop of the $C_{10} = 16796$ possible 2D walks of length 9:

{{get2DWalkFromParentheses(generateIterativeCatalanParentheses(10, i))}}

Plane Trees

A Plane Tree (a.k.a. a Ordered Tree) is a tree with a certain node denoted as the root, and with the children being ordered (i.e. the order in which children are processed matters). Unsurprisingly, $C_{n}$ denotes the number of such plane trees with $n + 1$ nodes. We start yet again with the parentheses notation, and a root node. Every time we encounter an opening parenthesis (, we append a new child to the current node, and set that child as the current node. Every time we encounter a closing parenthesis ), we set the current node to its parent. Since the parenthesis representation is balanced, we will eventually end up at the root, and we'll never need to look at the root's parent (which by definition doesn't exist).

The Plane Tree with 11 nodes corresponding to the parenthesis notation ((()((()))()()))(())

As is tradition, let's list all of the cases for $C_{3}$ .

And we can cycle through the plane trees of $C_{10}$ , each with 11 nodes:

Binary Trees

A Binary Tree is just like a Plane Tree, except that each node can have only a left and a right child. In fact, a node can have only a right child, without a left. This structure is of course very familiar to most Computer Scientists. At this point you shouldn't be surprised that $C_{n}$ counts the number of binary trees with $n$ nodes. Just like before, we start with parenthesis notation, attaching a new node when a left parenthesis ( is seen, attaching it to the current child of the current node (or setting it as the root node if there is none), and setting the current node to point to this node. We also advance the node counter of the parent node. The logic is a bit more complicated for the closing parenthesis ). Upon seeing this, we "advance" the node counter of the current node, moving up the tree if the current node's counter reaches 2, and propagating until the current node is not exhausted. This explanation is somewhat convoluted, I admit. Another way to think about this is in terms of the Plane Graph; we do a 1:1 conversion from the Plane Tree to the Binary Tree, by taking each node (we ignore the root node of the Plane Tree), we set the first child of the Plane node as the left child of the Binary Node, and the next younger sibling of the current Plane node as the right child of the Binary Node. Critically, this is the direct sibling, not the cousin, or something odd like that. In a way, the leftmost line of descendants in the Plane Tree remains the leftmost path in the Binary Tree, whereas the root's children in the Plane Tree becomes the rightmost path in the Binary Tree.

The Binary Tree with 10 nodes corresponding to the parenthesis notation ((()((()))()()))(())

Let's see what corresponds to $C_{3}$ .

And now, $C_{10}$ on a timer:

Polygon Triangulation

We start with a regular polygon with $n + 2$ vertices. We can partition it into triangles whose vertices are the vertices of the polygon. The number of ways to do this is, of course, $C_{n}$ .

A dodecagon (12-gon) triangulation corresponding to the parenthesis notation ((()((()))()()))(()), including the corresponding embedded binary tree

We start by amending the Binary Tree representation by adding "dangling" nodes such that each original node has a parent and two children. This dangling representation ensures that each original node is surrounded by three other nodes. These original nodes will be the triangles of our triangulation, the "dangling" nodes will represent the edges of our triangulation. We will have $n$ original nodes, $n + 2$ "dangling" nodes, for a total of $2 n + 2$ nodes.

A "dangling" binary tree, obtained by adding "dangling" (white) nodes to a binary tree such that each original node (black) has three neighbors. ((()((()))()()))(())

We then enumerate the "dangling" nodes clockwise around the tree, in infix order, to map onto the edges of the polygon. The root "dangling" node receives the edge '0-1', the rightmost "dangling" node receives the edge '1-2', etc. until the leftmost "dangling" node receives the edge '(n-1)-0'. Then, working recursively bottom-up, each proper node infers its three edges from its children nodes.

Traditionally, $C_{10}$ on a timer:

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 {{hexToPartition("1A23495867")}}

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

And $C_{4}$ :

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

Murasaki Diagram

A Murasaki Diagram follows directly from the Non-intersecting partition example above. We take $n$ vertical bars, and connect them at the top if they belong to the same partition. Again, we get $C_{n}$ such structures.

Murasaki diagram matching the partition notation {{parenthesesToPartitions('((()((()))()()))(())').map((part) => `[${part.join(',')}]`).join(',')}}

Gallery

Let's put all of these representations of the same structure in one place. The timer advances the Catalan structure every $\frac{1}{2}$ second, and all tiles show one of the interpretations of the same bijective Catalan structure.

C_{{{n}}} = {{catalanNumber(n)}}

i = {{i % catalanNumber(n)}}

Balanced {{n}} pairs of parentheses

Random walk on nonnegative integers of length {{2*n}}, ending at 0

Voting sequence for two candidates {A,B} where A never trails, each getting {{n}} votes

Random walk in 2D of length {{n-1}}, ending on the X axis, never dipping below the X axis

Lattice paths on an {{n}} x {{n}} square, not crossing the diagonal

Plane Tree with {{n+1}} nodes

Binary tree with {{n}} nodes

Circle with {{n}} non-intersecting chords

Non interesecting partitions of {{n}} elements

Triangulation of {{n+2}}-gon

Murasaki Diagram of {{n}} items