Difference between revisions of "Catalan sequence"

Revision as of 20:35, 8 December 2007

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 $C_0 = 1$ , $C_1 = 1$ , $C_2 = 2$ , $C_3 = 5$ , .... In general, the $n$ th term of the Catalan sequence is given by the formula $C_n = \frac{1}{n + 1}\binom{2n}{n}$ , where $\binom{2n}{n}$ is the $n$ th central binomial coefficient.

Introduction

The Catalan sequence can be used to find:

The number of ways to arrange $n$ pairs of matching parentheses.
The number of ways a convex polygon of $n+2$ sides can be split into $n$ triangles by $n - 1$ nonintersection diagonals.
The number of rooted binary trees with exactly $n+1$ leaves.

Example

In how many ways can the product of $n$ ordered number be calculated by pairs? For example, the possible ways for $a\cdot b\cdot c\cdot d$ are $a((bc)d), a(b(cd)), (ab)(cd), ((ab)c)d,$ and $(a(bc))d$ .

Solution

External Links

@@ Line 1: / Line 1: @@
-The '''Catalan numbers''' are a [[sequence]] of [[positive integer]]s that arise as the solution to a wide variety of combinatorial problems.  The first few Catalan numbers 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 Catalan number 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]].
+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 ==
-Catalan numbers can be used to find:
+The Catalan sequence can be used to find:
 # The number of ways to arrange <math>n</math> pairs of matching parentheses.

Page

Toolbox

Search