Difference between revisions of "Catalan sequence"
Lemondemon (talk | contribs) |
(link) |
||
(9 intermediate revisions by 4 users not shown) | |||
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. |
− | # The number of ways a convex polygon of <math>n+2</math> sides can be split into <math>n</math> | + | # 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 | + | # 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. | ||
+ | |||
+ | A recursive definition of the Catalan sequence is <math>C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}</math> | ||
=== Example === | === Example === | ||
Line 13: | Line 16: | ||
=== Solution === | === Solution === | ||
− | == See | + | == See Also == |
* [[Combinatorics]] | * [[Combinatorics]] | ||
+ | * [[Fibonacci sequence]] | ||
+ | |||
+ | == External Links== | ||
+ | * [http://www-math.mit.edu/~rstan/ec/catadd.pdf Richard Stanley's Catalan Compendium (.pdf)] | ||
+ | * [http://www.research.att.com/~njas/sequences/A000108 Catalan numbers in the OEIS] | ||
+ | [[Category:Combinatorics]] |
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
.