Difference between revisions of "Catalan Numbers"
PhoebeJiang (talk | contribs) |
PhoebeJiang (talk | contribs) |
||
(39 intermediate revisions by the same user not shown) | |||
Line 7: | Line 7: | ||
|ImageDescElem= | |ImageDescElem= | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Line 48: | Line 16: | ||
{{!}}<math>C_n</math>{{!}}{{!}}1{{!}}{{!}}1{{!}}{{!}}2{{!}}{{!}}5{{!}}{{!}}14{{!}}{{!}}42{{!}}{{!}}132{{!}}{{!}}429{{!}}{{!}}1430{{!}}{{!}}4862{{!}}{{!}}16796{{!}}{{!}}58786{{!}}{{!}}208012{{!}}{{!}}742900{{!}}{{!}}2674440{{!}}{{!}}9694845{{!}}{{!}}35357670 | {{!}}<math>C_n</math>{{!}}{{!}}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= | =Why It's Interesting= | ||
− | |||
+ | ==History== | ||
− | |||
− | + | <gallery widths="200px" heights="220px"> | |
− | + | Image:Eugene_charles_catalan.jpeg | Eugène Charles Catalan | |
+ | Image:Euler.gif| Leonhard Euler | ||
+ | Image:3171225767658715.gif| Minggatu | ||
+ | </gallery> | ||
+ | The first person who discovered Catalan numbers was Leonhard Euler. In 1751, Euler discussed the number of ways to cut a polygon with lines into triangles without any of the lines intersecting in his letter to Christian Goldbach, a German mathematician. | ||
− | + | It was a French and Belgian mathematician, Eugène Charles Catalan, who described this number sequence in a well-defined formula, and introduced this subject to solve parentheses expressions. | |
− | + | Before Catalan, a Mongolian mathematician Minggatu was the first person in China who established and applied what was later to be known as Catalan numbers. In the 1730s, he brought forward this sequence of numbers and continued using it when he was trying to express series expansions of sin(ma), where m = 2, 3, 4, 5, 10, 100, 1000, and10000. This topic was included in his book, ''Ge Yuan Mi Lu Jie Fa'' (The Quick Method for Obtaining the Precise Ratio of Division of a Circle). | |
− | |||
==Applications== | ==Applications== | ||
Line 85: | Line 58: | ||
===Balanced Parentheses=== | ===Balanced Parentheses=== | ||
− | *We want to group a string of parentheses. Each open parenthesis must have a matching closed parenthesis. Therefore, "(( )( ))" is valid, but ")( )) ((" | + | *We want to group a string of parentheses. Each open parenthesis must have a matching closed parenthesis. Therefore, "(( )( ))" is valid, but ")( )) ((" and "( ))( ) (" are not. How many groupings are there to group n pairs of parentheses? |
:'''n:''' The number of pairs of parentheses. | :'''n:''' The number of pairs of parentheses. | ||
Line 102: | Line 75: | ||
− | * | + | *Many other applications are equivalent to balanced parentheses, and here is one example. If we want to connect 2n dots lying on a horizontal line in the plane with n nonintersecting arcs, the solution is also the Catalan sequence. Each arc connecting the two dots is equivalent to a pair of parentheses, with the left dot equivalent to an open parenthesis and the right dot equivalent to a closed parenthesis. |
− | |||
− | |||
[[Image:ConnectingDots.jpg|center|450px]] | [[Image:ConnectingDots.jpg|center|450px]] | ||
Line 126: | Line 97: | ||
{{!}}} | {{!}}} | ||
− | *Note that a pair of strokes and a pair of parentheses are equivalent: upstrokes are equivalent to open parentheses, and downstrokes are equivalent to closed parentheses. The fact that one pair of parentheses are inside another pair corresponds to that one pair of strokes are on top of another pair, forming the shape of mountain ranges. | + | *Note that a pair of strokes and a pair of parentheses are equivalent: upstrokes are equivalent to open parentheses, and downstrokes are equivalent to closed parentheses. The fact that one pair of parentheses are inside another pair corresponds to that one pair of strokes are on top of another pair, thus forming the shape of mountain ranges. |
===Polygon Triangulation=== | ===Polygon Triangulation=== | ||
− | *We want to cut <balloon title="The vertices of a convex polygon point ''outward'' towards the center of the polygon. Opposite to concave polygons, convex polygons satisfy the following two properties: each interior angle is less than or equal to 180 degrees; and each line segment connecting two of the vertices must remain inside the boundary of the polygon.">convex polygons</balloon> into triangles by connecting the vertices with straight, non-intersecting lines. How many different ways are there for a polygon with n+2 sides? This is the application | + | *We want to cut <balloon title="The vertices of a convex polygon in the plane point ''outward'' towards the center of the polygon. Opposite to concave polygons, convex polygons satisfy the following two properties: each interior angle is less than or equal to 180 degrees; and each line segment connecting two of the vertices must remain inside the boundary of the polygon.">convex polygons</balloon> into triangles by connecting the vertices with straight, non-intersecting lines. How many different ways are there for a polygon with n+2 sides? This is the application Euler was interested in. |
− | :'''n:''' The number of sides of the polygon. | + | :'''n:''' The number of sides of the polygon - 2. |
:'''Solution:''' <math>C_n</math> | :'''Solution:''' <math>C_n</math> | ||
Line 140: | Line 111: | ||
[[Image:Polygons 40.jpg|600px|center]] | [[Image:Polygons 40.jpg|600px|center]] | ||
− | :''Note that a 2-sided polygon is set to be triangulated in exactly one way, do nothing, | + | :''Note that a 2-sided polygon is set to be triangulated in exactly one way, do nothing, so it follows'' <math>C_0 = 1 </math>. |
===Binary Trees=== | ===Binary Trees=== | ||
− | *How many <balloon title="A full binary tree is a rooted tree where each internal node has exactly two lines going up or zero lines. ">full binary trees</balloon> there are in order to have n <balloon title="The nodes that connect | + | *How many <balloon title="A full binary tree is a rooted tree where each internal node has exactly two lines going up or zero lines. ">full binary trees</balloon> there are in order to have n <balloon title="The nodes that connect other nodes above are internal nodes.">internal nodes</balloon>? |
− | :'''n:''' The number of internal nodes on | + | :'''n:''' The number of internal nodes on full binary trees. |
:'''Solutioin:'''<math>C_n</math>. | :'''Solutioin:'''<math>C_n</math>. | ||
Line 172: | Line 143: | ||
===Binary Paths=== | ===Binary Paths=== | ||
− | *In a n × n grid, we are going to joint the lower left point and the upper right point by a path. We are only allowed to go to the right or upwards for each unit, and cannot pass above the diagonal connecting | + | *In a n × n grid, we are going to joint the lower left point A and the upper right point B by a path. We are only allowed to go to the right or upwards for each unit, and cannot pass above the diagonal connecting A and B. |
:'''n:''' The number of paths described above. | :'''n:''' The number of paths described above. | ||
− | :'''Solution:''' <math>C_n</math>. Thus, the answer to the main image is <math>C_8</math>. | + | :'''Solution:''' <math>C_n</math>. (Thus, the answer to the main image is <math>C_8</math>.) |
− | [[image:Binary Paths 120.jpg| | + | :[[image:Binary Paths 120.jpg|300px]] |
− | [[image:Binary_Paths_30.jpg|450px]] | + | :[[image:Binary_Paths_30.jpg|450px]] |
[[Image:Dyck_Path.jpg|300px|right|thumb| Figure-1 An example of Dyck Path.]] | [[Image:Dyck_Path.jpg|300px|right|thumb| Figure-1 An example of Dyck Path.]] | ||
− | [[image:Binary_Paths_400.jpg|550px]] | + | :[[image:Binary_Paths_400.jpg|550px]] |
:'''Facts:''' | :'''Facts:''' | ||
Line 189: | Line 160: | ||
:1. Did you find out that these kind of paths look a lot like mountain ranges if you rotate them counterclockwise about origin until the diagonal is horizontal? | :1. Did you find out that these kind of paths look a lot like mountain ranges if you rotate them counterclockwise about origin until the diagonal is horizontal? | ||
− | :2. Did you notice that, whatever value n is, the first step is alway to the east and the last step is always to the north? | + | :2. Did you notice that, whatever value n is, the first step is alway to the east and the last step is always to the north? It is because we cannot pass above the diagonal. |
Line 205: | Line 176: | ||
===Permutations=== | ===Permutations=== | ||
− | *A permutation of {1, 2, ... , n} is an rearrangement of the n numbers. For example, the permutation of {1, 2, 3} includes 6 terms: (1, 2, 3), (1, 3, 2), (2, 1, 3,), (2, 3, 1), (3, 1, 2), (3, 2, 1). 123 | + | *A permutation of {1, 2, ... , n} is an rearrangement of the n numbers. For example, the permutation of {1, 2, 3} includes 6 terms: (1, 2, 3), (1, 3, 2), (2, 1, 3,), (2, 3, 1), (3, 1, 2), (3, 2, 1). 123-avoiding permutation means to avoid an increasing subsequence of 3 terms (the 3 terms do not have to be consecutive). Therefore, we should avoid (1, 2, 3) for n=3. Take n=4 as another example, (4, 3, 1, 2) is valid, but (4, 1, 2, 3) is not valid because of the subsequence 123, and neither is (2, 3, 1, 4) because of 234. |
:'''n:''' The number of permutations that avoid 123. | :'''n:''' The number of permutations that avoid 123. | ||
Line 222: | Line 193: | ||
{{!}}} | {{!}}} | ||
− | :''Note that 123 | + | :''Note that 123-avoiding permutation only avoids an increasing subsequence of '''three''' terms, regardless of the value of n. Therefore, (1,2), (2,1) are valid although they are increasing subsequences as well.'' |
− | *Similarly, there is a 321 avoiding permutation, which avoids a decreasing subsequence of 3 terms. Take ''n'' = 3 as an example, we will then have (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2). | + | *Similarly, there is a 321-avoiding permutation of [n], which avoids a decreasing subsequence of $3$ terms. Take ''n'' = 3 as an example, we will then have (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2). And a permutation of [n] is called 132-avoiding, ``if it does not have three entries a < b < c so that a is the leftmost of them and b is the rightmost of them'' <ref name="Bona">Bona, Miklos. A self-dual poset on objects counted by the Catalan numbers. Schol of Mathe- matics, Institute of Advanced Study. November 10, 1998. </ref>. |
− | * Catalan numbers count <u>shuﬄes of the permutation</u> <math>1,2, \cdots, n</math> with itself, i.e., permutations of the multiset <math>\left \{ 1^2, 2^2, \cdots , n^2 \right \}</math> which are a union of two disjoint subsequences <math>1,2, \cdots, n </math>. | + | * Catalan numbers count <u>shuﬄes of the permutation</u> <math>1,2, \cdots, n</math> with itself, i.e., permutations of the multiset <math>\left \{ 1^2, 2^2, \cdots , n^2 \right \}</math> which are a union of two disjoint subsequences <math>1,2, \cdots, n </math>. On top of this, there should be <u>no weakly decreasing subsequence of length three </u>. <ref name = "Catalan Addendum ">Stanley, Richard P. ''Catalan Addendum''. MIT Mathematics. Version of 22 October 2011. (No.t^6) Retrieved from Richard Stanley's home page http://www-math.mit.edu/~rstan/ec/.</ref> |
:''Explanations.'' A shuffle of <math>1, 2, \cdots, n </math> and itself <math>1, 2, \cdots, n </math> is obtained by intermixing the letters in each string of numbers, while the letters in each string must stay in the original order. For example, a shuffle of <font color=orange>123</font> and <font color=forestgreen>456</font> could be: <font color=orange>12</font><font color=forestgreen>45</font><font color=orange>3</font><font color=forestgreen>6 </font>. No weakly decreasing of length three means that the subsequence either is strictly increasing or has at most two equal entries not followed by a decrease. For example, <font color=orange>12</font><font color=forestgreen>12</font>'''33''' is valid (because it has only two equal entries instead of three with no decrease followed), but <font color=orange>1</font><font color=forestgreen>1</font><font color=orange>2</font>'''332'''is not (because there is a decrease, 2, followed after 33). | :''Explanations.'' A shuffle of <math>1, 2, \cdots, n </math> and itself <math>1, 2, \cdots, n </math> is obtained by intermixing the letters in each string of numbers, while the letters in each string must stay in the original order. For example, a shuffle of <font color=orange>123</font> and <font color=forestgreen>456</font> could be: <font color=orange>12</font><font color=forestgreen>45</font><font color=orange>3</font><font color=forestgreen>6 </font>. No weakly decreasing of length three means that the subsequence either is strictly increasing or has at most two equal entries not followed by a decrease. For example, <font color=orange>12</font><font color=forestgreen>12</font>'''33''' is valid (because it has only two equal entries instead of three with no decrease followed), but <font color=orange>1</font><font color=forestgreen>1</font><font color=orange>2</font>'''332'''is not (because there is a decrease, 2, followed after 33). | ||
− | :Back to the application, let's see an example of ''n'' = 3 | + | :Back to the application, let's see an example of ''n'' = 3, where we want to know the number of shuffles of permutations of <font color=orange> 1, 2, 3 </font> with <font color=forestgreen> 1, 2, 3</font>. It turns out that there are 5 distinct shuffles: |
<center> 112233 112323 121233 121323 123123.</center> | <center> 112233 112323 121233 121323 123123.</center> | ||
Line 246: | Line 217: | ||
:a) these integers 1, 2, 3, ... , n are in increasing order when they ''first'' occur, and | :a) these integers 1, 2, 3, ... , n are in increasing order when they ''first'' occur, and | ||
− | :b) there is no form like <math>\alpha\beta\alpha\beta \cdots</math>. | + | :b) there is no form like <math>\alpha\beta\alpha\beta \cdots</math>, where the integers <math>\alpha, \beta, \cdots </math> do not have to be consecutive. |
− | :For example, '''1212''' and '''1'''<font grey>22</font>'''313''' are not valid. | + | :For example, '''1212''' and '''1'''<font grey>22</font>'''313''' are not valid. Here are the solutions where ''n'' = 3: |
<center>112233, 112332, 122331, 122133, 123321. </center> | <center>112233, 112332, 122331, 122133, 123321. </center> | ||
Line 258: | Line 229: | ||
[[image: Partition_4.jpg|530px|thumb|left| Figure-2 Partition of 4.]] | [[image: Partition_4.jpg|530px|thumb|left| Figure-2 Partition of 4.]] | ||
− | In combinatorics, ''' | + | In combinatorics, '''partition''' of a positive integer ''n'' is an expression of rewriting ''n'' as a sum of positives integers, where the summands do not differ in orders. The sum would be called composition if order matters. Take ''n''=4 as an example, there are 5 ways to partition 4: 4, 3+1, 2+2, 2+1+1, 1+1+1+1. Remember, the ordering of the integers does not matter, i.e. 1+1+2, 1+2+1, 2+1+1 are equivalent partitions. |
− | Partitions could be visualized in explicit graphs, and the most | + | Partitions could be visualized in explicit graphs, and the most commonly used one is called '''Young diagrams'''. Again, take ''n'' = 4 and ''n'' = 5 as two examples for better understanding. Young diagrams of partition 4 and 5 are shown in Figure-2 and Figure-3. |
[[Image: Partition_5.jpg|520px|thumb|right| Figure-3 Partition of 5.]] | [[Image: Partition_5.jpg|520px|thumb|right| Figure-3 Partition of 5.]] | ||
+ | *Young diagrams that <u>fit</u> in the <u>shape (''n'' - 1, ''n'' - 2, ... , 1)</u> follow Catalan sequence <ref name = "Enumerative Combinatorics">Stanley, Richard P. ''Enumerative Combinatorics'', vol.1 and vol.2. Cambridge University Press. New York/Cambridge. 1999.</ref>. | ||
− | + | :''Explanations.'' The shape (''n'' - 1, ''n'' - 2, ... , 1) is a Young diagram that looks like a upside down staircase. Its top stair consists of ''n'' - 1 blocks, next stair ''n'' - 2 blocks, and so on until the last stair has only 1 block. By "fit," we mean that we try to find Young diagrams that could be a part of the shape (''n'' - 1, ''n'' - 2, ... , 1) or the entire shape. | |
− | : | + | ::[[Image: Young2.jpg|480px|left]] |
− | : | + | :In this image above, the last figure is the shape (2, 1) where ''n'' = 3. Each of the other four figures, including the empty set, could be a part of the shape. Add the original shape, then we have five solutions for shape (2,1) in total. |
Line 281: | Line 253: | ||
− | '''Hasse diagram''' is used to represent a finite poset. Each element in the poset is a vertex in Hasse diagram. The transitive relation in the poset is represented by lines going up from one vertex to another in Hasse diagram. The lines could cross each other but cannot touch other vertex before it reaches the endpoint. It is the | + | '''Hasse diagram''' is used to represent a finite poset. Each element in the poset is a vertex in Hasse diagram. The transitive relation in the poset is represented by lines going up from one vertex to another in Hasse diagram. The lines could cross each other but cannot touch other vertex before it reaches the endpoint. It is the line segments and labeled vertices in the diagram that illustrates the partial order of a set. See Figure-4, -5, -6 for several examples of Hasse diagram. As you can see, the element in the poset is any object; it could be a set, a diagram or a number. |
− | <gallery widths="300px" heights=" | + | <gallery widths="300px" heights="220px"> |
− | Image: | + | Image:Hasse5.jpg| Figure-4 Hasse diagram of a 3-element set. |
− | Image:Hasse3.jpg| | + | Image:Hasse3.jpg| Figure-5 Hasse diagram of Young diagrams. |
− | Image:Hasse2.jpg| | + | Image:Hasse2.jpg| Figure-6 Hasse diagram of the poset 2 × 4. |
</gallery> | </gallery> | ||
− | How do Hasse diagrams embody the 3 definitions of posets? In example 1 | + | How do Hasse diagrams embody the 3 definitions of posets? In Figure 4, |
+ | |||
+ | #Each element in the diagram reflects itself, i.e., the set {a} is less or equal to itself {a}. This shows reflexivity. | ||
+ | #Since set {a} is less or equal to {a} and {a} is less or equal to {a}, then {a} = {a}. This symmetry does not work between, for example {a} and {b}, because {a} and {b} are two different, nonsymmetric sets. This is the idea of antisymmetry. | ||
+ | #Since the empty set is less or equal to set {a}, and set {a} is less or equal to set {a, b}, the empty set is less or equal to {a, b}. In the diagram, the three sets are connected with 2 line segments. This shows that if we can follow the lines going from the bottom element up to the top one, then all the elements on the way obey transitivity. Likewise, we can tell that {b} is less or equal to {a, b, c} according to the diagram. | ||
+ | |||
+ | |||
+ | *<u>Linear extensions</u> of <u>the poset '''2 × ''n'' '''</u> follow Catalan sequence <ref name = "Enumerative Combinatorics">Stanley, Richard P. ''Enumerative Combinatorics'', vol.1 and vol.2. Cambridge University Press. New York/Cambridge. 1999.</ref> (See Figure 7). | ||
− | + | [[Image:Poset1.jpg|150px|thumb|center|Figure-7 This is the Hasse diagram of the poset '''2 × ''n'' '''.]] | |
− | |||
− | |||
− | [[Image: | + | :''Explanations.'' If ''n'' = 3, then it looks like this [[Image: Hasse4.jpg|150px]]. Linear extension is obtained by rewriting the Hasse diagram on a line, and people read it from bottom up as they read Hasse diagrams. How do we know where to put the elements? Starting from the bottom 1, we write each element in Hasse diagram only after the elements it connects from the bottom are already written. Hence, there are more than one linear extension of a poset. The gif pictures will help you comprehend the process. |
+ | <center> | ||
+ | <gallery widths="330px" heights="220px"> | ||
+ | Image: Poset_123456.gif| Figure-8 Illustrations of linear extension 123456. | ||
+ | Image: Poset_135246.gif| Figure-9 Illustrations of linear extension 135246. | ||
+ | </gallery></center> | ||
− | + | :Repeat the same steps as shown in Figure-8 and Figure-9, and we will get 5 linear extensions. The starting and ending point will never change, whereas the points in between vary. | |
− | + | <center> 123456 , 123546, 132456, 132546, 135246 </center> | |
− | : | + | :The number of linear extensions of a poset ''2''× ''n'' turns out to be the ''n''th Catalan numbers. |
Line 342: | Line 324: | ||
</template> | </template> | ||
− | It is not a coincidence but certainty. Each entry in Pascal's Triangle is in the form of <math>\tbinom{k}{r}</math> | + | It is not a coincidence but certainty. Each entry in Pascal's Triangle is in the form of <math>\tbinom{k}{r}</math>, where ''k'' is the row number starting at 0 from top to bottom, and ''r'' is the entry number starting at 0 from left to right. Since all of the blue numbers are on odd rows "0, 2, 4, ...", we use ''2n'' to represent them. Therefore, the numbers in middle column could be expressed as <math>\tbinom{2n}{n}</math>. The numbers in adjacent column could be expressed as <math>\tbinom{2n}{n+1}</math>. It is now obvious that the differences of numbers in the middle column on odd rows and their adjacent column are Catalan numbers. |
<center><math>\begin{pmatrix} | <center><math>\begin{pmatrix} | ||
Line 355: | Line 337: | ||
|ImageDesc= | |ImageDesc= | ||
+ | |||
+ | ==Basic Description== | ||
+ | |||
+ | |||
+ | The ''n''th Catalan number is defined as | ||
+ | |||
+ | :<center><math>C_{n} = \frac{1}{n+1} \cdot \begin{pmatrix} | ||
+ | 2n \\ | ||
+ | n | ||
+ | \end{pmatrix} = \frac{(2n)!}{n!(n+1)!}, \qquad n = 0, 1, 2, ...</math></center> | ||
+ | |||
+ | The binomial coefficient, <math>\tbinom{n}{r}</math>, pronounced as ''n choose r,'' represents the number of possible combinations of <math>r</math> objects from a collection of <math> n</math> objects: | ||
+ | |||
+ | <center> <math>\binom{n}{r} = \frac{n!}{r! (n-r)!} </math>. </center> | ||
+ | |||
+ | Therefore, | ||
+ | |||
+ | <center><math> \begin{pmatrix} | ||
+ | 2n \\ | ||
+ | n | ||
+ | \end{pmatrix} = \frac{(2n)!}{n! (2n -n)!} = \frac{2n \cdot (2n -1) \cdot (2n -2) \cdots (2n - n + 1)}{n!} </math></center> | ||
+ | |||
+ | Example: <math>\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}. </math> | ||
+ | |||
+ | 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. | ||
+ | |||
+ | :<center><math>C_{n} = \begin{pmatrix} | ||
+ | 2n \\ | ||
+ | n | ||
+ | \end{pmatrix} - \begin{pmatrix} | ||
+ | 2n \\ | ||
+ | n + 1 | ||
+ | \end{pmatrix}, \qquad n = 0, 1, 2, ...</math></center> | ||
+ | |||
+ | |||
+ | See ''Proof'' in the next section to know more about its proof. Note that <math>\tbinom{2n}{n} , \tbinom{2n}{n+1} \in \mathbb{N}</math> and <math>\tbinom{2n}{n} > \tbinom{2n}{n + 1} </math>. Therefore, <math>C_n</math> is the difference between two positive, natural numbers, which could be extended to [[Catalan Numbers#Pascal's Triangle|Pascal's Triangle]]. | ||
+ | |||
==Proofs== | ==Proofs== | ||
Line 366: | Line 388: | ||
\end{pmatrix}, n = 0, 1, 2, ...</math> is the formula for Catalan sequence. ''' | \end{pmatrix}, n = 0, 1, 2, ...</math> is the formula for Catalan sequence. ''' | ||
− | :1. Check it is true when <math>n = 0</math>. | + | :1. Check if it is true when <math>n = 0</math>. |
:<center><math>C_{0} = \begin{pmatrix} | :<center><math>C_{0} = \begin{pmatrix} | ||
2(0) \\ | 2(0) \\ | ||
Line 400: | Line 422: | ||
== Recursive Definition== | == 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. | |
<center><math>C_0 =1, C_{n+1} = \sum_{i=0}^n C_i C_{n-i} \text{ for } n\ge 1 </math>. </center> | <center><math>C_0 =1, C_{n+1} = \sum_{i=0}^n C_i C_{n-i} \text{ for } n\ge 1 </math>. </center> | ||
Line 410: | Line 432: | ||
The "pattern" is that we can always separate them in two collections. For example, we can separate the set "(<font color=orange>( )</font>) <font color=forestgreen>( )</font>" into: "(<font color=orange>( )</font>)" and "<font color=forestgreen>( )</font>." We name them collection A and collection B, either of which is able to contain zero pairs of parentheses. Similarly, <Big>( <font color=orange>(</font><font color=forestgreen>( )</font><font color=orange>)</font> ) </Big> could be separated into "<Big> ( <font color=orange>(</font><font color=forestgreen>( )</font><font color=orange>)</font> ) </Big>" and nothing. For <Big>( <font color=orange>( )</font><font color=forestgreen>( )</font> ) </Big>, we treat it as a whole and put it in collection A, so B is, again, empty. | The "pattern" is that we can always separate them in two collections. For example, we can separate the set "(<font color=orange>( )</font>) <font color=forestgreen>( )</font>" into: "(<font color=orange>( )</font>)" and "<font color=forestgreen>( )</font>." We name them collection A and collection B, either of which is able to contain zero pairs of parentheses. Similarly, <Big>( <font color=orange>(</font><font color=forestgreen>( )</font><font color=orange>)</font> ) </Big> could be separated into "<Big> ( <font color=orange>(</font><font color=forestgreen>( )</font><font color=orange>)</font> ) </Big>" and nothing. For <Big>( <font color=orange>( )</font><font color=forestgreen>( )</font> ) </Big>, we treat it as a whole and put it in collection A, so B is, again, empty. | ||
− | What about <Big> ( )<font color=orange>( )</font><font color=forestgreen>( )</font> </Big>? At first glance, we see three pairs of parentheses, but we have only two | + | What about <Big> ( )<font color=orange>( )</font><font color=forestgreen>( )</font> </Big>? 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: |
<center> <math> ( \quad ) \quad {\color{White} ( ) }</math> </center> | <center> <math> ( \quad ) \quad {\color{White} ( ) }</math> </center> | ||
Line 417: | Line 439: | ||
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. | 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" | {{{!}}class="wikitable" style="margin: 1em auto 1em auto;" border="1" cellspacing="3" cellpadding="10" | ||
Line 457: | Line 479: | ||
− | This method may not be | + | This method may not be so powerful for those applications with figures. Hence, we need another way of thinking to approach problems like Polygon Triangulation, in order to obtain the recursive definition. |
Here, we use the case of a 6-side polygon where ''n'' = 4. | Here, we use the case of a 6-side polygon where ''n'' = 4. | ||
− | We will start with drawing the first triangle based on the horizontal side at the top of hexagon | + | We will start with drawing the first triangle based on the horizontal side at the top of hexagon. This horizontal line is going to be part of the triangle. Since there are four vertices left, besides the two vertices that the horizontal line connects, we can draw four different cases. See figure below. |
[[Image:Recursive_1.jpg|center|300px]] | [[Image:Recursive_1.jpg|center|300px]] | ||
− | Each triangle divides the hexagon into two | + | Each triangle divides the hexagon into two polygons, on the left and right of the original triangle. Our next step is trying to triangulate these two separated polygons. Recall that a polygon with <math>k > 3</math> sides can be triangulated into <math>C_{k-2}</math> ways. In the first case (the first hexagon in the figure above), there is a pentagon on the left that has <math>C_3</math> ways of triangulation and nothing on the right of the selected triangle, which has <math>C_0</math> triangulations. Thus, the first case has <math>C_3 \cdot C_0 </math> solutions in total. In Case 2, we have a quadrangle and a triangle, so there are <math>C_2 \cdot C_1</math> solutions. Similar methods can be applied to Case 3 and 4. |
[[Image:Recursive_2.jpg|center|400px]] | [[Image:Recursive_2.jpg|center|400px]] | ||
− | Add up the number of solutions in each case, and we will get the total number of ways to triangulate a ''6'' - side polygon | + | Add up the number of solutions in each case, and we will get the total number of ways to triangulate a ''6'' - side polygon <math>C_4 = C_3 C_0 + C_2 C_1 + C_1 C_2 + C_0 C_3</math>. |
− | + | Generally, a ''n+2'' - side polygon have ''n'' different first triangles after the initial step of triangulation. On the left and right side of each of those triangle, there are ''n+1'' -side polygon and nothing <math>C_{n-1} C_0</math>, ''n'' - side polygon and a triangle <math> C_{n-2} C_1 </math>, ''n-1'' - side polygon and a quadrangle <math> C_{n-3} C_2 </math>, ''n-2''-side polygon and a ''5'' - side polygon <math> C_{n-4} C_3 </math>, and so on. | |
Take the sum of them, and the total number of ways to triangulate a ''n+2'' - side polygon is | Take the sum of them, and the total number of ways to triangulate a ''n+2'' - side polygon is | ||
− | <center><math>C_n = C_{n-1} C_0 + C_{n-2} C_1 +C_{n-3} C_2 + \cdots + C_1 C_{n+2} + C_0 C_{n-1}</math> | + | <center><math>C_n = C_{n-1} C_0 + C_{n-2} C_1 +C_{n-3} C_2 + \cdots + C_1 C_{n+2} + C_0 C_{n-1}</math>.</center> |
− | + | ||
+ | ---- | ||
− | |||
'''Bijection''' is the one-to-one correspondence of two sets or a both one-to-one and onto function. In a more understandable way, we can always pair every element in one set with exactly one element in the other set. Hence, there are no unpaired elements in either sets and the total numbers of elements in both sets are the same. | '''Bijection''' is the one-to-one correspondence of two sets or a both one-to-one and onto function. In a more understandable way, we can always pair every element in one set with exactly one element in the other set. Hence, there are no unpaired elements in either sets and the total numbers of elements in both sets are the same. | ||
Line 490: | Line 512: | ||
# no element of ''X'' may be paired with more than one element of ''Y'', | # no element of ''X'' may be paired with more than one element of ''Y'', | ||
# each element of ''Y'' must be paired with at least one element of ''X'', and | # each element of ''Y'' must be paired with at least one element of ''X'', and | ||
− | # no element of ''Y'' may be paired with more than one element of ''X''. | + | # no element of ''Y'' may be paired with more than one element of ''X''. <ref name = "Bijection">Wikipedia. ''Bijection''. Retrieved from http://en.wikipedia.org/wiki/Bijection.</ref> |
− | Property 1 and 2 | + | Property 1 and 2 guarantee that the bijection is within domain ''X''. Functions satisfying property 3 are called "onto." Functions satisfying property 4 are called "one-to-one." |
Line 516: | Line 538: | ||
: * Binary Trees. The base is the one full binary tree at the bottom. Similar to the first method for "Balanced Parentheses," collection A contains the "baby" trees branching out from the ''left'' node of the base tree, while collection B contains the "baby" trees branching out from the ''right'' node of the base tree. All of the trees in both collections have a total number of ''n'' - 1. | : * Binary Trees. The base is the one full binary tree at the bottom. Similar to the first method for "Balanced Parentheses," collection A contains the "baby" trees branching out from the ''left'' node of the base tree, while collection B contains the "baby" trees branching out from the ''right'' node of the base tree. All of the trees in both collections have a total number of ''n'' - 1. | ||
− | : * Binary Paths: Besides rotating counterclockwise, there is another way to look at the bijection between binary paths and open parentheses. Starting with the origin (0, 0), the unit path to the east is equivalent to an open parentheses, so the unit path to the north is equivalent to | + | : * Binary Paths: Besides rotating counterclockwise, there is another way to look at the bijection between binary paths and open parentheses. Starting with the origin (0, 0), the unit path to the east is equivalent to an open parentheses, so the unit path to the north is equivalent to a closed parentheses. The reason we could do this kind of bijection is that there are definitely same numbers of steps to the east and steps to the north because the grid has the same length and width. |
: * Stacking Coins. If you outline a border that is tangent to the coins for each coin stack, it will be obvious that it looks like mountain ranges. For instance, [[Image:CoinsRanges.jpg|130px]] is equivalent to the second mountain range when ''n''=3 illustrated in the section [[Catalan Numbers#Mountain Ranges|Mountain Ranges]]. | : * Stacking Coins. If you outline a border that is tangent to the coins for each coin stack, it will be obvious that it looks like mountain ranges. For instance, [[Image:CoinsRanges.jpg|130px]] is equivalent to the second mountain range when ''n''=3 illustrated in the section [[Catalan Numbers#Mountain Ranges|Mountain Ranges]]. | ||
− | : * 123 Avoiding Permutation. <font color=salmon>STILL TRYING TO FIGURE IT OUT</font> | + | : * 123 Avoiding Permutation. |
+ | : * Posets. <font color=salmon>STILL TRYING TO FIGURE IT OUT</font> | ||
Line 535: | Line 558: | ||
:<center><math>\left ( f(x) \right ) ^2 = C_0 C_0 + (C_0 C_1 + C_1 C_0) x + ( C_0 C_2 + C_1 C_1 + C_2 C_0) x ^2+ \cdots </math>.</center> | :<center><math>\left ( f(x) \right ) ^2 = C_0 C_0 + (C_0 C_1 + C_1 C_0) x + ( C_0 C_2 + C_1 C_1 + C_2 C_0) x ^2+ \cdots </math>.</center> | ||
− | + | Apply recurrence relation, <math> C_{n+1} = \sum_{i=0}^n C_i C_{n-i} \text{ for }n\ge 1 </math>, that is, <math>C_1 = C_0 C_0, C_2 = C_0 C_1 + C_1 C_0, \text{etc.}</math> Therefore, | |
:<center><math>\left ( f(x) \right ) ^2 = C_1 + C_2 x + C_3 x ^2+ \cdots </math>.</center> | :<center><math>\left ( f(x) \right ) ^2 = C_1 + C_2 x + C_3 x ^2+ \cdots </math>.</center> | ||
Line 547: | Line 570: | ||
:<center><math> x \left ( f(x) \right ) ^2 - f(x) + C_0 = 0</math>.</center> | :<center><math> x \left ( f(x) \right ) ^2 - f(x) + C_0 = 0</math>.</center> | ||
− | Solve it as <math> a | + | Solve it as <math> a m^2 + bm + c = 0 </math> where <math>a = x, b =-1, c = C_0 = 1, </math> and <math>m = f(x) </math>, by using the quadratic formula <math>m=\frac{-b \pm \sqrt {b^2-4ac}}{2a}</math> to get the roots. |
− | :{{EquationRef2|Eq. 3}}<center><math>f(x) = \frac{1 | + | :{{EquationRef2|Eq. 3}}<center><math>f(x) = \frac{1 - \sqrt {1-4x}}{2x}</math></center> |
− | + | If we follow the + symbol, <math>f(x) </math> will go to <math> \infty</math> as <math>x \to 0</math>. Therefore, we only use the - sign. | |
Line 557: | Line 580: | ||
:<math>(a + b) ^ n = {n \choose 0}a^n b^0 + {n \choose 1}a^{n-1}b^1 + {n \choose 2}a^{n-2}b^2 + \cdots </math> | :<math>(a + b) ^ n = {n \choose 0}a^n b^0 + {n \choose 1}a^{n-1}b^1 + {n \choose 2}a^{n-2}b^2 + \cdots </math> | ||
− | :<math>{\color{white}(a + b) ^ n} = a^n + \frac{n}{1} a^{n-1} b^1 + \frac{n(n-1)}{2 \cdot 1} a^{n-2} b^2 + \frac{ n (n-1) (n-2)} {3 \cdot 2 \cdot 1} a^{n-3} b^3 +\; \cdots </math> | + | :<math>{\color{white}(a + b) ^ n} = a^n + \frac{n}{1} a^{n-1} b^1 + \frac{n(n-1)}{2 \cdot 1} a^{n-2} b^2 + \frac{ n (n-1) (n-2)} {3 \cdot 2 \cdot 1} a^{n-3} b^3 +\; \cdots .</math> |
So when <math>a = 1, b= -4x</math>, and <math>n = \frac{1}{2}</math>, | So when <math>a = 1, b= -4x</math>, and <math>n = \frac{1}{2}</math>, | ||
− | :<center><math>\sqrt{1-4x} = (1-4x)^{\frac{1}{2}} = 1 + \frac{(\frac{1}{2})}{1} (-4x)^1 + \frac{ (\frac{1}{2}) (\frac{1}{2} -1)} {2 \cdot 1}(-4x)^2 + \frac{ (\frac{1}{2}) (\frac{1}{2} -1) (\frac{1}{2} -2)} {3 \cdot 2 \cdot 1}(-4x)^3 + \frac{ (\frac{1}{2})(\frac{1}{2} -1)(\frac{1}{2} -2)(\frac{1}{2} -3) } {5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} (-4x)^4 + \; \cdots </math>.</center> | + | :<center><math>\sqrt{1-4x} = (1-4x)^{\frac{1}{2}} </math></center> |
+ | |||
+ | :<center><math> = (1)^{\frac{1}{2}} + \frac{(\frac{1}{2})}{1} (1)^{\frac{1}{2} -1} (-4x)^1 + \frac{ (\frac{1}{2}) (\frac{1}{2} -1)} {2 \cdot 1} (1)^{\frac{1}{2} -2} (-4x)^2 + \frac{ (\frac{1}{2}) (\frac{1}{2} -1) (\frac{1}{2} -2)} {3 \cdot 2 \cdot 1} (1)^{\frac{1}{2} -3} (-4x)^3 + \frac{ (\frac{1}{2})(\frac{1}{2} -1)(\frac{1}{2} -2)(\frac{1}{2} -3) } {5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} (1)^{\frac{1}{2} -4} (-4x)^4 + \; \cdots </math>.</center> | ||
Simplify it, and we get: | Simplify it, and we get: | ||
− | :<center><math> (1-4x)^{\frac{1}{2}} = 1 + \frac{(\frac{1}{2})}{1} (- | + | :<center><math> (1-4x)^{\frac{1}{2}} = 1 + \frac{(\frac{1}{2})}{1} (-4)^1 (x)^1 + \frac{ (\frac{1}{2}) (-\frac{1}{2})} {2 \cdot 1}(-4)^2 (x)^2 + \frac{ (\frac{1}{2}) (- \frac{1}{2}) (-\frac{3}{2})} {3 \cdot 2 \cdot 1}(-4)^3 (x)^3 + \frac{ (\frac{1}{2})(-\frac{1}{2})(-\frac{3}{2})(-\frac{5}{2}) } {5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} (-4)^4 (x)^4 + \; \cdots </math>.</center> |
In order to make it nicer and clearer, replace the powers of 2 with factorials: | In order to make it nicer and clearer, replace the powers of 2 with factorials: | ||
− | :<center><math>(1-4x)^{\frac{1}{2}} = 1 - \frac{1}{1!} ( | + | :<center><math>(1-4x)^{\frac{1}{2}} = 1 - \frac{1}{1!} (2) x - \frac{1} {2!} (2^2) x^2 - \frac{ 3 \cdot 1} {3!} (2^3) x^3 + \frac{5 \cdot 3 \cdot 1}{4!} (2^4) x^4 + \; \cdots </math>.</center> |
Plug it back into {{EquationNote|Eq. 3}}. | Plug it back into {{EquationNote|Eq. 3}}. | ||
− | :<center><math>f(x) = 1 | + | :<center><math>f(x) = \frac{1 - \sqrt {1-4x} }{2x} = \frac{1}{2x} \cdot \left ( 1 - \frac{1}{1!} (2) x - \frac{1} {2!} (2^2) x^2 - \frac{ 3 \cdot 1} {3!} (2^3) x^3 + \frac{5 \cdot 3 \cdot 1}{4!} (2^4) x^4 + \cdots \right ) </math>.</center> |
+ | Then, | ||
− | The terms <math>3 \cdot 1, 5 \cdot 3 \cdot 1 </math> look like factorials, but | + | :<center><math> f(x) = 1 + \frac{1}{2!} (2) x + \frac{3 \cdot 1}{3!} (2^2) x^2 + \frac{5 \cdot 3 \cdot 1}{4!} (2^3) x^3 + \frac{7 \cdot 5 \cdot 3 \cdot 1}{5!} (2^4) x^4 + \; \cdots </math></center> |
+ | |||
+ | |||
+ | The terms <math>3 \cdot 1, 5 \cdot 3 \cdot 1 </math> look like factorials, but even numbers are missing. However, <math>2^2 \cdot 2! = 2 \cdot (2 \cdot 1) = 4 \cdot 2, 2^3 \cdot 3! = 2 \cdot (3 \cdot 2 \cdot 1) = 6 \cdot 4 \cdot 2. </math> Thus, if we want to express the factorial of odd numbers, all we need to do is to divid by factorials of even numbers: | ||
<center><math>5 \cdot 3 \cdot 1 = \frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{6 \cdot 4 \cdot 2} = \frac{6!}{2^3 \cdot 3!} </math></center> | <center><math>5 \cdot 3 \cdot 1 = \frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{6 \cdot 4 \cdot 2} = \frac{6!}{2^3 \cdot 3!} </math></center> | ||
Line 584: | Line 613: | ||
<center><math>(2n-1) \cdot (2n-3) \cdot \cdots \cdot 3 \cdot 1 = \frac{(2n)!}{2^n \cdot n!} </math></center> | <center><math>(2n-1) \cdot (2n-3) \cdot \cdots \cdot 3 \cdot 1 = \frac{(2n)!}{2^n \cdot n!} </math></center> | ||
− | Therefore, | + | Therefore, |
+ | |||
+ | :<center><math> f(x) = 1 + \frac{ \frac{(2\cdot 1)!}{2^1 \cdot 1!} \cdot 2}{2!} x + \frac{ \frac{(2 \cdot 2)!}{2^2 \cdot 2!} \cdot 2^2}{3!} x^2 + \frac{ \frac{(2 \cdot 3)!}{2^3 \cdot 3!} \cdot 2^3}{4!} x^3 + \cdots </math>.</center> | ||
+ | |||
+ | After several steps of simplification, | ||
:<center><math> f(x) = 1 + \frac{1}{2} \left( \frac{2!}{1!1!} \right) x + \frac{1}{3} \left( \frac{4!}{2!2!} \right) x^2 + \frac{1}{4} \left( \frac{6!}{3!3!} \right) x^3 + \frac{1}{5} \left( \frac{8!}{4!4!} \right) x^4 + \; \cdots = \sum_{i=0}^\infty \frac{1}{i + 1} {2i \choose i} x^i </math>.</center> | :<center><math> f(x) = 1 + \frac{1}{2} \left( \frac{2!}{1!1!} \right) x + \frac{1}{3} \left( \frac{4!}{2!2!} \right) x^2 + \frac{1}{4} \left( \frac{6!}{3!3!} \right) x^3 + \frac{1}{5} \left( \frac{8!}{4!4!} \right) x^4 + \; \cdots = \sum_{i=0}^\infty \frac{1}{i + 1} {2i \choose i} x^i </math>.</center> | ||
Line 592: | Line 625: | ||
We can now conclude that the coefficient is the formula for the ith Catalan number is <math>C_i = \frac{1}{i+1} {2i \choose i}. \blacksquare</math> | We can now conclude that the coefficient is the formula for the ith Catalan number is <math>C_i = \frac{1}{i+1} {2i \choose i}. \blacksquare</math> | ||
− | ''Other approaches could produce this definition formula as well, but we will not show them here. The proof shown is the most fundamental one, based on a proof from <ref name = "Catalan Numbers">Davis, Tom. ''Catalan Numbers''. Mathematical Circles Topics. 2010. Retrieved from http://www.geometer.org/mathcircles/catalan.pdf.</ref>. }} | + | ''Other approaches could produce this definition formula as well, but we will not show them here. The proof shown is the most fundamental one, based on a proof from <ref name = "Catalan Numbers">Davis, Tom. ''Catalan Numbers''. Mathematical Circles Topics. 2010. Retrieved from http://www.geometer.org/mathcircles/catalan.pdf.</ref>. |
+ | |||
+ | }} | ||
==Summary== | ==Summary== | ||
− | + | So far we have seen a certain number of applications of Catalan numbers and how they are related to each other. In fact, Catalan numbers arise in over 600 examples. | |
− | + | We have been convinced that, however the examples vary, applications of Catalan numbers are related to each other in an equivalent way. If we remember the Ballot sequence, which says that "In a sequence of ''2n'' items with ''n'' + 's and ''n'' - 's, if there are no more - 's than + 's anywhere in the sequence(in other words, the sum of this sequence is always nonnegative), then the number of ways of counting these items is the ''n''th Catalan number." | |
− | + | Think about the parentheses. If there are more closed parentheses than open parentheses somewhere in the sequence, then it will not make sense. | |
− | A class of 400 college students is voting for their class president. 200 students vote for A, and 200 students vote for B. If in the voting process | + | Any problem that follows this rule could be solved by Catalan numbers. Here is one example. A class of 400 college students is voting for their class president. 200 students vote for A, and 200 students vote for B. If in the voting process B always trails A, then could you be able to tell me the number ways of the sequence in which the votes could be appear? |
Line 616: | Line 651: | ||
<references/> | <references/> | ||
− | [ | + | [6] Stanley, Richard P. ''Enumerative Combinatorics'', vol.1. Cambridge University Press. New York/Cambridge. 1999. |
− | + | [7] Campbell, Douglas M.. ''The Computation of Catalan Numbers''. Mathematics Magazine, Vol. 57, No.4 (Sep., 1984), pp. 195 - 208. | |
− | [ | + | [8] Choo, Koo-Guan. ''Catalan Numbers''. Retrieved from http://www.maths.usyd.edu.au/u/kooc/catalan.html. |
− | [ | + | [9] Britz, Thomas. Cameron, Peter. ''Partially ordered sets''. 2001. Retrieved from http://www.maths.qmul.ac.uk/~pjc/csgnotes/posets.pdf. |
− | [ | + | [10] Dowling, Thomas A. ''Catalan Numbers''. Department of Mathematics, Ohio State University. Retrieved from http://www.mhhe.com/math/advmath/rosen/r5/instructor/applications/ch07.pdf. |
− | |||
− | |||
− | |||
|InProgress=Yes | |InProgress=Yes | ||
}} | }} |
Latest revision as of 11:50, 14 July 2012
Worm and Apple |
---|
Worm and Apple
- 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.
Contents
Basic Description
Catalan numbers grow rapidly. The first several Catalan numbers are listed as following.
0 | 1 | 2 | 3 | 4 | |||||||||||||
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
The first person who discovered Catalan numbers was Leonhard Euler. In 1751, Euler discussed the number of ways to cut a polygon with lines into triangles without any of the lines intersecting in his letter to Christian Goldbach, a German mathematician.
It was a French and Belgian mathematician, Eugène Charles Catalan, who described this number sequence in a well-defined formula, and introduced this subject to solve parentheses expressions.
Before Catalan, a Mongolian mathematician Minggatu was the first person in China who established and applied what was later to be known as Catalan numbers. In the 1730s, he brought forward this sequence of numbers and continued using it when he was trying to express series expansions of sin(ma), where m = 2, 3, 4, 5, 10, 100, 1000, and10000. This topic was included in his book, Ge Yuan Mi Lu Jie Fa (The Quick Method for Obtaining the Precise Ratio of Division of a Circle).
Applications
In this section we will consider 10 most representative examples of applications of Catalan numbers that arise in a variety of combinatorial problems. Examples are indicated with bullet points.
Stacking Coins
- We are going to stack coins on a bottom row that consists of n consecutive coins. It is not allowed to put the coins on the two sides of the bottom coins. How many ways there are to stack coins on the n coins?
- n: The number of ways to stack coins in the plane.
- Solution: .
Balanced Parentheses
- We want to group a string of parentheses. Each open parenthesis must have a matching closed parenthesis. Therefore, "(( )( ))" is valid, but ")( )) ((" and "( ))( ) (" are not. How many groupings are there to group n pairs of parentheses?
- n: The number of pairs of parentheses.
- Solution: .
1 solution | ||||||
1 solution | ||||||
2 solutions | ||||||
5 solutions |
- Many other applications are equivalent to balanced parentheses, and here is one example. If we want to connect 2n dots lying on a horizontal line in the plane with n nonintersecting arcs, the solution is also the Catalan sequence. Each arc connecting the two dots is equivalent to a pair of parentheses, with the left dot equivalent to an open parenthesis and the right dot equivalent to a closed parenthesis.
Mountain Ranges
- We want to form mountain ranges on a line with n upstrokes and n downstrokes. Same as the matching rule of the parentheses grouping problem, each upstroke must have a matching downstroke. How many mountain ranges are there for each value of n?
- n: The number of pairs of upstrokes and downstrokes.
- Solution:.
1 solution | ||||||
1 solution | ||||||
2 solutions | ||||||
/ \ / \ / \ | 5 solutions |
- Note that a pair of strokes and a pair of parentheses are equivalent: upstrokes are equivalent to open parentheses, and downstrokes are equivalent to closed parentheses. The fact that one pair of parentheses are inside another pair corresponds to that one pair of strokes are on top of another pair, thus forming the shape of mountain ranges.
Polygon Triangulation
- We want to cut convex polygons into triangles by connecting the vertices with straight, non-intersecting lines. How many different ways are there for a polygon with n+2 sides? This is the application Euler was interested in.
- n: The number of sides of the polygon - 2.
- Solution:
- Note that a 2-sided polygon is set to be triangulated in exactly one way, do nothing, so it follows .
Binary Trees
- How many full binary trees there are in order to have n internal nodes?
- n: The number of internal nodes on full binary trees.
- Solutioin:.
- Note that when there is only one node, we have one solution, which is the node itself, so it matches with .
- In summary, a full binary tree with internal nodes has nodes, branches and leaves.
- Other transformations of binary trees and plane trees also contains Catalan sequence:
- 1. Binary trees with n vertices ^{[1]}.
- 2. Plane trees with n+1 vertices ^{[1]}.
Binary Paths
- In a n × n grid, we are going to joint the lower left point A and the upper right point B by a path. We are only allowed to go to the right or upwards for each unit, and cannot pass above the diagonal connecting A and B.
- n: The number of paths described above.
- Solution: . (Thus, the answer to the main image is .)
- Facts:
- 1. Did you find out that these kind of paths look a lot like mountain ranges if you rotate them counterclockwise about origin until the diagonal is horizontal?
- 2. Did you notice that, whatever value n is, the first step is alway to the east and the last step is always to the north? It is because we cannot pass above the diagonal.
- This kind of lattice walk is also known as Dyck Path. Based on Cartesian Coordinates system, a Dyck path is a walk from (0, 0) to (n, n) in a n × n lattice that is composed of one-unit steps only in positive x-axis and positive y-axis directions without passing above the line y = x (see Figure-1). Other transforms of Dyck Paths turn out to follow the sequence of Catalan numbers as well:
- 1. Dyck Paths (as defined above) from (0, 0) to (2n + 2, 0) such that any maximal sequence of consecutive steps (1, -1) ending on the x-axis has odd length ^{[1]}.
- 2. Dyck Paths (as defined above) from (0, 0) to (2n + 2, 0) with no peaks at height two ^{[1]}.
Permutations
- A permutation of {1, 2, ... , n} is an rearrangement of the n numbers. For example, the permutation of {1, 2, 3} includes 6 terms: (1, 2, 3), (1, 3, 2), (2, 1, 3,), (2, 3, 1), (3, 1, 2), (3, 2, 1). 123-avoiding permutation means to avoid an increasing subsequence of 3 terms (the 3 terms do not have to be consecutive). Therefore, we should avoid (1, 2, 3) for n=3. Take n=4 as another example, (4, 3, 1, 2) is valid, but (4, 1, 2, 3) is not valid because of the subsequence 123, and neither is (2, 3, 1, 4) because of 234.
- n: The number of permutations that avoid 123.
- Solution: .
1 solution | ||
1 solution | ||
2 solutions | ||
5 solutions | ||
14 solutions |
- Note that 123-avoiding permutation only avoids an increasing subsequence of three terms, regardless of the value of n. Therefore, (1,2), (2,1) are valid although they are increasing subsequences as well.
- Similarly, there is a 321-avoiding permutation of [n], which avoids a decreasing subsequence of $3$ terms. Take n = 3 as an example, we will then have (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2). And a permutation of [n] is called 132-avoiding, ``if it does not have three entries a < b < c so that a is the leftmost of them and b is the rightmost of them ^{[2]}.
- Catalan numbers count shuﬄes of the permutation with itself, i.e., permutations of the multiset which are a union of two disjoint subsequences . On top of this, there should be no weakly decreasing subsequence of length three . ^{[3]}
- Explanations. A shuffle of and itself is obtained by intermixing the letters in each string of numbers, while the letters in each string must stay in the original order. For example, a shuffle of 123 and 456 could be: 124536 . No weakly decreasing of length three means that the subsequence either is strictly increasing or has at most two equal entries not followed by a decrease. For example, 121233 is valid (because it has only two equal entries instead of three with no decrease followed), but 112332is not (because there is a decrease, 2, followed after 33).
- Back to the application, let's see an example of n = 3, where we want to know the number of shuffles of permutations of 1, 2, 3 with 1, 2, 3. It turns out that there are 5 distinct shuffles:
- Note that they are distinctive shuffles. In fact, for each single shuffle, some of the entries may come from either string of 1, 2, 3, although the sequence appears the same. For instance, the first shuffle 112233 could have a multiplicity 8.
- Catalan sequence is also the answer to the number of permutations of , formed from integers 1, 1, 2, 2, 3, 3, ... n, n such that
- a) these integers 1, 2, 3, ... , n are in increasing order when they first occur, and
- b) there is no form like , where the integers do not have to be consecutive.
- For example, 1212 and 122313 are not valid. Here are the solutions where n = 3:
Young Diagrams
In combinatorics, partition of a positive integer n is an expression of rewriting n as a sum of positives integers, where the summands do not differ in orders. The sum would be called composition if order matters. Take n=4 as an example, there are 5 ways to partition 4: 4, 3+1, 2+2, 2+1+1, 1+1+1+1. Remember, the ordering of the integers does not matter, i.e. 1+1+2, 1+2+1, 2+1+1 are equivalent partitions.
Partitions could be visualized in explicit graphs, and the most commonly used one is called Young diagrams. Again, take n = 4 and n = 5 as two examples for better understanding. Young diagrams of partition 4 and 5 are shown in Figure-2 and Figure-3.
- Young diagrams that fit in the shape (n - 1, n - 2, ... , 1) follow Catalan sequence ^{[1]}.
- Explanations. The shape (n - 1, n - 2, ... , 1) is a Young diagram that looks like a upside down staircase. Its top stair consists of n - 1 blocks, next stair n - 2 blocks, and so on until the last stair has only 1 block. By "fit," we mean that we try to find Young diagrams that could be a part of the shape (n - 1, n - 2, ... , 1) or the entire shape.
- In this image above, the last figure is the shape (2, 1) where n = 3. Each of the other four figures, including the empty set, could be a part of the shape. Add the original shape, then we have five solutions for shape (2,1) in total.
Posets
Partially Ordered Set P, or Poset P for short, is a set together with a binary relation denoted , satisfying the following three axioms, where x and y are arbitrary objects:
- For all (reflexivity)
- If , and , then . (antisymmetry)
- If , and , then . (transitivity) ^{[1]}
Hasse diagram is used to represent a finite poset. Each element in the poset is a vertex in Hasse diagram. The transitive relation in the poset is represented by lines going up from one vertex to another in Hasse diagram. The lines could cross each other but cannot touch other vertex before it reaches the endpoint. It is the line segments and labeled vertices in the diagram that illustrates the partial order of a set. See Figure-4, -5, -6 for several examples of Hasse diagram. As you can see, the element in the poset is any object; it could be a set, a diagram or a number.
How do Hasse diagrams embody the 3 definitions of posets? In Figure 4,
- Each element in the diagram reflects itself, i.e., the set {a} is less or equal to itself {a}. This shows reflexivity.
- Since set {a} is less or equal to {a} and {a} is less or equal to {a}, then {a} = {a}. This symmetry does not work between, for example {a} and {b}, because {a} and {b} are two different, nonsymmetric sets. This is the idea of antisymmetry.
- Since the empty set is less or equal to set {a}, and set {a} is less or equal to set {a, b}, the empty set is less or equal to {a, b}. In the diagram, the three sets are connected with 2 line segments. This shows that if we can follow the lines going from the bottom element up to the top one, then all the elements on the way obey transitivity. Likewise, we can tell that {b} is less or equal to {a, b, c} according to the diagram.
- Linear extensions of the poset 2 × n follow Catalan sequence ^{[1]} (See Figure 7).
- Explanations. If n = 3, then it looks like this . Linear extension is obtained by rewriting the Hasse diagram on a line, and people read it from bottom up as they read Hasse diagrams. How do we know where to put the elements? Starting from the bottom 1, we write each element in Hasse diagram only after the elements it connects from the bottom are already written. Hence, there are more than one linear extension of a poset. The gif pictures will help you comprehend the process.
- Repeat the same steps as shown in Figure-8 and Figure-9, and we will get 5 linear extensions. The starting and ending point will never change, whereas the points in between vary.
- The number of linear extensions of a poset 2× n turns out to be the nth Catalan numbers.
Pascal's Triangle
- Catalan numbers lie in Pascal's Triangle.
If you take the difference of numbers in the middle column on odd rows and their adjacent column, you will find the Catalan sequence.
<template>AlignEquals
A More Mathematical Explanation
- Note: understanding of this explanation requires: *combinatorics
Basic Description
The nth Catalan number is defined as
'"`UNIQ--math-0000003D-QI [...]
Basic Description
The nth Catalan number is defined as
The binomial coefficient, , pronounced as n choose r, represents the number of possible combinations of objects from a collection of objects:
Therefore,
Example:
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.
See Proof in the next section to know more about its proof. Note that and . Therefore, is the difference between two positive, natural numbers, which could be extended to Pascal's Triangle.
Proofs
- Prove is the formula for Catalan sequence.
- 1. Check if it is true when .
.
- 2. Show it is true when .
- Prove this recurrence relation: for n=0, 1, 2, ... .
- Recall that
. - Therefore, we have
. - Take the ratio of to :
. - Thus,
- for all nonnegative values of n.
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.
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.
Add up all of the situations, and we get the total number:
This formula is the recursive relation that we are looking for. Plugging actual numbers may help you understand this great formula.
<template>AlignEquals
Teaching Materials
- There are currently no teaching materials for this page. Add teaching materials.
References
- ↑ ^{1.0} ^{1.1} ^{1.2} ^{1.3} ^{1.4} ^{1.5} ^{1.6} Stanley, Richard P. Enumerative Combinatorics, vol.2. Cambridge University Press. New York/Cambridge. 1999. Cite error: Invalid
<ref>
tag; name "Enumerative Combinatorics" defined multiple times with different content Cite error: Invalid<ref>
tag; name "Enumerative Combinatorics" defined multiple times with different content Cite error: Invalid<ref>
tag; name "Enumerative Combinatorics" defined multiple times with different content - ↑ Bona, Miklos. A self-dual poset on objects counted by the Catalan numbers. Schol of Mathe- matics, Institute of Advanced Study. November 10, 1998.
- ↑ Stanley, Richard P. Catalan Addendum. MIT Mathematics. Version of 22 October 2011. (No.t^6) Retrieved from Richard Stanley's home page http://www-math.mit.edu/~rstan/ec/.
[6] Stanley, Richard P. Enumerative Combinatorics, vol.1. Cambridge University Press. New York/Cambridge. 1999.
[7] Campbell, Douglas M.. The Computation of Catalan Numbers. Mathematics Magazine, Vol. 57, No.4 (Sep., 1984), pp. 195 - 208.
[8] Choo, Koo-Guan. Catalan Numbers. Retrieved from http://www.maths.usyd.edu.au/u/kooc/catalan.html.
[9] Britz, Thomas. Cameron, Peter. Partially ordered sets. 2001. Retrieved from http://www.maths.qmul.ac.uk/~pjc/csgnotes/posets.pdf.
[10] Dowling, Thomas A. Catalan Numbers. Department of Mathematics, Ohio State University. Retrieved from http://www.mhhe.com/math/advmath/rosen/r5/instructor/applications/ch07.pdf.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.