Catalan numbers are the sequence that counts many recursive combinatorics objects, including balanced parentheses, binary trees, and certain lattice paths. The nth Catalan number is \(C_n=\frac{1}{n+1}\binom{2n}{n}\).
Catalan numbers are a sequence of counting numbers in combinatorics that show up whenever a structure can be built by splitting a problem into two smaller parts. The sequence starts 1, 1, 2, 5, 14, 42, and so on, with the first term usually written as .
A standard closed form is . That formula is useful because it turns a hard counting problem into a binomial coefficient calculation. You will also see the same sequence defined recursively as for . That recurrence matches the way many Catalan objects break apart into a left piece and a right piece.
One of the easiest ways to picture Catalan numbers is with balanced parentheses. For example, when there are three pairs of parentheses, there are 5 valid arrangements: , , , is not valid, and so on. The rule is that at every point in the string, you can never have more closing parentheses than opening ones.
The same counting pattern also appears in binary trees. If you count the number of distinct binary tree shapes with internal nodes, you get the th Catalan number. This is why Catalan numbers show up in data structures too, not just in pure counting problems.
Another common model is lattice paths. A Catalan path often means a path from to using only steps right and up, with the path never crossing above the diagonal. That diagonal restriction is what makes the count nontrivial. Without the restriction, you would just be counting all paths, but Catalan numbers count the valid ones.
A common mistake is to think Catalan numbers count any object with two choices at each step. They do not. The objects usually have a very specific noncrossing, well-formed, or recursively split structure. That structure is what makes the recurrence and the binomial formula work.
Catalan numbers keep showing up in combinatorics because they are one of the cleanest examples of recursive counting. If a problem has a “left part plus right part” shape, Catalan numbers are often the answer, or part of the answer.
They matter in two big ways. First, they give you exact counts for well-formed structures like parentheses strings and binary tree shapes. Second, they connect different tools in the course, especially recurrence relations and generating functions. If you can recognize a Catalan structure, you can switch from brute-force listing to a formula or recursion that actually scales.
They also show up in computer science ideas that are built from trees, such as parsing expressions or organizing search trees. That makes them a bridge between abstract counting and concrete data structures. In a problem set, this often means translating a shape or rule into a recursion, then checking whether the answer matches the Catalan sequence.
Keep studying COMBINATORICS Unit 6
Visual cheatsheet
view galleryRecurrence Relations
Catalan numbers are a classic recurrence example because the nth term is built from smaller Catalan counts. When you split a structure into a left and right part, the count often becomes a sum of products. That recursive setup is exactly what recurrence relations are for, so Catalan numbers are a strong test case for recognizing and solving recurrences.
Generating Functions
Catalan numbers have a famous generating function, which is why they come up in the generating functions unit. Instead of counting objects one at a time, you package the sequence into a power series and use algebra to recover the coefficients. This is useful when the recursion is too messy to solve directly.
Binary Trees
Binary tree shapes are one of the most common Catalan objects. If a problem asks how many different binary search tree shapes you can build with a fixed number of nodes, the answer follows the Catalan pattern. The left subtree and right subtree split is what makes the count recursive.
Counting paths in a grid
Some Catalan problems count grid paths that stay on one side of a diagonal. Those paths are easy to describe but harder to count directly, which is why Catalan numbers show up. The restriction is the whole point, since unrestricted paths would be counted by a simple binomial coefficient instead.
A problem set question might ask you to count valid parentheses strings, binary tree shapes, or restricted lattice paths and recognize that the answer is a Catalan number. The move is usually to identify the recursive split first, then write the recurrence or match the pattern to .
If a quiz gives you a list of counts, you may need to spot that 1, 1, 2, 5, 14, 42 is the Catalan sequence and then use the closed form or recurrence to find the next term. In tree problems, draw the left and right substructure before counting. In path problems, pay attention to the restriction, since that is what separates Catalan counts from ordinary binomial counts.
Catalan numbers count recursive combinatorial structures, not just any object with multiple choices.
The closed form is , and the recurrence is .
Balanced parentheses, binary tree shapes, and diagonal-restricted lattice paths are the most common Catalan examples.
The sequence begins 1, 1, 2, 5, 14, 42, which makes it easy to recognize in counting problems.
If a structure splits into a left piece and a right piece, Catalan numbers are often the counting pattern to look for.
Catalan numbers are a sequence that counts many recursively defined objects in Combinatorics. They show up in problems like balanced parentheses, binary trees, and certain grid paths that cannot cross a boundary.
You can use the formula or the recurrence . The formula is fastest when you just need one value, while the recurrence helps when the problem is built from smaller pieces.
A binary tree splits naturally into a left subtree and a right subtree, which matches the Catalan recurrence. Each possible split contributes a product of smaller Catalan counts, so the total number of tree shapes follows the same sequence.
No. Catalan numbers are built from binomial coefficients, but they are not the same thing. The Catalan formula uses and then divides by , which filters the count down to a more restricted class of objects.