卡特兰数

//大制作 # 卡特兰数学习笔记 [安利另一篇可以补充学习的（这篇非常之应试）](https://www.cnblogs.com/adelalove/p/8504778.html) ### 总结 一般运用在输入量很小的数学题，是一种组合数问题的递推题 ### 解题关键 然后记忆卡特兰数的前几项（下标从0开始）:$ f[0]=1 ,f[1]= 1 ,f[2]= 2 ,f[3]= 5 ,f[4]= 14 ,f[5]= 42 ,f[7]= 132 $。 ### 考法 ​ 1.括号化 ​ 2.出栈次序 ​ 3.凸多边形三角划分 ​ 4.给定节点组成二叉搜索树 ​ 5.n对括号正确匹配数目 ### 递推柿子 #### 一.（一般不用来实现，用来推规律） ### $$ h(n)=\Sigma ^{i=0}_{n-1}h(i)*h(n-i-1) $$ ##### 代码实现 ```cpp f[0]=f[1]=1; scanf("%d",&n); for(int i=2;i<=n;i++)//求f[0]~f[n] { for(int j=0;j<i;j++)//公柿 { f[i]+=f[j]*f[i-j-1]; } } printf("%lld",f[n]); ``` ### 二.（最常用） $$ h(n)=C^{n}_{2n}/(n+1) $$ ### 三.（也需要记忆一下） ​ $$ h(0)=1,h(n+1)=\frac{2(2n+1)}{n+2}*h(n) $$ ### 四.（也很常用） $$ f(n)=C^{n}_{2n}-C^{n-1}_{2n} $$ ### 五.(好多时候取模要用) $$f(n)=\frac{(2n)!}{(n+1)!*(n)!}$$ [这个公式有点不熟悉，所以此公式的运用戳这里](https://www.luogu.com.cn/blog/dlp/ti-xie-p1976-ji-dan-bing) ## 应用 #### 一.进出栈问题： #### **栈是一种先进后出（FILO，First In Last Out）的数据结构．如下图1，1,2,3,4顺序进栈，那么一种可能的进出栈顺序是：1In→2In→2Out→3In→4In→4Out→3Out→1Out, 于是出栈序列为1,3,4,2**。 **那么一个足够大的栈的进栈序列为1,2,3,⋯,n时有多少个不同的出栈序列？** 我们可以这样想，假设 $k$ 是最后一个出栈的数。比k早进栈且早出栈的有 $k-1$ 个数，一共有 $h(k-1)$ 种方案。比 $k$ 晚进栈且早出栈的有n-k个数，一共有 $h(n-k)$ 种方案。所以一共有 $h(k-1)h(n-k)$ 种方案.显而易见，k取不同值时，产生的出栈序列是相互独立的，所以结果可以累加。k的取值范围为$1$至$n$，所以结果就为$h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0)$ 变种（排队问题）： 出栈入栈问题有许多的变种，比如n个人拿5元、n个人拿10元买物品，物品5元，老板没零钱。问有几种排队方式。熟悉栈的同学很容易就能把这个问题转换为栈。值得注意的是，由于每个拿5元的人排队的次序不是固定的，所以最后求得的答案要*n!。拿10元的人同理，所以还要*n!。所以这种变种的最后答案为$h(n)*n$!。 #### 二. 二叉树构成问题： **有n个结点，问总共能构成几种不同的二叉树。** 我们可以假设，如果采用中序遍历的话，根结点第k个被访问到，则根结点的左子树有k-1个点、根结点的右指数有n-k个点。k的取值范围为1到n。讲到这里就很明显看得出是卡特兰数了。 #### 三. 凸多边形的三角形划分 ##### 一个凸的n边形，用直线连接他的两个顶点使之分成多个三角形，每条直线不能相交，问一共有多少种划分方案。 #### 结论：对凸n边形进行不同的三角形分割（只连接顶点对形成n个三角形）数为h[n-2] 这也是非常经典的一道题。我们可以这样来看，选择一个基边，显然这是多边形划分完之后某个三角形的一条边。图中我们假设基边是 $p1$ ， $pn$ ，我们就可以用 $p1$、$pn$ 和另外一个点假设为pi做一个三角形，并将多边形分成三部分，除了中间的三角形之外，一边是i边形，另一边是$n-i+1$边形。i的取值范围是$2$到$n-1$。所以本题的解$c(n)=c(2)c(n-1)+c(3)c(n-2)+...c(n-1)c(2)$。令$t(i)=c(i+2)$。则$t(i)=t(0)t(i-1)+t(1)t(i-2)...+t(i-1)t(0)$。很明显，这就是一个卡特兰数了。  ### 四.有n+1个叶子的满二叉树的个数 事实上，向左记为+1，向右记为−1，按照向左优先的原则，从根节点开始遍历．例如第一个图记为+1,+1,+1,−1,−1,−1,于是由卡特兰数的含义可得满二叉树的个数为f(n)。 ##### 如下图 n=4,ans=f(n-1)=f(3)=5  #### 五.括号问题 **结论：n个数入栈后的出栈的排列总数是h[n]** 你有n对括号，即n个左括号，n个右括号，问这些括号有多少种合理的排列方式。 我们可以将应用1变换形式： 将 -1 看成右括号，+1 看成左括号，就变成了左括号和右括号各有n个时，合法括号表达式的个数。 比如2个左括号和2个右括号组成的合法表达式有$h[2]$ = 2种，是()()和(())。 #### 六.平面上连接可以形成凸包(凸多边形)的2n个点分成2个一组连成n条线段，两两线段之间不相交的情况总数是h[n]. 类似的有： （1）在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数 （2）一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ #### 七.对于一个n*n的正方形网格，每次只能向右或者向上移动一格，那么从左下角到右上角所有在副对角线(下图中虚线)右下方的路径总数为h[n] 例子: n=4 h[4]=14  可以将一条水平边记为+1,垂直边记为-1,那么就组成了一个n个+1和n个-1的序列，并且保证前k步中水平边数不小于垂直边数，换句话说前k个元素的和非负。 #### 八.对于集合{1,2,3,.....2*n}，将集合元素两两分为n个子集，若任意两个子集都不交叉，那么我们称此划分为一个不交叉划分。此时不交叉的划分数就是h[n]。 考虑将每个子集中较小的数用左括号代替，较大的用右括号代替，那么带入原来的1至2n的序列中就形成了合法括号问题。 例如集合{1,2,3,4,5,6}的不交叉划分有五个： {{1,2}, {3,4}, {5,6}}， {{1,2},{3,6},{4,5}}， {{1,4},{2,3},{5,6}}，{{1,6},{2,3},{4,5}} 和 {{1,6},{2,5},{3,4}}。 #### 九.在一个2*n的格子中填入1到2n这些数值使得每个格子内的数值都比其右边和上边的所有数值都小的情况数也是h[n]. #### 十.n层的阶梯切割为n个矩形的切法数也是h[n].  # ........ ## 但是，总而言之，这其中有一个最常考的模型 （这篇也挺不错[这个](https://www.luogu.com.cn/blog/user35379/solution-p1641)） ``` 有一个长度为2n的01序列，其中1,0各n个，要求对于任意的整数k ∈ [ 1 , 2 n ]数列的前k个数中，1的个数不少于0的个数 ``` 换一种说法：由 $n$ 个 $+1$ 和$n$个 $-1$ 构成 $ 2n$ 项的数列 $a1,a2,a3,a4.......$ 其部分和满足 $a1+a2+a3+ak>=0$ , $ 0<=k<=2n$ #### 结论:这样的数列个数为h[n]（卡特兰数列的第n项） 我们把0,1操作扔到一个坐标系中。1看成向右上方走一步，0看成向右下角走一步，那么最后构造完后一定走到了 $(2*n,0)$ 如下图：  那么总的路径数量就是在2n步中选择n步为1，方案数为 $$ C^n_{2n} $$ 接着来考虑题目中的限制条件：对于任意前缀，1的个数不少于0。 那么转化到坐标系中，也就是说走的路径不应该穿过x轴，即直线$ y=0$，也就是不接触 $y= -1$。 于是我们把与y=-1的接触点的右边整条路径以$ y= -1$为对称轴翻折，于是终点变为了 (2n,-2)。 **为什么可以这样？** **或者这样做的目的是什么？** 与y=-1交点C的后一步即与y=0的交点（4,0）以后0,1个数是相等的，所以翻折后0,1总个数不变。 ##### But 对于（3，-1）到（4,0）这一步1操作来说，将1操作变成了0操作。 如下图：  那那么此时的路径数量即为总路径数中不符合题意的路径数，那么我们用总路径数减去不符合的路径数，就是最终的答案。 而此时的路径数量也很简单，因为将n步1操作中的1次转化成0操作，所以也就是一共有n-1个1,方案数为 $$ C_{2n}^{n-1} $$ ##### 所以总方案数就是 $$ C^n_{2n}-C_{2n}^{n-1} $$ #### 诶，这不就是卡特兰数吗? # 十分之重要： **一般是将与y=-1的交点到原点的函数对称，这样要好求一点** ### 例题 0. [小猫（板板题）](https://www.luogu.com.cn/problem/P1375) 1. [洛谷1641 生成字符串](https://www.luogu.org/problemnew/show/P1641) 2. [Loj10238网格](https://loj.ac/problem/10238) 这两道题需要在深刻理解了上述卡特兰数的推导后进行一些变形得出最终的答案。 具体的变动在于，转换成基本模型后，1和0的个数不一样，分别为 $n$ 和 $m$ ，最后可以得出答案为 $$ C^n_{n+m}-C^{m-1}_{n+m} $$ 白水一道紫题。 3. [洛谷P2532 树屋阶梯](https://www.luogu.org/problemnew/show/P2532) ~~这道题我一看两军阵前……，跟卡特兰数好像没有直接关系~~,但是手画几个样例后，发现答案都是卡特兰数，那么基本上就可以大胆猜想了。 但实际上，我们可以从 $dp$ 的角度考虑这道题。对于任意大小为 $n$ 的阶梯，我们都可以现在左下角放一个大块，然后在上方构造一个大小为 $i$ 的阶梯，右下方构造大小为 $n − i − 1$ 的阶梯，那么转移方程就十分显然： $$ f(n)=\Sigma^{n-1}_{i=0}f(i)*f(n-i-1) $$ 显然就是卡特兰数，直接一波通项式+高精度搞定。 4. [洛谷P3200 有趣的数列](https://www.luogu.org/problemnew/show/P3200) 首先有一个结论，对于每个偶数位，上面放的数必须不小于当前位的下标。（意会一下） 转化一下题意：把 $1~2n$ 这些数依次放入序列，每次可以选择最后的奇数位或偶数位。 然后再观察后发现一个显然的性质：**对于任意时刻，数列中的奇数位数量不能少于偶数位数量**。否则偶数位上放的数不可能大于等于下标。 于是，这就是一个卡特兰数模板，通项式秒切。具体对于组合数的处理，可以参看各种题解。 # 总结 [点击](https://www.luogu.com.cn/blog/dlp/bu-chong-p1641-post) # 完结撒花