Difference between revisions of "Catalan sequence"
(link) |
|||
| (10 intermediate revisions by 5 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 == | ||
| + | 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 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 [[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 === | ||
In how many ways can the product of <math>n</math> ordered number be calculated by pairs? For example, the possible ways for <math>a\cdot b\cdot c\cdot d</math> are <math>a((bc)d), a(b(cd)), (ab)(cd), ((ab)c)d,</math> and <math>(a(bc))d</math>. | In how many ways can the product of <math>n</math> ordered number be calculated by pairs? For example, the possible ways for <math>a\cdot b\cdot c\cdot d</math> are <math>a((bc)d), a(b(cd)), (ab)(cd), ((ab)c)d,</math> and <math>(a(bc))d</math>. | ||
| Line 7: | 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 14: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.
sides can be split into 
nonintersection 
leaves.
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 
.
