Massive Math Stuff: Catalan number - Wikipedia, the free encyclopedia

Sunday, July 20, 2014

The nth Catalan number is given directly in terms of binomial coefficients by

C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\mbox{ for }n\ge 0.

The first Catalan numbers for n = 0, 1, 2, 3, … are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796

Using Binomial Coefficient

C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,

$C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0;$

Application
C_n is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways ofassociating n applications of a binary operator).

C_n is the number of different ways a convex polygon with n + 2 sides can be cut into triangles by connecting vertices withstraight lines

http://mathforum.org/advanced/robertd/catalan.html

the number of ways a polygon with n+2 sides can be cut into n triangles
the number of ways to use n rectangles to tile a stairstep shape (1, 2, ..., n−1, n).
the number of ways in which parentheses can be placed in a sequence of numbers to be multiplied, two at a time
the number of planar binary trees with n+1 leaves
the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal

The

nth Catalan number counts the number of different ways

n pairs of brackets can be correctly matched.

E.g. for

n=3 there are these distinct correctly matched pairs of brackets:

((())) () (()) () () () (()) () (() ())

(Etc.)

Properties

C0=1 and Cn+1=∑ni=0CiCn−i for n≥0

Total number of possible Binary Search Trees with n keys
http://www.geeksforgeeks.org/g-fact-18/
Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!

Read full article from Catalan number - Wikipedia, the free encyclopedia

Massive Math Stuff