Catalan Numbers
Catalan numbers count several recursively balanced structures: correctly nested parentheses, ordered full binary tree shapes, and nonnegative lattice paths with equal up/down steps. Their common recurrence comes from choosing a first balanced component and an independent remainder. This lesson computes Catalan values modulo 1000000007 using DP, avoiding division altogether while explaining the familiar closed formula and its limits.
Prerequisites: Combinations; DP; modular arithmetic.
Build the idea
1. Define the parenthesis problem
Cₙ counts strings with n opening and n closing parentheses whose every prefix has at least as many openings as closings. C₀=1 for the empty string. Merely having equal totals is insufficient: ")(" has balanced totals but an invalid prefix. The corresponding path uses an up-step for opening and down-step for closing, never going below zero.
2. Split at the match of the first opening
A nonempty valid string has the unique form (A)B. If A uses i pairs, B uses n−1−i. Their choices are independent, giving Cᵢ·Cₙ₋₁₋ᵢ for that split. Sum i=0..n−1. The same split represents a root with ordered left and right full-binary subtrees when n counts internal nodes.
3. Derive the closed count by reflection
Among all C(2n,n) up/down sequences, reflect the prefix through the first step below zero for every invalid path. This is a bijection to paths with n+1 up-steps and n−1 down-steps, counted by C(2n,n+1). Subtracting yields C(2n,n)−C(2n,n+1)=C(2n,n)/(n+1). The division is an exact integer identity before any modular reduction.
4. Trace n=3
C₀=1, C₁=1, C₂=2. Then C₃=C₀C₂+C₁C₁+C₂C₀=2+1+2=5. The five strings are ((())), (()()), (())(), ()(()), ()()(). Each has one unambiguous (A)B decomposition; several may share the same split size. The code computes every earlier entry first, reducing after each addition and product.
5. Use the right counting convention
Ordered FULL binary trees with n internal nodes have Catalan count; this is not the number of arbitrary labeled trees. Modular recurrence uses only addition/multiplication and can be adapted to composite moduli with safe arithmetic. A fast prime factorial formula additionally requires valid factorial inverses and division by n+1; do not use it blindly when n is large relative to the prime.
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
// Key idea: 5. Use the right counting convention Ordered FULL binary trees with n internal nodes have
// Catalan count; this is not the number of arbitrary labeled trees.
#include<iostream>
#include<vector>
int main(){
int N;
std::cin>>N;
const long long MOD=1000000007;
std::vector<long long>catalan(N+1,0);
catalan[0]=1;
for(int n=1;n<=N;++n){
for(int left=0;left<n;++left){
catalan[n]=(catalan[n]+catalan[left]*catalan[n-1-left])%MOD;
}
}
std::cout<<catalan[N]<<'\n';
}
Complexity analysis
O(N²) time from summing n split positions for every n≤N; O(N) storage. The program allows 0≤N≤1000. Each reduced-residue product plus one reduced accumulator fits long long. The output is a modular count, not the potentially huge exact Catalan integer.
Example input and output
Read N in 0..1000. Print C_N modulo 1000000007.
Input
3
Output
5
The recurrence combines 2+1+2 possibilities from the three first-component splits.
Practical applications
Use for balanced syntax, noncrossing structures, ordered tree shapes and constrained paths. The DP split principle transfers to many recursive counting tasks. For very large n under a suitable prime, a carefully justified binomial formula may be faster.
Check your understanding
What does C₀=1 represent?
Put it into practice
Enumerate parenthesis strings for n≤5 and compare valid counts with the DP.
Show a hint
Track prefix balance and require the final balance to be zero.