Difference between revisions of "Catalan sequence"
m (Catalan number moved to Catalan sequence) |
(terminology changed along with move) |
||
Line 1: | Line 1: | ||
− | The '''Catalan | + | 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 == | == Introduction == | ||
− | Catalan | + | 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 to arrange <math>n</math> pairs of matching parentheses. |
Revision as of 20:35, 8 December 2007
The Catalan sequence is a sequence of positive integers that arise as the solution to a wide variety of combinatorial problems. The first few terms of the Catalan sequence are ,
,
,
, .... In general, the
th term of the Catalan sequence is given by the formula
, where
is the
th central binomial coefficient.
Introduction
The Catalan sequence 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
.