卡特兰数

lihp2020

卡特兰数  在组合原理   好像 就两种
1  在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数
按这个方法
先随便把一个凸多边形 切开 分成左右两个多边形  左右两个 又是满足互不相交的对角线
算的结果 有个递推公式h(n) = h(1)*h(n-1) +h(2)*h(n-2) + ... + h(n-1)h(1)，n>=2
再利用生成函数  和生成函数的平方 求解 还有牛顿二项式定理 能得到
(1/n+1)C（n ,2n)

这个知识点 理解还是很好理解 就是计算过程的操作比较6  求一般表达式 也只是只是背诵的流程
2 n个1和n个-1组成一个2n位的数列，要求从左到右扫描，任意位求和>0，试求满足这条件的数有多少
这个方法是 容斥原理 全排列 减去不符合条件的  
结果是C（n ,2n)-C（n+1 ,2n)=(1/n+1)C（n ,2n)
这个知识点 有条 "一个不合要求的数对应于一个由n－1个1和n+1个-1组成的一个排列"  
反正 这个知识点是过背诵的 我才疏学浅 一直理解不透 为啥一一对应

两种方法 都有不同的复杂度
我在想 有没有一个很牛X的解释
由于有除法  是否 对于任意序列  都能转换成一个唯一的 卡特兰序列 其中这样的一般序列有n+1个  都是转换成同1个卡特兰序列
或者一个 卡特兰序列 通过转换 可以生成 n+1个序列  这个序列的所有 就是一个任意序列？

我只是想想   有没有这样是可不可以更简单的