Difference between revisions of "Catalan sequence"
(→See also: split section to external links) |
m (Catalan number moved to Catalan sequence) |
(No difference)
|
Revision as of 20:34, 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
.