Difference between revisions of "Catalan sequence"
Lemondemon (talk | contribs) |
|||
| Line 2: | Line 2: | ||
== Introduction == | == Introduction == | ||
| + | Catalan numbers 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> triangles | ||
| + | # The number of rooted binary trees with exactly <math>n+1</math> leaves | ||
| + | |||
=== 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>. | ||
Revision as of 18:26, 31 August 2006
The Catalan Numbers are a sequence of numbers that show up in a variety of instances.
Contents
Introduction
Catalan numbers 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 - The number of rooted binary trees with exactly
leaves
sides can be split into 
leavesExample
In how many ways can the product of 
ordered number be calculated by pairs? For example, the possible ways for 
are 
and 
.
