卡特兰数 —— 一次分析过瘾！

卡特兰数的性质：

0：给定n个0和n个1，他们按照某种顺序排成长度为2n得序列，满足任意前缀中0得个数都不少于1得个数的序列的个数为：

证明：

我们假设不满足条件的序列个数为S。

那么一定存在一个位置：1 <= 2p+1 <= n.

使得前2p+1个数中有p个0,p+1个1.

则后面的数中有n-p个0，n-p-1个1

我们让后面的数取反（即0变1，1变0）

则现在序列总共有:

p+n-p-1  =  n-1 个 0

p+1+n-p = n+1 个 1

那么对于n-1个0，n+1个1的任意排列序列，一定存在一个位置2p+1,使得[1,2p+1]中有p个0，p+1个1.（显然，1比0多2个，无论如何都存在这么一个位置）

把后面的数翻转后就得到了n个0，n个1的任意序列

综上

即 

得证。

问题0的变形：m个0，n个1的序列，任意前缀的0的个数不少于任意前缀的1的个数

同上：

如果01任意排列，m个0，n个1。的序列个数为.

直接求满足条件的不好求，我们假设不满足条件的序列个数为S。

那么一定存在一个位置：1 <= 2p+1 <= 2*n.

使得前2p+1个数中有p个0,p+1个1.

则后面的数中有m-p个0，n-p-1个1

我们让后面的数取反（即0变1，1变0）

则现在序列总共有:

p+n-p-1  =  n-1 个 0

p+1+m-p = m+1 个 1

那么对于n-1个0，m+1个1的任意排列序列，一定存在一个位置2p+1,使得[1,2p+1]中有p个0，p+1个1.（显然，1比0多2个，无论如何都存在这么一个位置）

n-1-p个0，m-p个1

我们把后面的数01翻转:

m-p+p=m个0，n-1-p+p+1=n个1.

综上

即 

 

——————————————————分割线————————————————————

http://lanqi.org/skills/10939/ 下列问题参考这篇blog————解法是自己分析的，只是问题选用这篇博客

 

1.一个足够大的栈的进栈序列为1,2,3,⋯,n时有多少个不同的出栈序列

一个合法的序列必须满足任意时刻出栈小于等于入栈，即任意前缀中，出栈的个数小于入栈的个数。

且序列中入栈n次，出栈n次

显然可以转化为问题0求解。

2.求n+1个叶子的满二叉树的个数

满足满二叉树必须左节点等于右节点等于n。

从根节点出发dfs遍历，遇到左节点记+1，遇到右节点计-1

只要满足任意时刻左节点的个数大于等于有节点的个数，这个序列构成的满二叉树就是合法的。

转化为问题0.

3.电影票每张50元，如果有m+n个人排队买票，其中m个人各持有50元面值的钞票1张，另外n个人各持有100元面值的钞票1张，而票房没有预备找零．有多少种方法可以将这m+n个人排成一列，顺序购票，使得无需因为等待找零而耽误时间？

显然，一张50可以找零一张100的，即任意时刻，持有50钞票的人必须不少于持有100钞票的。

且m个50，n个100，即问题0的变形。

4.n个左括号和n个右括号组成的合法括号序列

我们把左括号当成0，右括号当成1.组成  n个0，n个1的序列。

满足任意前缀0的个数大于等于1的个数即是一个合法的序列。

即转化为了问题0

5.如图,圆周上有2n个点，以这些点为端点连互不相交的n条弦，求不同的连法总数．

https://blog.****.net/bjfu170203101/article/details/106039600

这是我刚做的一道题，里面是递推的分析得到的递推式。

下面考虑另一种思路：

把这个2n个点每个点标记为+1或-1.

从一个节点开始顺时针扫描：

把距离最近的+1，与-1连接成边。

如果从起点顺时针扫描出来的序列满足：任意前缀和大于等于0.则所得的n个弦一定是不相交的。（可以类比一下括号序列，每个匹配括号进行连边，一定不会有交点）

所以这又又转化为了问题0.

所以结果为：

6.求凸n+2边形用其n−1条对角线分割为互不重叠的三角形的分法总数．

https://blog.****.net/bjfu170203101/article/details/106039600

其中一种思路类比这道题。