Catalan Number
Counts many recursive structures such as balanced parentheses.
Formula
Variables
Example
C_3 = 5
How it works
The Catalan number C_n counts the number of ways to build a balanced recursive object of size n, such as correctly matched parentheses strings, full binary trees, or monotonic lattice paths that stay on one side of a diagonal. The formula works because among all 2n choose n ways to arrange n opening and n closing symbols, exactly the invalid arrangements can be removed by a reflection argument, leaving 1/(n+1) times the central binomial coefficient. This makes Catalan numbers a standard result in counting problems with a built-in “never violate the rule” constraint.
When to use it
Use this when counting structures that must remain properly nested or never cross a boundary, especially in combinatorics, graph theory, and recursive algorithms. It is especially useful for balanced parentheses, binary tree shapes, and Dyck paths.
Worked example, step by step
Find the Catalan number for n = 4. C_4 = (1/(4+1)) * binom(2*4, 4) C_4 = (1/5) * binom(8, 4) C_4 = (1/5) * (8! / (4!4!)) C_4 = (1/5) * (40320 / (24*24)) C_4 = (1/5) * 70 C_4 = 14
Common mistakes to avoid
- Forgetting the division by n+1 and using only the central binomial coefficient
- Using n in the binomial top instead of 2n
- Thinking C_n counts all parenthesis strings with n pairs, rather than only the balanced ones
Did You Know?
Catalan numbers count binary trees, paths, and polygon triangulations.
Share this formula
More in Probability & Combinatorics
View allPermutations
BasicNumber of ordered arrangements of r items from n.
Combinations
BasicNumber of unordered selections of r items from n.
Factorial
BasicProduct of all positive integers up to n.
Permutations with Repetition
BasicOrdered arrangements of r items from n when repetition is allowed.
Permutations of a Multiset
IntermediateArrangements of n items where some are identical.
Classical Probability
BasicProbability of an event with equally likely outcomes.