Catalan numbers
E586576
Catalan numbers are a sequence of natural numbers that count a wide variety of combinatorial structures, such as correctly matched parentheses, binary tree shapes, and lattice path configurations.
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
combinatorial sequence
ⓘ
integer sequence ⓘ |
| asymptoticGrowth | C_n ~ 4^n / (n^{3/2} * sqrt(pi)) ⓘ |
| counts |
number of Dyck paths of semilength n
ⓘ
number of correct bracket sequences of length 2n ⓘ number of full binary tree shapes with n+1 leaves ⓘ number of monotonic lattice paths along grid edges from (0,0) to (n,n) that do not cross above the diagonal y=x ⓘ number of non-crossing partitions of an n-element set ⓘ number of rooted ordered binary trees with n internal nodes ⓘ number of stack-sortable permutations of length n ⓘ number of standard Young tableaux of shape (n,n) ⓘ number of ways to insert parentheses in a product of n+1 factors ⓘ number of ways to triangulate a convex (n+2)-gon ⓘ |
| fieldOfStudy |
combinatorics
ⓘ
enumerative combinatorics ⓘ |
| generalTermFormula |
C_n = (1/(n+1)) * binomial(2n, n)
ⓘ
C_n = (2n)! / ((n+1)! n!) ⓘ C_n = binomial(2n, n) - binomial(2n, n+1) ⓘ |
| generatingFunction | C(x) = (1 - sqrt(1-4x)) / (2x) ⓘ |
| growthType | exponential ⓘ |
| hasEighthTerm | 429 ⓘ |
| hasFifthTerm | 14 ⓘ |
| hasFirstTerm | 1 ⓘ |
| hasFourthTerm | 5 ⓘ |
| hasNinthTerm | 1430 ⓘ |
| hasSecondTerm | 1 ⓘ |
| hasSeventhTerm | 132 ⓘ |
| hasSixthTerm | 42 ⓘ |
| hasTenthTerm | 4862 ⓘ |
| hasThirdTerm | 2 ⓘ |
| indexDomain | n ≥ 0 ⓘ |
| monotonicity | C_n is strictly increasing for n ≥ 1 ⓘ |
| namedAfter | Eugène Charles Catalan NERFINISHED ⓘ |
| nonNegativity | C_n ≥ 0 for all n ≥ 0 ⓘ |
| OEISID | A000108 NERFINISHED ⓘ |
| recurrenceRelation |
C_0 = 1
ⓘ
C_{n+1} = (4n+2)/(n+2) * C_n ⓘ C_{n+1} = sum_{i=0}^{n} C_i C_{n-i} ⓘ |
| relatedConcept |
Dyck paths
NERFINISHED
ⓘ
ballot problem ⓘ binary trees ⓘ non-crossing partitions ⓘ |
| relatedSequence |
Motzkin numbers
NERFINISHED
ⓘ
Schröder numbers NERFINISHED ⓘ |
| valueAtFive | C_5 = 42 ⓘ |
| valueAtFour | C_4 = 14 ⓘ |
| valueAtOne | C_1 = 1 ⓘ |
| valueAtThree | C_3 = 5 ⓘ |
| valueAtTwo | C_2 = 2 ⓘ |
| valueAtZero | C_0 = 1 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.