Catalan Numbers Calculator
Calculate Catalan numbers with applications in combinatorics and binary trees
Enter a non-negative integer (0 to 30)
Risultati
Inserisci i valori e clicca Calcola per vedere il risultato.
Theory & Formula
Catalan Numbers
Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. The nth Catalan number counts the number of expressions containing n pairs of parentheses which are correctly matched.
Formulas
\(C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\)
\(C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}\)
The first formula uses binomial coefficients, while the second is a recursive definition
Applications
- Number of ways to correctly match n pairs of parentheses
- Number of different binary trees with n+1 leaves
- Number of paths from (0,0) to (n,n) that don't cross the diagonal
- Number of ways to triangulate a convex polygon with n+2 sides
- Number of ways to connect 2n points on a circle with n non-crossing chords
First Catalan Numbers
The first few Catalan numbers are: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796...
Example
Calculate C₃ (number of ways to match 3 pairs of parentheses):
\(C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \cdot 20 = 5\)