# Edit Create an Image Page: Catalan Numbers

You do not have permission to edit this page, for the following reasons:

• The action you have requested is limited to users in one of the groups: Users, dte, math_doctor.

To create an image page, simply complete the form below and then hit the 'Save Page' button at the bottom of the form. As you complete the form, remember that one of the main goals of the Math Images Project is to provide explanations of the images on our site at various levels, so that everyone can understand some of the math behind the images. Try to complete the form as fully as possible, but remember that other users will have the opportunity to add more information to your image pages in the future. Also, please note that by contributing to the Math Images Project, you agree to comply to the guidelines as stated in our general disclaimer.

As always, thank you for your contributions! --The Math Images Project

If you need help filling out this page, please consult our Help sections: Want to Contribute and Math Resources.

Note: * Indicates a required field.

Please note: When you are filling in the below explanations, you should feel free to use standard wikitext.

Image Title*: This greedy little worm wants to eat the poor apple. He can only go to the east and to the north in this 8 by 8 grid. Since there is stain on the grid, he cannot pass above the diagonal connecting the worm and the apple. How many ways could he get there? The main image shows only one way of reaching the apple. :This is a very famous grid problem in combinatorics, which could be solved by Catalan numbers. Catalan numbers grow rapidly. The first several Catalan numbers are listed as following. {{{!}}class="wikitable" style="margin: 1em auto 1em auto;" border="1" cellspacing="3" cellpadding="10" {{!}}n{{!}}{{!}}0{{!}}{{!}}1{{!}}{{!}}2{{!}}{{!}}3{{!}}{{!}}4{{!}}{{!}}
5
{{!}}{{!}}
6
{{!}}{{!}}
7
{{!}}{{!}}
8
{{!}}{{!}}
9
{{!}}{{!}}
10
{{!}}{{!}}
11
{{!}}{{!}}
12
{{!}}{{!}}
13
{{!}}{{!}}
14
{{!}}{{!}}
15
{{!}}{{!}}
16
{{!}}- {{!}}C_n{{!}}{{!}}1{{!}}{{!}}1{{!}}{{!}}2{{!}}{{!}}5{{!}}{{!}}14{{!}}{{!}}42{{!}}{{!}}132{{!}}{{!}}429{{!}}{{!}}1430{{!}}{{!}}4862{{!}}{{!}}16796{{!}}{{!}}58786{{!}}{{!}}208012{{!}}{{!}}742900{{!}}{{!}}2674440{{!}}{{!}}9694845{{!}}{{!}}35357670 {{!}}} More explicit and detailed description is under ''More Mathematical Explanation'' section. =Why It's Interesting= ==History== Image:Eugene_charles_catalan.jpeg ==Basic Description== The ''n''th Catalan number is defined as :
C_{n} = \frac{1}{n+1} \cdot \begin{pmatrix} 2n \\ n \end{pmatrix} = \frac{(2n)!}{n!(n+1)!}, \qquad n = 0, 1, 2, ...
The binomial coefficient, \tbinom{n}{r}, pronounced as ''n choose r,'' represents the number of possible combinations of r objects from a collection of n objects:
\binom{n}{r} = \frac{n!}{r! (n-r)!} .
Therefore,
\begin{pmatrix} 2n \\ n \end{pmatrix} = \frac{(2n)!}{n! (2n -n)!} = \frac{2n \cdot (2n -1) \cdot (2n -2) \cdots (2n - n + 1)}{n!}
Example: \begin{pmatrix} 11 \\ 4 \end{pmatrix} = \frac{11!}{4!~(11-4)!} = \frac{11 \times 10 \times 9 \times 8}{4 \times 3 \times 2 \times 1}. Catalan numbers could be described in various but equivalent ways. If you transform the first formula just a little bit, you will get another useful formula of Catalan numbers. :
C_{n} = \begin{pmatrix} 2n \\ n \end{pmatrix} - \begin{pmatrix} 2n \\ n + 1 \end{pmatrix}, \qquad n = 0, 1, 2, ...
See ''Proof'' in the next section to know more about its proof. Note that \tbinom{2n}{n} , \tbinom{2n}{n+1} \in \mathbb{N} and \tbinom{2n}{n} > \tbinom{2n}{n + 1} . Therefore, C_n is the difference between two positive, natural numbers, which could be extended to [[Catalan Numbers#Pascal's Triangle|Pascal's Triangle]]. ==Proofs== * '''Prove C_{n} = \begin{pmatrix} 2n \\ n \end{pmatrix} - \begin{pmatrix} 2n \\ n + 1 \end{pmatrix}, n = 0, 1, 2, ... is the formula for Catalan sequence. ''' :1. Check if it is true when n = 0. :
C_{0} = \begin{pmatrix} 2(0) \\ 0 \end{pmatrix} - \begin{pmatrix} 2(0) \\ 0 + 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} - \begin{pmatrix} 0 \\ 1 \end{pmatrix} = 1 - 0 = 1 .
:2. Show it is true when n \geqslant 1. :
C_n = \frac{1}{n+1} {2n \choose n} = {2n \choose n} - \frac{n}{n+1} {2n \choose n} = \frac{2n!}{n!n!} - \frac{n}{n+1} \frac{2n!}{n!n!} = \frac{2n!}{n!n!} - \frac{2n!}{(n+1)!(n-1)!} = {2n \choose n} - {2n \choose n+1}. \blacksquare
*'''Prove this recurrence relation: C_{n+1} = \frac{2(2n+1)}{n+2} C_n for n=0, 1, 2, ... . ''' :Recall that
C_n = \frac{(2n)!}{n!(n+1)!}, \qquad n = 0, 1, 2, \cdots.
:Therefore, we have
C_{n+1} = \frac{(2n+2)!}{(n+1)!(n+2)!}, \qquad n = 0, 1, 2, \cdots.
:Take the ratio of C_{n+1} to C_n: :
\frac{C_{n+1}}{C_n} = \frac{ \frac{(2n+2)!}{(n+1)!(n+2)!}}{ \frac{(2n)!}{n!(n+1)!}} = \frac{ (2n+2)! n! (n+1)!} {(n+1)! (n+2)! (2n)!} = \frac{(2n+2) (2n+1)}{(n+1) (n+2)} = \frac{ 2(2n+1)}{(n+2)}.
:Thus, :
C_{n+1} = \frac{ 2( 2n+1)}{(n+2)} C_n
: for all nonnegative values of n. \blacksquare == Recursive Definition== We have seen various kinds of applications of Catalan numbers so far: "Stacking Coins," "Balanced Parentheses," "Mountain Ranges," "Polygon Triangulation," "Binary Trees," "Binary Paths," "Permutation," "Young Diagrams" and "Posets." In fact, all the sequences are equivalent, and we will show that there is a common formula that counts them all.
C_0 =1, C_{n+1} = \sum_{i=0}^n C_i C_{n-i} \text{ for } n\ge 1 .
In the application Balanced Parenthese, it is already known that for each open parenthesis, there is a close parenthesis. Now, let's try to find a pattern in these paired parentheses with example ''n'' = 3:
( (( )) ) - ( ( )( ) ) - (( )) ( ) - ( ) (( )) - ( )( )( ) .
The "pattern" is that we can always separate them in two collections. For example, we can separate the set "(( )) ( )" into: "(( ))" and "( )." We name them collection A and collection B, either of which is able to contain zero pairs of parentheses. Similarly, ( (( )) ) could be separated into " ( (( )) ) " and nothing. For ( ( )( ) ) , we treat it as a whole and put it in collection A, so B is, again, empty. What about ( )( )( ) ? At first glance, we see three pairs of parentheses, but we have only two collections. We could choose to put the first two pairs of parentheses in collection A and the last pair should be in B, or put two in collection B and only one in A. This is exactly the same and we do not want to count them twice, thus there is a need for a regulation in order to avoid the repetitiveness. Since n is no less than 1 in the recurrence definition mentioned above, it is certain that there is at least a pair of parentheses, and we will fix it in collection A. Thus, the simplest form where ''n'' = 1 is:
and this is our base form. For values of n that are greater than 1, we simply ''add'' more pairs of parentheses ''inside'' the fixed black parenthese to collection A, and place the rest in collection B. In this way, both collection A and B are able to contain up to ''n'' - 1 pairs of parentheses (the black parentheses in the base form does not count as one of them). If collection A contains ''k'' pairs, then it is not hard to find that there are ''n - ( k + 1)'' pairs in collection B. What is the purpose of separating the parentheses into two collections? Well, we want to two collections A and B for the purpose of counting the combinations of parentheses systematically, that is, if A has 0 pairs, B has ''n'' - 1 pairs; A 1 pair, and B ''n '' - 2 pairs; A 2 pairs, and B ''n'' - 3 pairs, etc. {{{!}}class="wikitable" style="margin: 1em auto 1em auto;" border="1" cellspacing="3" cellpadding="10" {{!}}
'''Number of Pairs'''
'''Contained in A'''
{{!}}{{!}}
'''Number of Pairs'''
'''Contained in B'''
{{!}}{{!}}
'''Illustration'''
{{!}}{{!}}
'''Number of Solutions'''
'''for Each Situation'''
{{!}}- {{!}}
0
{{!}}{{!}}
n - 1
{{!}}{{!}}
\Big( \quad \Big) {\color{Blue}( \cdots ) \cdots}
{{!}}{{!}}
C_0 C_{n-1}
{{!}}- {{!}}
1
{{!}}{{!}}
n - 2
{{!}}{{!}}
\Big( \ {\color{Maroon} ( \ )} \ \Big) {\color{Blue}( \cdots ) \cdots}
{{!}}{{!}}
C_1 C_{n-2}
{{!}}- {{!}}
\vdots
{{!}}{{!}}
\vdots
{{!}}{{!}}
\vdots
{{!}}{{!}}
\vdots
{{!}}- {{!}}
n - 1
{{!}}{{!}}
0
{{!}}{{!}}
\Big( \ {\color{Maroon} ( ( \cdots ) )( \cdots ) \cdots} \ \Big) {\color{White} ABCDEFGH}