Several seemingly unrelated problems that produce the same sequence

Lets have a quick look at following problems:

1. Counting Valid Parenthesis
   Given n pairs of left and right parentheses, find the number of valid parentheses expressions.
2. Number of Unlabelled Binary Trees
   Given n nodes, count the number of different binary tree structures that can be formed.
3. Possible Unique BSTs
4. And many more …

Link -> Examples of Catalan numbers
There is a good youtube video for more examples

What do these problems have in common? Can you guess ?

They all follow a specific sequence which is
1, 1, 2, 5, 14, 42, 132… (indexing starting from 0)

For an example, lets take first problem
“Consider the problem of counting valid expressions using n pairs of parentheses”

For n = 3, the valid combinations are:
((()))
(()())
(())()
()(())
()()()
Total = 5 (The 3rd number in the sequence)

But from where does this sequence came from ?

Revealing the hidden connection — The Catalan Numbers

The number in above example is not arbitrary — it is exactly the 3rd Catalan number.

The nth Catalan Number is given by

and the sequence becomes C0, C1, C2 ...and so on

Just a note, the recurrence relation equivalent of above formula is also discussed later in the article

But Why these problems follow this sequence ?

Catalan numbers appear whenever a structure can be formed by choosing a root (or split point) and independently building two smaller structures on its left and right.

At first glance these problems look unrelated, but they all share the same structural property.

Building the intuition for Catalan Number formula

Lets take the problem “Given n nodes, find the number of ways to arrange them in a Binary Tree”

This problem also follows the same sequence of Catalan numbers.
1, 1, 2, 5, 14, 42, 132…

Lets understand the underlying structure for Catalan number formula

Every binary tree consists of a root, a left subtree, and a right subtree.

root
├── left subtree
└── right subtree

If the tree has n nodes:

• the root uses 1 node
• the remaining n − 1 nodes are divided between the left and right subtree

root consumes = 1 node
left subtree  = i nodes
right subtree = (n − 1 − i) nodes

Total possible binary tree structures will be given by following formula (which is nothing but equivalent recurrence relation for above mentioned nth Catalan number )

This formula comes directly from the structural decomposition discussed earlier.

A structure of size n decomposes into two independent substructures of size i and n−1−i.

Why we multiply

If:

• the left side can be formed in C_i ways
• the right side can be formed in C_{n-1-i} ways then the total number of structures for this split is:

because the two sides are independent.

Why we sum

The split between left and right can happen in multiple ways:

• left gets 0 elements
• left gets 1 element
• left gets 2 elements
• …
• left gets n-1 elements

For each possible split we count the number of structures, and add them together.
That is exactly what the summation does.

The Big Takeaway

At first glance, problems like counting valid parentheses, possible binary trees, and unique BSTs seem completely unrelated.

But while looking at their structure, they all follow the same pattern.

The lesson is that many algorithmic problems are not about discovering new formulas, its about recognizing familiar structures in different forms.

Once the underlying pattern is determined, we can tweak the implementation here and there as per the requirement of the problem.

Author’s Notes

I enjoy breaking down complex computer science ideas into simple mental models.

If you found this useful, feel free to connect or share your thoughts by connecting with me on linkedin