Catalan sequence
From AoPSWiki
(Redirected from Catalan Numbers)
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.
Contents |
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 
.
