卡特兰数解析

卡特兰数定义 公式C01, Cn∑k1nCk−1⋅Cn−k(n0)C_01,\,C_n\sum_{k1}^{n}C_{k-1}\cdot C_{n-k}(n0)C0​1,Cn​∑k1n​Ck−1​⋅Cn−k​(n0)。但是如果按照定义硬算的话就会很慢所以我们必须用到一些更简便的公式。通项公式Cn1n1(2nn)(2nn)−(2nn1) (n≥0)C_n\frac{1}{n1}\binom{2n}{n}\binom{2n}{n}-\binom{2n}{n1}\,(n\ge0)Cn​n11​(n2n​)(n2n​)−(n12n​)(n≥0)。递推式Cn4n−2n1Cn−1 (n≥1), C01C_n\frac{4n-2}{n1}C_{n-1}\,(n\ge1),\,C_01Cn​n14n−2​Cn−1​(n≥1),C0​1。公式证明作为数学爱好者可以学一下如果只是打 cp 没必要了。。。应用路径计数我们设AnA_nAn​表示在一个n×nn\times nn×n的矩阵里面每步可以向右或者向上从(0,0)(0,0)(0,0)走到(n,n)(n,n)(n,n)有几种走法。但有一个限制必须要在yxyxyx这条对角线的下方可以碰到这条直线但是不能超过它。如下图我们假设这条路径第一次碰到对角线的位置是(k,k)(k,k)(k,k)。那么这条路径就分为两个部分一个深蓝色的部分相当于在一个k×kk\times kk×k的矩阵里走路但是不能碰到对角线另一个暗红色的部分相当于在一个(n−k)×(n−k)(n-k)\times (n-k)(n−k)×(n−k)的矩阵里走路。只需要求∑k1n[从 (0,0) 走到 (k,k)但不能碰到对角线的方法数]⋅An−k\sum_{k1}^{n}[从\,(0,0)\,走到\,(k,k)但不能碰到对角线的方法数]\cdot A_{n-k}∑k1n​[从(0,0)走到(k,k)但不能碰到对角线的方法数]⋅An−k​即可。考虑怎么算[从 (0,0) 走到 (k,k)但不能碰到对角线的方法数][从\,(0,0)\,走到\,(k,k)但不能碰到对角线的方法数][从(0,0)走到(k,k)但不能碰到对角线的方法数]第一步一定是往右走最后一步一定是往上走。因为如果你从(0,0)(0,0)(0,0)开始往上走就超过了对角线如果最后一步是向右走到达(k,k)(k,k)(k,k)的就证明你走到过(k−1,k)(k-1,k)(k−1,k)超过了对角线。既然这两步绿色是确定的就只看剩下的蓝色部分由于在(k,k)(k,k)(k,k)之前路线没有碰到过k×kk\times kk×k的矩阵的对角线所以可以直接把对角线向下移动一格发现问题变成了在一个(k−1)×(k−1)(k-1)\times(k-1)(k−1)×(k−1)的矩阵里正常行走可以碰对角线。所以得出答案就是Ak−1A_{k-1}Ak−1​。那么递推式就是An∑k1nAk−1⋅An−kA_n\sum_{k1}^{n}A_{k-1}\cdot A_{n-k}An​∑k1n​Ak−1​⋅An−k​而初始值就是A01A_01A0​1。发现这与卡特兰数的定义刚好一样可以套用公式计算。拓展括号序列问题长度为2n2n2n的合法括号序列有几种将左括号看成向右走x1x1x1右括号看成向上走y1y1y1。要使序列合法在整个序列的每一个位置上在此位置之前的左括号数量必须要大于等于右括号数量也就是x≥yx\ge yx≥y并且最后左括号数量要等于右括号数量也就是xynxynxyn。这本质上和上面的问题是一样的因为对角线上以及它下面的点都满足y≤xy\le xy≤x而其他点不满足起点(0,0)(0,0)(0,0)代表什么括号都没加入终点(n,n)(n,n)(n,n)刚好是我们想要到最终状态有nnn个左括号nnn个右括号。拓展出栈序列问题依次向栈中加入1,2,…,n1,2,\dots,n1,2,…,n有多少种合法的出栈序列这个问题也和走方格一样就是每一个时刻出栈次数小于等于入栈次数将出栈当成向上入栈当成向右走即可。圆内不相交弦计数问题圆上有2n2n2n个点求将这些点成对连接起来且使得所得到的nnn条线段两两不交的方案数。在拉了一条直线之后就会把圆变成左右两半且在不同半的点不能互相连线否则就会与中间的线交叉。两半的点数一定都是偶数左半边点的对数是kkk则0≤k≤n−10\le k\le n-10≤k≤n−1这2k2k2k个点变成了一个独立的问题它们之间可以在满足不交叉的情况下连线另外一半有2n−2k−22n-2k-22n−2k−2个点也是一个独立的问题。如果圆上的nnn对点点数为2n2n2n的连线方法数是TnT_nTn​那么Tn∑k0n−1Tk⋅Tn−k−1T_n\sum_{k0}^{n-1}T_k\cdot T_{n-k-1}Tn​∑k0n−1​Tk​⋅Tn−k−1​和卡特兰数的定义是一样的。简单总结一下就是如果这个问题可以递归那么就推出递归的式子看看能不能用卡特兰数便利地计算。