Catalan number
Don't really know how to start.
doCatalan The count starts with its definition.
\(f_i\) It's Cattleya's number.\(i\) item that makes\(f_0 = 1\)
Recursive:\(f_i = \sum_{j = 0}^{i - 1} f_j \times f_{i - j - 1}\)
Recursive: $ f_{i+1} = f_i \times \frac{2 \times (2i + 1)}{i+2} $
The simplification gives:\(f_i = C_{2i}^{i} - C_{2i}^{n - 1}\)
According to the recursive formula, it is known that the Cartland number is describing: when we can divide a problem and get two subproblems, and the two subproblems do not affect each other.
Classical Example: Triangulation of Convex Polygons
We use a number of lines to connect\(n\) The two vertices of a side shape, where lines and lines do not intersect, are finally divided into a number of triangles, and the number of division schemes is asked.
We learned this stuff in middle school. But essentially it's division, starting with a cut that divides into two small convex polygons. Enumerate how many vertices are on the left side after the division, and then multiply the number of solutions for the two small convex polygons.
Get the recursive formula:\(f_i = \sum_{j = 0}^{i - 1} f_j \times f_{i - j - 1}\)
Exactly the same.
Number of programs for binary trees
\(n\) How many kinds of binary trees are there for the number of points. Distinguish between left and right sons, i.e., swapping left and right sons directly counts as new.
Binary trees are also very classically divided into two pieces. All still enumerate the number of left son nodes and list the recursive equations directly.
\(f_i = \sum_{j = 0}^{i - 1} f_j \times f_{i - j - 1}\)
Exactly the same.
The above problems are all based on recursive formulas. We talk about it next:\(f_i = C_{2i}^{i} - C_{2i}^{i - 1}\)
Two-dimensional planar path problem
On a two-dimensional planar coordinate system from the\((0,0)\) until (a time)\((n,n)\), which can only go one step up or one step to the right at a time, ask how many routes there are. There is the only requirement that the points traveled must be in a straight line\(y =x\) down, i.e., the number of times you go up at any given moment must be less than or equal to the number of times you go right.
Removing the unique condition is to use\(n\) Up.\(n\) Right. Ask this.\(2n\) All permutations of an operation. We readily obtain that in sequences that are all upward going, the selection of the\(n\) One out into the right.
Consider illegal paths, for any illegal path along a straight line\(y = x + 1\) Mirroring, all discordant paths go to this line and only discordant paths go to this line. After mirroring the endpoint becomes\((n - 1,n+1)\) , we can map the illegitimate paths one by one as described above into the paths from the\((0,0)\) until (a time)\((n - 1,n + 1)\) path, there are still a total of\(2n\) An operation that is nothing more than the selection of\(n - 1\) One when to the right.
Finally, we get Eq:\(f_i = C_{2i}^{i} - C_{2i}^{i - 1}\)
disjoint chord problem (math.)
A circle with\(2n\) points, link any two with a string so that any two lines do not intersect.
We rewrite the line as a start point and an end point. The Chint start point and the first end point encountered clockwise are connected to a line. We can do a one-to-one mapping.
Still thinking in terms of what can be intersected, it is easy to get a total of\(C_{2i}^{i}\) Kinds of programs.
The case of illegitimacy must be that one end point is not connected, that is, all the previous starting points are matched, so it's still the same as the aforementionedTwo-dimensional planar path problem same, i.e., the number at the starting point at any given moment must be greater than the number at the end point.
Finally got:\(f_i = C_{2i}^{i} - C_{2i}^{i - 1}\)
More
Cartesian numbers exist everywhere: number of bracket sequences, in and out of stacks, 312 alignments... Understand that its essence is the division of the problem, selecting the occurrence of the event scenarios to be mapped one by one. It's really quite simple.