Difference between revisions of "Catalan sequence"
(→Introduction) |
(link) |
||
Line 6: | Line 6: | ||
# 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. | ||
# The number of ways a [[convex polygon]] of <math>n+2</math> sides can be split into <math>n</math> [[triangle]]s by <math>n - 1</math> nonintersection [[diagonal]]s. | # The number of ways a [[convex polygon]] of <math>n+2</math> sides can be split into <math>n</math> [[triangle]]s by <math>n - 1</math> nonintersection [[diagonal]]s. | ||
− | # The number of [[rooted binary tree]]s with exactly <math>n+1</math> leaves. | + | # The number of [[Tree (graph theory)#Rooted Tree|rooted binary tree]]s with exactly <math>n+1</math> leaves. |
# The number of paths with <math>2n</math> steps on a rectangular grid from <math>(0,0)</math> to <math>(n,n)</math> that do not cross above the main diagonal. | # The number of paths with <math>2n</math> steps on a rectangular grid from <math>(0,0)</math> to <math>(n,n)</math> that do not cross above the main diagonal. | ||
Latest revision as of 15:00, 5 July 2024
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.
- The number of paths with
steps on a rectangular grid from
to
that do not cross above the main diagonal.
A recursive definition of the Catalan sequence is
Example
In how many ways can the product of ordered number be calculated by pairs? For example, the possible ways for
are
and
.