Catalan numbers: C₀=1, C₁=1, C₂=2, C₃=5, C₄=14, C₅=42, ... Formula: Cₙ = C(2n,n)/(n+1). Recurrence: Cₙ = Σ Cᵢ·Cₙ₋₁₋ᵢ. They count: valid parenthesizations, full binary trees with n+1 leaves, triangulations of (n+2)-gons, monotonic lattice paths, and many more.
How to Use
Enter n:
- Input: Non-negative integer
- Output: Cₙ and first n values
- Extra: Counting interpretations
What Cₙ Counts
- Valid arrangements of n pairs of parentheses
- Full binary trees with n+1 leaves
- Triangulations of (n+2)-gon
- Monotonic paths that don't cross diagonal
Growth Rate
Cₙ ~ 4ⁿ/(n^(3/2)·√π). Grows exponentially but slower than 4ⁿ. C₁₀ = 16796, C₂₀ = 6564120420.
Step-by-Step Instructions
- 1Enter a value for n.
- 2View Cₙ.
- 3See first n Catalan numbers.
- 4Explore interpretations.
- 5Check growth rate.