Catalan Number

The Cattleya number is also called card The Catalan number 2477203708 is a series of numbers that often appear in various counting problems in combinatorics. This number is more important in computer science, and there are some specific application examples. This article is mainly divided into three parts:

1. The explanation of the meaning of the recursive expression of Cattelan numbers
2. The proof process of Cattelan number expressions
3. Cattelan The application of the number in the computer

Catalan Number recursive interpretation

Assuming h(0)=1, h(1 )=1, the catalan number satisfies the recurrence formula:

What is the physical meaning behind the recursion? Here is the problem of the stack sequence:

Problem description:A stack ( Infinity) push sequence is 1, 2, 3,…, n, how many different pop sequence are there?

Meaning explanation:First, we set h(n)

“>h(n)< /span>h(n)=The number of pop sequences with sequence number n. (We assume that the last element popped from the stack is k. Obviously, the conditions when k takes different values ​​are independent of each other, that is, the addition principle can be used after the number of cases where each k is finally popped from the stack. Since k is finally popped from the stack, Therefore, before k is put on the stack, the values ​​smaller than k are all popped out of the stack, here is the case h( k−1)

“> h(k−1) h(k−1), and then the value greater than k is stacked, And they are all popped before k, so there is h(n−k) math>”>h(n−k) h(n−k) kinds of ways, because it is smaller than k and The stacking and popping of values ​​greater than k are independent of each other. The principle of multiplication can be used here, h( n−k)&#x2217 ;h(k−1< /mn>)

“>h(n−k)∗h (k−1) span> h(n−k)∗h(k−1), the sum is Catalan recursion. span>

Catalan Number expression proof

The nth Cattleya number h (n) The expression is as follows

The specific certification process is as follows

In order to facilitate programming To achieve, the relationship between h(n) and h(n-1) needs to be further derived

It is known that h< mo stretchy="false">(n)

“>h(n)h(n), Easy to know

Deductionh(n)

“>h(n ) h(n)’sC2n< mrow class="MJX-TeXAtom-ORD">n

“> C n2n C2nn and h(n−1)

“>h(n−1)h(n −1) of C2n&#x2212 ;2n−1

“>Cn−12n−2< /span>C2n−2n The relationship between −1 is determined by kCnk=n< mi>Cn−1 k−1“>kCkn= nCk−1n−1 span> kCnk=nCn−1k−1知

h(n)

“>C2nn

“>h(n−1)

“>C2n−2n−1

“>kCnk=nCn−1k−1

“>
最终得到h(n)

“>h(n)h(n)和h(n−1)

“>h(n−1)h(n−1)之间的递归式h(n)=2(2n−1)n+1h(n−1)

“>h(n)=2(2n−1)n+1h(n−1)h(n)=2(2n−1)n+1h(n−1)< /span>

Catalan Number应用实例

括号匹配问题

问题描述: 矩阵连乘 P=A1A2...An

“>P=A1A2...AnP=A1A2…An，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，问有几种括号化的方案？

问题转换一下就是n对括号的正确匹配方案，可以做一下LeetCode-22

出栈次序问题

问题描述: 一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?

出栈问题问题正是卡特兰数递归式h(n)=h(0)h(n−1)+h(1)h(n−2)+...+h(n−1)h(0)

“>h(n)=h(0)h(n−1)+h(1)h(n−2)+...+h(n−1)h(0)h(n)=h(0)h(n−1)+h(1)h(n−2)+…+h(n−1)h(0)的由来

相关应用问题

1. 有2n个人排成一行进入剧场，入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？ (将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)

2. n个1和n个0组成一个2n位的二进制数，要求从左到右扫描，0的累计数不小于1的累计数，求满足条件的的数。

3. 12个人排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？

   我们先把这12个人从低到高排列，然后，选择6个人排在第一排，那么剩下的6个肯定是在第二排。对问题进行转化：用0表示对应的人在第一排，用1表示对应的人在第二排，那么含有6个0，6个1的序列，并且任意前缀中0的个数大于等于1的个数就对应一种方案，转化后的问题就是问题2了。

4. 给定节点组成二叉树的问题：给定n个节点，能构成多少种形状不同的二叉树？

   先取一个点作为顶点，然后左边依次可以取0至n-1个相对应的，右边是n-1到0个，两两配对相乘，就是h(0)∗h(n−1)+h(2)∗h(n−2)+...+h(n−1)h(0)=h(n)

   “>h(0)∗h(n−1)+h(2)∗h(n−2)+...+h(n−1)h(0)=h(n) h(0)∗h(n−1)+h(2)∗h(n−2)+…+h(n−1)h(0)=h(n)能构成h(n)

   “>h(n)h(n)个，因此二叉树问题也可以解释卡特兰数递归式(1.1)式的由来

5. n*n棋盘从左下角走到右上角而不穿过主对角线的走法？

   要从左下角走到右上角则必须向上走n步，向右n步，同时为了不跨过主对角线，则走过的步数中向上走的步数必须大于等于向右走的步数，剖析之后发现这个问题与问题3是等价问题，走法有卡特兰数h(n)

   “>h(n)h(n)种。

   可以做一下下面两题练练手：

   hdoj2067-小兔的棋盘

   LeetCode62-Unique Paths

6. n个+1和n个-1构成的2n项序列，其部分和总满足：a1+a2+...+an>=0

   “>a1+a2+...+an>=0a1+a2+…+an>=0的序列的个数。

   卡特兰数表达式(1.2)式就是以该问题模型为基础推导出来的

7.