Statements (51)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
integer sequence
|
| gptkbp:appearsIn |
combinatorics
|
| gptkbp:discoveredBy |
gptkb:Eugène_Charles_Catalan
|
| gptkbp:field |
gptkb:mathematics
combinatorics |
| gptkbp:first_terms |
2
1 132 14 42 5 429 |
| gptkbp:generatingFunction |
C(x) = (1 - sqrt(1-4x)) / (2x)
|
| gptkbp:growthForm |
asymptotically C(n) ~ 4^n / (n^{3/2} sqrt(pi))
|
| https://www.w3.org/2000/01/rdf-schema#label |
Catalan numbers
|
| gptkbp:n-thTermFormula |
C(n) = (2n)! / ((n+1)! n!)
|
| gptkbp:namedAfter |
gptkb:Eugène_Charles_Catalan
|
| gptkbp:numberOfRooms |
number of ways to triangulate a convex polygon with n+2 sides
number of stack-sortable permutations of n elements number of correct bracket sequences of length 2n number of non-crossing partitions of a set number of rooted binary trees with n+1 leaves number of monotonic lattice paths along the edges of a grid that do not cross the diagonal |
| gptkbp:OEIS |
A000108
|
| gptkbp:recurrence |
C(0) = 1, C(n+1) = sum_{i=0}^{n} C(i)C(n-i)
|
| gptkbp:relatedTo |
gptkb:Dyck_paths
gptkb:Schröder_numbers binomial coefficients Motzkin numbers |
| gptkbp:sequence |
non-negative integers
increasing sequence |
| gptkbp:usedIn |
gptkb:geometry
algorithm analysis computer science mathematical puzzles graph theory algebraic structures planar graphs enumerative combinatorics parsing expressions polygon triangulation RNA secondary structure enumeration lattice path enumeration non-crossing handshakes parenthesization problems stack sorting tree enumeration |
| gptkbp:bfsParent |
gptkb:Dyck's_theorem
gptkb:Dyck_language gptkb:Pascal's_Triangle |
| gptkbp:bfsLayer |
6
|