Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Catalan sequence"
(→‎Introduction)
 
(3 intermediate revisions by 2 users not shown)
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 ==
 
== 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.
 
# 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 [[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 ===

Latest revision as of 02:47, 19 December 2018

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:

  1. The number of ways to arrange $n$ pairs of matching parentheses.
  2. The number of ways a convex polygon of $n+2$ sides can be split into $n$ triangles by $n - 1$ nonintersection diagonals.
  3. The number of rooted binary trees with exactly $n+1$ leaves.
  4. The number of paths with $2n$ steps on a rectangular grid from $(0,0)$ to $(n,n)$ that do not cross above the main diagonal.

A recursive definition of the Catalan sequence is $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$

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

See Also

External Links

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Catalan_sequence&oldid=99537"