In depth understanding of the Catalan number and its applications
- 2020-04-02 01:02:43
- OfStack
To h (0) = 1, h (1) = 1, Catalan number meet recursive type: h (n) = h (0) * h (n - 1) + h (1) * h (n - 2) +... A + h (n - 1) h (0) (n > = 2) The general form of Catalan number formula is: < img Alt = "border = 0 C_n = \ frac {1} {n + 1} {2 n \ choose n} = \ frac {(2 n)! } {(n + 1)! N! } "SRC =" / / files.jb51.net/file_images/article/201305/201305281742269.png ">
Recursive relation:
< img border = 0 class = Tex Alt = "C_0 = 1 \ quad \ mbox {and} \ quad C_ {n + 1} = \ sum_ {I = 0} ^ {n} C_i \, C_ {n - I} \ quad \ mbox {for} n \ ge 0." SRC = "/ / files.jb51.net/file_images/article/201305/2013052817422610.png" >It also meet
The < img border = 0 class = Tex Alt = "C_0 = 1 \ quad \ mbox {and} \ quad C_ {n + 1} = \ frac {2} (2 n + 1) + 2} {n C_n," SRC = "/ / files.jb51.net/file_images/article/201305/2013052817422611.png" >
This provides a faster way to calculate the catalans.
Cattelan number applies n elements in order to push, how many out orders? This problem is a Catalan number problem, and the proof process is as follows:
If 1 represents the push stack and 0 represents the push stack, it can be converted to find a binary number of 2n bits, including n ones and n zeros. When scanning from left to right to any one bit, the number of zeros passed is not more than 1. Obviously containing n, n, 1 0 2 n bit binary number of < img border = 0 class = Tex Alt = "{2 n \ choose n}" SRC = "/ / files.jb51.net/file_images/article/201305/2013052817422612.png" >, consider below does not meet the requirements of the number.
Consider a 2n bit binary number with n 1s and n 0s, when m+1 0 and m 1 1 are scanned to the 2m+1 bit (it is easy to prove that there must be such a case), then there must be n-m 1 and n-m-1 0 in the subsequent 0-1 arrangement. If the zeros of 2m+2 and subsequent parts become 1, and 1 becomes 0, then there is a binary number of n+1 zeros and n-1 ones.
Conversely, any 2n binary number consisting of n+1 0 and n-1 1 1, since there are 2 more 0's and 2n is even, the cumulative number of 0's must exceed the cumulative number of 1's on an odd digit. Also in the following part, the 0 and 1 are interchanged, so that it becomes a 2n digit composed of n 0 and n 1, that is, the 2n digit composed of n+1 0 and n-1 1 must correspond to an unqualified number.
Thus the undesirable 2n bits correspond to the arrangement of n+1 zeros and n-1 ones. Obviously, the number of scenarios that do not meet the requirements is c(2n,n+1).
Thus < img border = 0 class = Tex Alt = "C_n = {2 n \ choose n} - {2 n \ choose n + 1} = \ frac {1} {n + 1} {2 n \ choose n}" SRC = "/ / files.jb51.net/file_images/article/201305/2013052817422613.png" >. Never put off till tomorrow what you can.
Bracketed problem For example, matrix chain product: P=a1 x a2 x a3 x ...... By an, by the associative law of multiplication, we don't change the order, we just use parentheses to represent the product of pairs. (h (n))
Stack order problem
1. The stack sequence of a stack (infinite) is 1,2,3,.. N, how many different stack sequences are there?
2. 2n people entered the theater in a line. Admission is 5 yuan. Only n of them have a 5 dollar bill, and the other n have a 10 dollar bill, and the theater has no other money, so how many ways is there to get a 5 dollar bill change at the box office if someone with 10 dollars buys a ticket? The arrival of a $5 holder is considered to be a $5 push, and the arrival of a $10 holder is considered to be a $5 push.
Divide multilateral rows into triangle problems
1. How many ways can a convex polygon region be divided into a triangle region?
A big city lawyer works n blocks north and n blocks east of her house. Every day she walks 2n blocks to work. If she never crosses (but can touch) the diagonal from home to office, how many possible paths are there?
3. Select 2n points on the circle and connect these points in pairs to make the n line segments obtained disjoint.
Given N nodes, how many different binary trees can be formed?
Some pen questions
1, 16 people in order to buy baked bread, eight of them each with only a piece of 5 yuan, the other eight each with only a piece of 10 yuan. The owner of the bakery had no money at the beginning. There were 16 customers who didn't know each other, and each of them bought only one. Ask the 16 people how many ways they can arrange their money so that they don't have to break the bank.
H (8) = 16! / (8! * 9!) Is equal to 1430, so the total is equal to h of 8 times 8 factorial. * 8! = 16! / 9
2, in the library a total of six people in line, three return "interview" book, three in the "interview" book, the library has no interview book, the total number of their line?
H (3) = 6! / (3! * 4!) Is equal to 5, so the total is equal to h of 3 times 3 factorial. * 3! = 180