Mathematics
Catalan Numbers and Their Occurrence in Combinatorics
Quick fact
The Catalan numbers appear in over 200 different combinatorial problems—from counting valid bracket arrangements to counting the ways to parenthesize an expression. For example, the 5th Catalan number (42) equals the number of ways to fully parenthesize a sum of 6 numbers, and the 10th Catalan number (16796) counts the number of full binary trees with 11 leaves.
Why this is interesting
You might have noticed that the number of ways to arrange parentheses, triangulate a polygon, or climb a staircase sometimes gives the same surprising sequence. What hidden connection links these seemingly different problems?
Read the full explanation
Understanding Catalan Numbers and Their Occurrence in Combinatorics
Start with a simple question: how many ways can you arrange n pairs of parentheses so that they are correctly matched? For n=1, you get '()' – 1 way. For n=2, you get '(())' and '()()' – 2 ways. For n=3, there are 5 ways: '((()))', '(()())', '(())()', '()(())', '()()()'. This sequence – 1, 2, 5, 14, 42 – is the Catalan sequence. The key is to see that the first symbol must be '(', and it naturally splits the remaining parentheses into two independent groups: one inside that first pair and one after it. This leads to a recursive definition: the nth Catalan number is the sum of products of smaller Catalan numbers. This same recursion appears in many problems, such as counting the number of ways to triangulate a convex polygon, counting Dyck paths (paths that never go below the diagonal), or counting binary search trees. The surprising part is that all these different counting problems lead to the same numbers.