January 10, 2013 at 11:42Catalan numbers
Undoubtedly, the most remarkable mathematical fact is identity 
. In it, surprisingly, seemingly completely unrelated constants from different areas of mathematics converged. To prove this identity is not so difficult, but few manage to explain it, understand the deepest meaning.
As another remarkable fact, I would like to recall the numbers of Catalan, which surprisingly emerge in a variety of combinatorial problems. Unfortunately, they fall outside the consideration of a typical school curriculum, but I am sure that any computer science specialist should be familiar with them.
The Catalan number itself is expressed by the formula C (n) = (2n)! / N! (N + 1)!, Where the exclamation point, as usual, denotes a factorial. The beginning of the sequence looks like this: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 ...
English Wikipedia claims that at least 66 different designs are known that lead to the appearance of Catalan numbers. Here is some of them:
For each of these constructions, it can be proved either by induction or by recursive relations that the number of corresponding objects is expressed by the Catalan number. I will not dwell on these proofs - they can be found in discrete mathematics textbooks. There are also some wonderful relationships that can be obtained using some of the constructions mentioned. But this requires writing cumbersome formulas, which I would like to avoid. Now another thing is more interesting - is it really a coincidence of all these quantities for completely different things?
Of course not. The connection of these structures is much deeper. It is possible to build a one-to-one correspondence between these objects and I will try to demonstrate some of these correspondences. In addition to simple curiosity, this has some practical value. For example, the problem of generating all binary trees (the solution of which is not obvious in the forehead) can be reduced to the much simpler problem of generating bracket sequences.
It is very easy to construct a correspondence between bracket sequences and monotonous squared paths. Reading the bracket sequence from left to right, we will build the path, starting from the lower left corner - for each opening bracket we draw a horizontal segment, for a closing bracket - vertical.
Since the sequence had an equal number of opening and closing brackets, the path will eventually end in the upper right corner, and the fact that each opening bracket is earlier than the corresponding closing bracket (because the sequence is correct) ensures that the path does not go to upper half of the square. Obviously, this construction is reversible and a bracket sequence can be obtained from each monotone path.
In the figure below, the corresponding brackets and line segments are marked in one color. It is clearly seen that the segments corresponding to one pair of brackets “see each other”:
As a second problem, we construct a correspondence between the correct bracket sequences and 2xn Yungam tables. Here, too, everything is simple. We number the brackets from left to right. If the bracket is opening, then write the number corresponding to it on the top line. If it closes, then to the bottom. Since the i-th opening bracket is always to the left of the i-th closing bracket, the number corresponding to the opening bracket will be less than the number corresponding to the closing one. So, the top number in the table will be less than the bottom in the same column, that is, from the correct bracket sequence, we got the Young table. This construction is also reversible, which means that a one-to-one correspondence is obtained.
Now let's deal with binary trees. It is very easy to see the correspondence between binary trees and parentheses in an expression with homogeneous operations, but this gives slightly different sequences. To bind binary trees to the correct bracket sequences, you need to use a slightly different approach. We will use the standard tree traversal and number the vertices (we take the root as 0) in the traversal order. Now, if during the transition to the number I we went down from the parent to the child, then we put the opening bracket in the i-th place. Otherwise, set the closing.
The tree is binary, so each node has a neighbor. So, going down to the child and putting the opening bracket, we will sooner or later get to his neighbor and put the closing bracket. This ensures the correctness of the resulting sequence. The construction is easy to reverse and taking as a basis the bracket sequence to get a binary tree.
Note that if there are n pairs in the bracket sequence, then the corresponding tree has n + 1 leaves.
To build a correspondence between triangulations of a polygon, it is easiest to use a binary tree. This time we number all the leaves in it from left to right (mark the remaining nodes with letters). For triangulation we take a polygon in which there are one more vertices than the leaves in the tree. We mark one of the sides of this polygon as the starting one, and number the rest (for clarity, counterclockwise).
Next, we perform the following procedure — if two vertices of a tree are adjacent, then we “tighten” the corresponding sides of the polygon with the diagonal, which we mark with the letter that marks the parent of this pair of nodes in the tree. Next, we continue the “contraction” procedure until the only starting segment remains from the polygon.
As you can see, the three sides of each triangle in the resulting partition correspond to one parent node and its two descendants. Therefore, if you take two different trees, you get two different partitions.
Well, in conclusion, I will give a plate that shows the correspondence of objects for the third number of Catalan.
. In it, surprisingly, seemingly completely unrelated constants from different areas of mathematics converged. To prove this identity is not so difficult, but few manage to explain it, understand the deepest meaning. As another remarkable fact, I would like to recall the numbers of Catalan, which surprisingly emerge in a variety of combinatorial problems. Unfortunately, they fall outside the consideration of a typical school curriculum, but I am sure that any computer science specialist should be familiar with them.
The Catalan number itself is expressed by the formula C (n) = (2n)! / N! (N + 1)!, Where the exclamation point, as usual, denotes a factorial. The beginning of the sequence looks like this: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 ...
English Wikipedia claims that at least 66 different designs are known that lead to the appearance of Catalan numbers. Here is some of them:
- Correct parenthesis sequences are sets of opening and closing brackets in which each opening bracket corresponds to a closing one. The number of possible sequences with a fixed number of pairs of brackets is expressed by the Catalan number. For example, 14 correct sequences of four pairs of brackets:
((((()))), ((() ())), ((()) ()), ((())) (), (() ( ())), (() () ()), (() ()) (),
(()) (()), (()) () (), () ((())), () (() ()), () (()) (), () () (()), () () () () - Binary trees - trees, from each node of which (except for the leaves) exactly two branches come out. The number of binary trees with a given number of leaves is the number of Catalan. The figure shows five trees with 4 leaves in each.
Such trees were already discussed on Habré - Any trees. The number of nonisomorphic trees with a given number of vertices is also equal to the number of Catalan. Such trees were also discussed.
- Monotone paths in a square - routes from the lower left corner of the square to the upper right, which go along the grid lines up or to the right and do not go above the diagonal. The figure shows all such paths for a 3x3 square.
- Triangulation of the polygon. The number of different triangulations of a convex polygon by diagonals is equal to the Catalan number.
- Splitting vertices of a polygon into pairs. An even number of points on the circle can be combined into pairs with disjoint chords. The number of ways such associations are also equal to the number of Catalan.
- Young's table is a rectangle filled with consecutive numbers so that they grow in all rows and columns. The number of 2xn Young tables is also expressed by the Catalan number.
For each of these constructions, it can be proved either by induction or by recursive relations that the number of corresponding objects is expressed by the Catalan number. I will not dwell on these proofs - they can be found in discrete mathematics textbooks. There are also some wonderful relationships that can be obtained using some of the constructions mentioned. But this requires writing cumbersome formulas, which I would like to avoid. Now another thing is more interesting - is it really a coincidence of all these quantities for completely different things?
Of course not. The connection of these structures is much deeper. It is possible to build a one-to-one correspondence between these objects and I will try to demonstrate some of these correspondences. In addition to simple curiosity, this has some practical value. For example, the problem of generating all binary trees (the solution of which is not obvious in the forehead) can be reduced to the much simpler problem of generating bracket sequences.
Compliance 1
It is very easy to construct a correspondence between bracket sequences and monotonous squared paths. Reading the bracket sequence from left to right, we will build the path, starting from the lower left corner - for each opening bracket we draw a horizontal segment, for a closing bracket - vertical.
Since the sequence had an equal number of opening and closing brackets, the path will eventually end in the upper right corner, and the fact that each opening bracket is earlier than the corresponding closing bracket (because the sequence is correct) ensures that the path does not go to upper half of the square. Obviously, this construction is reversible and a bracket sequence can be obtained from each monotone path.
In the figure below, the corresponding brackets and line segments are marked in one color. It is clearly seen that the segments corresponding to one pair of brackets “see each other”:
Compliance 2
As a second problem, we construct a correspondence between the correct bracket sequences and 2xn Yungam tables. Here, too, everything is simple. We number the brackets from left to right. If the bracket is opening, then write the number corresponding to it on the top line. If it closes, then to the bottom. Since the i-th opening bracket is always to the left of the i-th closing bracket, the number corresponding to the opening bracket will be less than the number corresponding to the closing one. So, the top number in the table will be less than the bottom in the same column, that is, from the correct bracket sequence, we got the Young table. This construction is also reversible, which means that a one-to-one correspondence is obtained.
Compliance 3
Now let's deal with binary trees. It is very easy to see the correspondence between binary trees and parentheses in an expression with homogeneous operations, but this gives slightly different sequences. To bind binary trees to the correct bracket sequences, you need to use a slightly different approach. We will use the standard tree traversal and number the vertices (we take the root as 0) in the traversal order. Now, if during the transition to the number I we went down from the parent to the child, then we put the opening bracket in the i-th place. Otherwise, set the closing.
The tree is binary, so each node has a neighbor. So, going down to the child and putting the opening bracket, we will sooner or later get to his neighbor and put the closing bracket. This ensures the correctness of the resulting sequence. The construction is easy to reverse and taking as a basis the bracket sequence to get a binary tree.
Note that if there are n pairs in the bracket sequence, then the corresponding tree has n + 1 leaves.
Compliance 4
To build a correspondence between triangulations of a polygon, it is easiest to use a binary tree. This time we number all the leaves in it from left to right (mark the remaining nodes with letters). For triangulation we take a polygon in which there are one more vertices than the leaves in the tree. We mark one of the sides of this polygon as the starting one, and number the rest (for clarity, counterclockwise).
Next, we perform the following procedure — if two vertices of a tree are adjacent, then we “tighten” the corresponding sides of the polygon with the diagonal, which we mark with the letter that marks the parent of this pair of nodes in the tree. Next, we continue the “contraction” procedure until the only starting segment remains from the polygon.
As you can see, the three sides of each triangle in the resulting partition correspond to one parent node and its two descendants. Therefore, if you take two different trees, you get two different partitions.
Instead of an epilogue
Well, in conclusion, I will give a plate that shows the correspondence of objects for the third number of Catalan.