View source

The '''Catalan sequence''' is a [[sequence]] of [[positive integer]]s that arise as the solution to a wide variety of combinatorial problems.  The first few terms of the Catalan sequence 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 term of the Catalan sequence 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 ==
The Catalan sequence can be used to find:

# 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> [[triangle]]s by <math>n - 1</math> nonintersection [[diagonal]]s.
# The number of [[rooted binary tree]]s with exactly <math>n+1</math> leaves.

=== Example ===
In how many ways can the product of <math>n</math> ordered number be calculated by pairs?  For example, the possible ways for <math>a\cdot b\cdot c\cdot d</math> are <math>a((bc)d), a(b(cd)), (ab)(cd), ((ab)c)d,</math> and <math>(a(bc))d</math>.

=== Solution ===

== See Also ==
* [[Combinatorics]]
* [[Fibonacci sequence]] 

== External Links==
* [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]]