Catalan number
**Catalan number，卡特兰数又称卡塔兰数，**是组合数学中一个常出现在各种计数问题中出现的数列。
卡特兰数的前几个数
前20项为（OEIS中的数列A000108）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 176726319
排队买票问题(出栈次序问题)：
一个栈(无穷大)的进栈序列为1,2,3,…n,有多少个不同的出栈序列?
有2n个人排成一行进入公园。入场费1元。其中只有n个人有一张1元钞票，另外n人只有2元钞票，剧院无其它钞票，问有多少中方法使得只要有2元的人买票，售票处就有1元的钞票找零？(将持1元者到达视作将1元入栈，持2元者到达视作使栈中某1元出栈)
不难看出，该题求的是左端点为首元素的任意区间内，1的个数大于等于2的个数。
方法一：折现法
可以认为问题是，任意两种操作，持1元者买票是操作一，持2元买票者是操作二。要求每种操作的总次数一样，且进行第k次操作2前必须先进行至少k次操作1。我们假设一个人在原点，操作1是此人沿右上角45°走一个单位（一个单位设为根号2，这样他第一次进行操作1就刚好走到（1,1）点），操作2是此人沿右下角45°走一个单位。第k次操作2前必须先进行至少k次操作1，就是说明所走出来的折线不能跨越x轴走到y=-1这条线上！在进行n次操作1和n此操作2后，此人必将到到达（2n，0）！若无跨越x轴的限制，折线的种数将为C（2n，n），即在2n次操作中选出n次作为操作1的方法数。
现在只要减去跨越了x轴的情况数。对于任意跨越x轴的情况，必有将与y=-1相交。找出第一个与y=-1相交的点k，将k点以右的折线根据y=-1对称（即操作1与操作2互换了）。可以发现终点最终都会从（2n，0）对称到（2n，-2）。由于对称总是能进行的，且是可逆的。我们可以得出所有跨越了x轴的折线总数是与从（0,0）到（2n,-2）的折线总数。而后者的操作2比操作1要多0-（-2）=2次。即操作1为n-1,操作2为n+1。总数为C（2n，n-1）。
这个证明的关键就是最终一定会到达（2n,0)这个点。
对于不满足情况的方案，它一定会越过y=-1，捉住这个特点，我们可将求不合法的方案数这个问题换个说法来：从（0，0）到（2n,-2)一共有多少种走法？这个走法数就是C(2n,n-1)因为走右下角的要多走2步，同时一共只走2n步，那就右下角走n+1步，方案法就是2n选n-1.
合法数=C(2n,n)-C(2n,n-1);
Cn= 拥有 n+1 个叶子节点的二叉树的数量。例如 4个叶子节点的所有二叉树形态：卡特兰数 -
矩阵连乘：P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
答案：f(n)=h(n-1)
分析：可以这样考虑，首先通过括号化，将P分成两个部分，然后分别对两个部分进行括号化。比如分成(a1)×(a2×a3……×an)，然后再对(a1)和(a2×a3……×an)分别括号化；又如分成(a1×a2)×(a3……×an)，然后再对(a1×a2)和(a3……×an)括号化。设n个矩阵的括号化方案的种数为f(n)，那么问题的解为
f(n)=f(1)∗f(n−1)+f(2)∗f(n−2)+f(3)∗f(n−3)+f(n−1)∗f(1)f(n)=f(1)∗f(n−1)+f(2)∗f(n−2)+f(3)∗f(n−3)+f(n−1)∗f(1)
f(1)*f(n-1)表示分成(a1)×(a2×a3……×an)两部分，然后分别括号化。计算开始几项，f(1) = 1, f(2) = 1, f(3) = 2,f(4)=5。结合递归式，不难发现 f(n)等于h(n-1)
出栈次序
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
答案：f(n)=h(n)
分析：首先，我们设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递归式。而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为：f（n）=f（0）f（n-1）+f（1）f（n-2）+……+f（n-1）f（0）。看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n）= C（2n,n）/（n+1）= c（2n,n）-c（2n,n-1）（n=0，1，2，……）。最后，令f（0）=1，f（1）=1。
凸多边形三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f(6)=14。
答案：f(n)= h(n-2)
分析：因为凸多边形的任意一条边必定属于某一个三角形，所以我们以某一条边为基准，以这条边的两个顶点为起点P1和终点Pn（P即Point），将该凸多边形的顶点依序标记为P1、P2、……、Pn，再在该凸多边形中找任意一个不属于这两个点的顶点Pk（2<=k<=n-1），来构成一个三角形，用这个三角形把一个凸多边形划分成两个凸多边形，其中一个凸多边形是由P1，P2，……，Pk构成的凸k边形（顶点数即是边数），另一个凸多边形是由Pk，Pk+1，……，Pn构成的凸n-k+1边形。
此时，我们若把Pk视为确定一点，那么根据乘法原理，f（n）的问题就等价于——凸k多边形的划分方案数乘以凸n-k+1多边形的划分方案数，即选择Pk这个顶点的f（n）=f（k）×f（n-k+1）。而k可以选2到n-1，所以再根据加法原理，将k取不同值的划分方案相加，得到的总方案数为：f（n）=f（2）f（n-2+1）+f（3）f（n-3+1）+……+f（n-1）f（2）。看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n-2）（n=2，3，4，……）。此处f（2）=1和f（3）=1的具体缘由须参考详尽的“卡特兰数”。
类似问题一：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
答案：f(2n)= h(n)
分析：以其中一个点为基点，编号为0，然后按顺时针方向将其他点依次编号。那么与编号为0相连点的编号一定是奇数，否则，这两个编号间含有奇数个点，势必会有个点被孤立，即在一条线段的两侧分别有一个孤立点，从而导致两线段相交。设选中的基点为A，与它连接的点为B，那么A和B将所有点分成两个部分，一部分位于A、B的左边，另一部分位于A、B的右边。然后分别对这两部分求解即可。
设问题的解f(n)，那么
f(n)=f(0)∗f(n−2)+f(2)∗f(n−4)+f(4)∗f(n−6)+…f(n−4)∗f(2)+f(n−2)∗f(0)f(n)=f(0)∗f(n−2)+f(2)∗f(n−4)+f(4)∗f(n−6)+…f(n−4)∗f(2)+f(n−2)∗f(0)
f(0)*f(n-2)表示编号0的点与编号1的点相连，此时位于它们右边的点的个数为0，而位于它们左边的点为2n-2。依次类推，f(0) = 1, f(2) = 1, f(4) = 2。结合递归式，不难发现f(2n) 等于h(n)。
类似问题二：Cn=n*n的方格地图中，从一个角到另外一个角，不跨越对角线的路径数？例如，4×4方格地图中的路径有14条：
答案：f(2n)= h(n)
类似问题三：圆桌周围有2n个人，他们两两握手，但没有交叉的方案数？
答案：f(2n)= h(n)
二叉搜索树个数
给定N个节点，能构成多少种不同的二叉搜索树？
答案：f(n)= h(n)
作者：BugFree_张瑞
来源：****
原文：https://blog.****.net/u011489043/article/details/77884434
版权声明：本文为博主原创文章，转载请附上博文链接！