Catalan sequence
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.
Example
In how many ways can the product of ordered number be calculated by pairs? For example, the possible ways for
are
and
.