Difference between revisions of "Catalan sequence"

(See also: split section to external links)
Line 13: Line 13:
 
=== Solution ===
 
=== Solution ===
  
== See also ==
+
== 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 $C_0 = 1$, $C_1 = 1$, $C_2 = 2$, $C_3 = 5$, .... In general, the $n$th Catalan number is given by the formula $C_n = \frac{1}{n + 1}\binom{2n}{n}$, where $\binom{2n}{n}$ is the $n$th central binomial coefficient.

Introduction

Catalan numbers can be used to find:

  1. The number of ways to arrange $n$ pairs of matching parentheses.
  2. The number of ways a convex polygon of $n+2$ sides can be split into $n$ triangles by $n - 1$ nonintersection diagonals.
  3. The number of rooted binary trees with exactly $n+1$ leaves.

Example

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

Solution

See Also

External Links