从这节开始，我们遇到的组合数可能会比较大，大到long long存不下，那怎么办？c++大数板子欢迎你...c++大数板子有好多版本，自己写的舒服直接保存下来备用即可，这里我不再提供，不过，这里我给大家准备了Java大数运算的简单代码，Java自带大数运算这个实属良心之举，可以关注我博客，传送门，只是简单介绍哦，深入探讨咨询度娘。
开始正题，Catalan数是一组比较神奇的数字1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670,不要小看这组数字，他的神秘之处在于：我们记C[n]为Catalan数列第n+1个数，从0开始，也就是说C[0] = 1 , C[1] = 1 , C[2] = 2 ... 结果你会发现：
- 1 如果序列1，2，...，n入栈，那么C[n] 就是这组数字出栈的排列种数，也就是对应的Catalan数。
- 2 对一个有N + 2 条边的凸多边形(N>=1)用连接顶点的不相交对角线将该多边形拆分成若干三角形，那么C[n]就是拆分的方法数，也就是对应的Catalan数。
- 3 具有n个节点的二叉树有多少种呢？C[n]个，也就是对应的Catalan数。
- 4 给出n对括号，括号正确配对的字符串个数就是C[n]对应的Catalan数。
- 更多Catalan数的应用可以查询百度。
那么重点来了，既然Catalan数这么神奇，这Catalan数有什么共性呢？其实是有的:
Catalan数的计算公式是 C[0] = 1 , C[1] = 1 , C[n] = C[0] * C[n-1] + C[1] * C[n-2] + C[2] * C[n-3]+....+C[n-1] * C[0].
Catalan数的递推公式为C[n] = C[n-1](4n-2)/(n+1)，这样我们就可以愉快的递推了。
这里我选择将入栈数这个应用讲一下证明，其它的应用，大家也可以在百度上找到，网上关于这些的博客也有很多，我就不一一讲解了，其实我自己也并不掌握很好，避免误人子弟（😜逃....
🙂N个数出栈排列数的证明
设C[n]是序列1，2....N入栈后，出栈的排列数。显然，C[0] = 1 C[1] = 1 C[2] = 2 ; 对于C[n] (n>=2) 如果第一个出栈的数是K，则K这个数字将序列1.....N分成两个子序列：序列1....K-1(长度为K-1，已经入栈) 和序列 K+1.....N(长度为N-K，尚未入栈)，则由乘法原理，如果第一个出栈数是K，则出栈的排列数为F[k] = C[k-1] * C[n-k]；，因为1<=K<=N,则N个数总的排列方法为K从1取值到N，即F[1]+F[2].....+F[N] ；即C[N] = C[0]C[n-1]+C[1]C[n-2]+....+C[n-1]*C[0]；即Catalan数的公式。
码到这里累死我了.....😣.....插播一条广告吧：有没有对机器学习，物联网，大数据，云计算感兴趣的童鞋，我有个交流群，想把它建设起来，大家来助力哇，有想法的私聊我，咱们大二大三的时候一块做项目😊
广告之后，马上回来，接下来，我给出一道Catalan数列应用的题，大家看一下：
题面：
这是一个很小但是很古老的游戏。请您以顺时针顺序在地上写下连续的数字：1，2，3.....2N-1，2N。这2N个数字形成一个圆圈；然后，你来画一些线段，将这些书连接成整数的数对，每一个数都要连到另一个数字上，而且没有两个线段是相交的。这是个简单的游戏是不是？当您写完这些数字的时候，您来告诉大家，对于输入的N可以有多少种不同的方式将这些数字连成数对？（1<=N<=100）
解析
先确定一个点，然后枚举其它的点P与这个点相连，构成一条线段，保证这条线段把所有的点分成两部分，且都是偶数个，也就是整数对个。那么这样的点P有N个，（到时候我可以画图演示，这里不懂现在可以私聊我），设这条线段左边有i对点，那么这条线段左边的点的连接方法数就有C[i]种，而线段右边有n-i-1对点，（因为有一条线段已经连接了一对点，所以剩下n-1对点，也就是2*n-2个点），所以我们可以得到递推公式：C[n] = C[i] * C[n-i-1] ( i从0到n-1) , 而这一递推公式正是Catalan数的递推公式。
为了提高效率，我们先离线计算出前110个Catalan数来，由于Catalan数的上限超过了long long的范围，所以我们得采用用高精度计算了。
Java高精度简单学习👉传送门
Java代码：
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String []args){
Scanner in = new Scanner(System.in);
int k = in.nextInt();
while(k!=-1){
BigInteger a,b;
a = BigInteger.valueOf(1);
b = BigInteger.valueOf(1);
for(int i = 2; i <= k; i++) {
b = a.multiply(BigInteger.valueOf(4*i-2));
b = b.divide(BigInteger.valueOf(i+1));
a = b;
}
System.out.println(b);
k = in.nextInt();
}
in.close();
}
}
其实无非就是用了一个递推公式C[n] = C[n-1](4n-2)/(n+1)，这是Catalan数的递推公式，问题在于大数运算，如果选择Java的话，在程序编写上应该就比较轻松。
注意，这里只是简单介绍了Catalan数列，如果深入研究可以参考其他大牛的Blog，深入探讨已经超出了我这个组合数学小白的能力（菜是原罪）。有问题可以私聊我，欢迎指正，谢谢啦...
大家对于Catalan数列其它应用的理解也可以找我讨论，仅讨论而已😀
网友评论