Catalan number

From TheBestLinks.com

The Catalan numbers form a sequence of natural numbers that occur in various counting problems in combinatorics. The n-th Catalan number is defined by

<math>C_n = \frac{1}{n+1}{2n\choose n} \qquad\mbox{ for }n\ge 0<math>

(see binomial coefficient). The first Catalan numbers (sequence A000108 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000108) in OEIS) for n=0,1,2,3,... are

1, 1, 2, 5, 14, 42, 132, 429, 1430,...

All Catalan numbers are natural numbers because one can verify that

<math>C_n = {2n\choose n} - {2n\choose n-1} \qquad\mbox{ for }n\ge 1.<math>

Table of contents

1 Applications in combinatorics

2 Occurrence in probability theory

3 Recurrence relation and asymptotic expression

4 History

Applications in combinatorics

C_n is equal to the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's. For example, the following are the Dyck words of length 6: XXXYYY, XYXXYY, XYXYXY, XXYYXY, XXYXYY. Accordingly, C₃ = 5. Thinking of X as an open parenthesis and of Y as a closed one, every Dyck word of length 2n can be seen as an expression with n pairs of parentheses correctly placed together: ((())), ()(()), ()()(), (())(), (()()). Dyck words can be naturally represented as certain paths in a grid with n+1 by n+1 vertices connected by vertical and horizontal lines. The paths start in the lower left corner, end in the upper right corner, always move up or right, and never pass above the diagonal. X stands for "move right" and Y stands for "move up".

One can count Dyck words with the following trick due to D. André: focus on those words containing n X's and n Y's that are not Dyck words. In such a word, find the first Y that violates the Dyck condition, and then flip all letters following this Y from Y to X and vice versa. You obtain a word with n + 1 Y's and n − 1 X's, and in fact every word with n + 1 Y's and n − 1 X's can be obtained in this fashion in precisely one way. The number of these words is equal to

<math>{2n\choose n-1}<math>

which is therefore the same as the number of non-Dyck words; the number of Dyck words must then be

<math>{2n\choose n}-{2n\choose n-1}<math>

which is the nth Catalan number C_n.

C_n is also the number of different ways n + 1 factors can be completely parenthesized. For n=3 for example, we have the following 5 different parenthesizations of 4 factors: a(b(cd)), a((bc)d), (ab)(cd), (a(bc))d, ((ab)c)d. Such expressions can be naturally represented as rooted ordered binary trees, so C_n also counts the number of these trees with n + 1 leaves.

C_n is also equal to the number of different ways a polygon with n + 2 sides can be cut into triangles by connecting vertices with straight lines.

If w is a finite sequence of different integers, we define a reordering S(w) of w recursively as follows: write w = unv where n is the largest element in w and u and v are shorter sequences, and set S(w) = S(u)S(v)n, with S being the identity for one-element sequences. A permutation w of {1, ..., n} is called stack-sortable if S(w) = (1, ..., n). The number of stack-sortable permutations of {1, ..., n} is equal to C_n.

C_n is also the number of noncrossing partitions of the set { 1, ..., n }. A fortiori, C_n never exceeds the nth Bell number.

Occurrence in probability theory

The Catalan numbers occur in a simple expression for the moments of the Wigner semicircle distribution, which is important in free probability theory and the theory of random matrices.

Recurrence relation and asymptotic expression

The Catalan numbers satisfy the recurrence relation

<math>C_0 = 1 \qquad \mbox{and} \qquad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}\quad\mbox{for }n\ge 1.<math>

This follows from the fact that every Dyck word w of length ≥ 2 can be written in a unique way in the form

w = Xw₁Yw₂

with (possibly empty) Dyck words w₁ and w₂.

The generating function for the Catalan numbers is defined by

<math>c(x)=\sum_{n=0}^\infty C_n x^n<math>

and using the above recurrence relation we see that

and hence

Asymptotically, the Catalan numbers grow as

in the sense that the quotient of the n-th Catalan number and the expression on the right tends towards 1 for n → ∞. (This can be proved by using Stirling's approximation for n!.)

History

The Catalan sequence was first described in the 18th century by Leonhard Euler, who was interested in the number of different ways of dividing a polygon into triangles. The sequence is named after Eug�ne Charles Catalan, who discovered the connection to parenthesized expressions. The counting trick for Dyck words was found by D. André in 1887.

sl:Catalanovo število

Discussion

Last posted 0 of 0 messages

[no messages posted yet]

>> post message >>

Watch

You can add this article to your own "watchlist" and receive e-mail notification about all changes in this page.

Retrieved from "http://www.thebestlinks.com/Catalan_number.html"