Difference between revisions of "Catalan sequence"
(categories) |
|||
| Line 1: | Line 1: | ||
| − | The '''Catalan | + | The '''Catalan numbers''' are a [[sequence]] of [[positive integer]]s that arise as the solution to a wide variety of combinatorial problems. The first few Catalan numbers are <math>C_0 = 1</math>, <math>C_1 = 1</math>, <math>C_2 = 2</math>, <math>C_3 = 5</math>, .... In general, the <math>n</math>th Catalan number is given by the formula <math>C_n = \frac{1}{n + 1}\binom{2n}{n}</math>, where <math>\binom{2n}{n}</math> is the <math>n</math>th [[central binomial coefficient]]. |
== Introduction == | == Introduction == | ||
Catalan numbers can be used to find: | Catalan numbers can be used to find: | ||
| − | # The number of ways to arrange <math>n</math> pairs of matching parentheses | + | # The number of ways to arrange <math>n</math> pairs of matching parentheses. |
| − | # The number of ways a convex polygon of <math>n+2</math> sides can be split into <math>n</math> | + | # The number of ways a [[convex polygon]] of <math>n+2</math> sides can be split into <math>n</math> [[triangle]]s by <math>n - 1</math> nonintersection [[diagonal]]s. |
| − | # The number of rooted binary | + | # The number of [[rooted binary tree]]s with exactly <math>n+1</math> leaves. |
=== Example === | === Example === | ||
| Line 15: | Line 15: | ||
== See also == | == See also == | ||
* [[Combinatorics]] | * [[Combinatorics]] | ||
| − | + | * [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] | ||
[[Category:Combinatorics]] | [[Category:Combinatorics]] | ||
Revision as of 18: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.
Contents
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.
sides can be split into 
nonintersection 
leaves.Example
In how many ways can the product of ordered number be calculated by pairs? For example, the possible ways for 
are 
and 
.
