卡特兰数

先上一个超级强的大佬的博客，蒟蒻表示以前一直看不懂卡特兰数，但是这个博客讲的很好，豁然开朗

[传送门](http://blog.sina.com.cn/s/blog_6917f47301010cno.html)

然后这个博客举的具体例子很多：

[传送门](https://blog.****.net/wu_tongtong/article/details/78161211)

一、首先是卡特兰数出现的目的：卡特兰数求的是“n个数的进栈出栈序列”？“凸多边形的三角形分割”？“n×n的矩阵中不走过对角线且只能向右或向上走，从左下角走到右上角的方案数”？大概这些问题都有一些奇妙的同性，所以膜♂法师卡特兰就提出了卡特兰数

二、卡特兰数的前几位：1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

记个前几位，以后手膜的时候要是看到14啊，42啊，132啊，就往卡特兰数上面凑。

三、组合数求法

公式：Catalan(n) = C(2n, n) - C(2n, n-1) = C(2n, n)/(n+1)

                                                                

证明用折线法：我们假设入栈是向右上走，出栈是向右下走，那么保证任何时候入栈多于出栈即保证折线不越过x轴。Catalan(n)就是从(0, 0)走到(2n, 0)，看第一篇博客大佬的图

首先如果没有“不超过x轴”的限制，方案数是C(2n, n)，即从2n个操作中取出n个向右上的，剩余就是右下。

然后要去掉跨越了x轴的，再看图：

所有跨越了x轴的折线可以保证在某一个前缀，向右上走了m次，向右下走了m+1次，走到了(2m+1, -1)（如上图k点）。然后我们把k点后面的折线关于y = -1 对折，即把k点后面的向右上的变成了向右下的，向右下的变成了向右上的，现在跨越x轴的折线变成了从(0, 0) 走到(2n, -2)的折线，包含n-1次向右上的操作和n+1次向右下的操作，方案数C(2n, n-1)。

那么最后总方案数就是C(2n, n) - C(2n, n-1) 。而从C(2n, n) - C(2n, n-1)转化到C(2n, n)/(n+1)只需要稍微推一波就好了。

四、递推求法

公式：h(0) = h(1) = 1 (n <= 2)

          h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)

据说那些应用都是因为递推式和卡特兰数一样，所以才py和卡特兰数扯上了关系。

再拿出栈序列举个例子：首先，我们设f（n）=序列个数为n的出栈序列种数。（我们假定，最后出栈的元素为k，显然，k取不同值时的情况是相互独立的，也就是求出每种k最后出栈的情况数后可用加法原则，由于k最后出栈，因此，在k入栈之前，比k小的值均出栈，此处情况有f(k-1)种，而之后比k大的值入栈，且都在k之前出栈，因此有f(n-k)种方式，由于比k小和比k大的值入栈出栈情况是相互独立的，此处可用乘法原则，f(n-k)*f(k-1)种，求和便是Catalan递归式。ps.author.陶百百）

哇，看起来非常厉害！水题去了！