Difference between revisions of "Catalan sequence"
(→See also: split section to external links) |
|||
Line 13: | Line 13: | ||
=== Solution === | === Solution === | ||
− | == See | + | == See Also == |
* [[Combinatorics]] | * [[Combinatorics]] | ||
+ | * [[Fibonacci sequence]] | ||
+ | |||
+ | == External Links== | ||
* [http://www-math.mit.edu/~rstan/ec/catadd.pdf Richard Stanley's Catalan Compendium (.pdf)] | * [http://www-math.mit.edu/~rstan/ec/catadd.pdf Richard Stanley's Catalan Compendium (.pdf)] | ||
* [http://www.research.att.com/~njas/sequences/A000108 Catalan numbers in the OEIS] | * [http://www.research.att.com/~njas/sequences/A000108 Catalan numbers in the OEIS] | ||
[[Category:Combinatorics]] | [[Category:Combinatorics]] |
Revision as of 19:06, 8 December 2007
The Catalan numbers are a sequence of positive integers that arise as the solution to a wide variety of combinatorial problems. The first few Catalan numbers are , , , , .... In general, the th Catalan number is given by the formula , where is the th central binomial coefficient.
Introduction
Catalan numbers can be used to find:
- The number of ways to arrange pairs of matching parentheses.
- The number of ways a convex polygon of sides can be split into triangles by nonintersection diagonals.
- The number of rooted binary trees with exactly leaves.
Example
In how many ways can the product of ordered number be calculated by pairs? For example, the possible ways for are and .