数论之卡特兰数

2020 年 12 月 1 日
筆記
数论

1、基本模型

有一个长度为 $2n$的$01$序列，其中$1,0$各 $n$个，要求对于任意的整数 $k \in [1,2n] $，数列的前 $k$个数中，$1$的个数不少于$0$

满足条件的序列的数量为

\[Cat_n=\frac{C_{2n}^n}{n+1}
\]

另一种形式

\[Cat_n=C_{2n}^n-C_{cn}^{n-1}
\]

又一种形式

\[Cat(n)=\frac{1}{n+1}\sum_{i=0}^n{C_n^i}^2
\]

递推式

\[Cat_n=\sum_{i=0}^{n-1}Cat_i \times Cat_{n-i-1}
\]

\[Cat(n+1)=\frac{2(2n+1)}{n+2}Cat(n)
\]

2、证明

主要是运用了翻折的思想

传送门

可以通过这种方法得出更为普遍的结论

比如这道题

3、推论

以下问题都与卡特兰数有关

$1$、$n$个左括号和$n$个右括号组成的合法括号序列的数量为$Cat_n$

$2$、$1,2,…,n$经过一个栈，形成的合法出栈序列的数量为$Cat_n$

$3$、$n$个节点构成的不同二叉树的数量为$Cat_n$

$4$、在平面直角坐标系上，每一步只能向上或向右走，从$(0,0)$走到$(n,n)$并且除两个端点外不接触直线$y=x$的路线数量为$2Cat_n-1$

$5$、对凸 $n+2$ 边形进行不同的三角形分割的方案数(分割线断点仅为顶点，且分割线仅在顶点上相交)

$6$、$n$ 层的阶梯切割为 $n$ 个矩形的切法数

4、解题思路

$1$、通过递推式得到卡特兰数

比如这道题

$2$、可以将题目转化为卡特兰数的模型

比如这道题

$3$、还可以找规律

卡特兰数的前几项:$1,1,2,5,14,42,132$

5、一些技巧

卡特兰的题目有很多需要高精度，建议学习一下我的高精度板子

还有一些题目给出的模数不是质数

我们可以把模数分解质因数，求出在模每一个质数下的答案，再用中国剩余定理和到一起

但是还有一种更简单的方法

因为分子比分母中一定存在数量更多的(或一样多)的因数 $p$

于是可以分别算出分子和分母中含有的某个质数 $p$ 的指数是多少

再用上面的指数减去下面的指数，做一个快速幂就行了

求 $n!$ 中 $p$ 的指数

int cnt=0;
while(n){
	n/=p;
	cnt+=;
}

Tags: 数论