On this page
In combinatorics, certain sequences appear repeatedly in seemingly unrelated problems. If you have ever tried to count the number of valid ways to arrange parentheses in an algebraic expression, or the number of paths across a city grid that avoid crossing a certain boundary, you have encountered Catalan numbers. They are a fascinating mathematical tool that bridges the gap between geometry and algebra.
What are Catalan numbers?
The Catalan numbers form a sequence of natural numbers that answer a wide variety of complex counting problems. They are famous for how often they show up in discrete mathematics. The first few Catalan numbers for n = 0, 1, 2, 3, 4, and 5 are 1, 1, 2, 5, 14, and 42 (Wikipedia).
The n-th Catalan number is mathematically defined by the exact formula (2n)! / ((n + 1)! n!) (Wikipedia).
Because they rely on factorials and binomial coefficients, Catalan numbers grow very quickly as n increases. The sequence is named after the Belgian mathematician Eugène Charles Catalan, who discovered their connection to parenthesised expressions in the 19th century (Wikipedia). While Euler explored them even earlier to find the number of ways to divide a polygon into triangles, the sequence took Catalan's name.
How do you count balanced brackets?
A classic problem in computer science and mathematics is counting the number of ways to arrange n pairs of parentheses so that they are correctly matched. This means every closing bracket must have a corresponding opening bracket before it. You cannot close a bracket that you have not yet opened.
For n = 3 pairs of brackets, there are exactly 5 valid arrangements (Wikipedia):
((()))
(()())
(())()
()(())
()()()
This result perfectly matches the third Catalan number. You can think of this process sequentially: as you read the text string from left to right, the running count of opening brackets must always be greater than or equal to the running count of closing brackets. If you are practising for competitive engineering or medical exams, you can explore the Fermi Concept Library to see how such logical constraints build the foundation for complex counting, much like calculating arrangements with letters together using the bundle method. Learning to map strings of text into mathematical formulas is an incredibly useful habit.
How do you count grid paths that avoid the diagonal?
The exact same mathematical logic applies to grid routes, which are often called Dyck paths. Imagine you are standing on a square grid of size n × n. You start at the bottom-left corner at the coordinate (0, 0) and aim to reach the top-right corner at (n, n). To make progress, you are only allowed to take steps to the right and steps upward.
The total number of possible paths without any restrictions is simply the number of ways to choose n upward steps out of 2n total steps, calculated using combinations as (2n)! / (n! n!) (Wikipedia).
However, suppose you add a new restrictive rule: the path must never cross above the diagonal line connecting (0, 0) to (n, n). The path is allowed to touch the diagonal, but it cannot step into the upper-left half of the grid. In this scenario, moving right is mathematically identical to opening a bracket, and moving up is identical to closing a bracket. Just as you cannot close more brackets than you have opened, your path cannot take more upward steps than rightward steps at any given point in the journey.
Consequently, the number of valid paths on an n × n grid is exactly the n-th Catalan number, evaluated as (2n)! / ((n + 1)! n!) (Wikipedia).
Where else do Catalan numbers appear?
The beauty of Catalan numbers lies in how they connect different geometric and algebraic ideas. They do not just govern brackets and grid routes. For instance, if you want to divide a convex polygon with n + 2 sides into triangles by drawing non-intersecting diagonals, the number of valid ways to do it is also the n-th Catalan number (Wikipedia).
They also define the number of possible full binary trees with n internal nodes, which is why Catalan numbers are frequently taught in algorithms courses. Understanding these isomorphic connections—where one mathematical structure maps perfectly onto another—is a key skill when tackling tricky permutations or selection problems with at least or at most conditions.
By recognising the underlying pattern across different phrasing, you can quickly turn a time-consuming counting task into a simple arithmetic calculation, a technique you can practice on past exam questions in the Fermi Problem Library.
