卡特兰数
定义
卡特兰数的定义就是形如 1 , 2 , 5 , 14 , 42 , 132... 1,2,5,14,42,132... 1,2,5,14,42,132...的序列的几种公式，包括组合数递推等形式：
- f ( n ) = C 2 n n n + 1 = C 2 n n − C 2 n n − 1 , n ≥ 1 f(n)= \frac{C_{2n}^n}{n+1}=C_{2n}^{n}-C_{2n}^{n-1},n \geq 1 f(n)=n+1C2nn=C2nn−C2nn−1,n≥1（证明从组合数计算公式下手）
- f ( n ) = ∑ i = 0 n − 1 f ( i ) ∗ f ( n − i − 1 ) f(n)=\sum_{i=0}^{n-1} f(i)*f(n-i-1) f(n)=∑i=0n−1f(i)∗f(n−i−1)
- f ( n + 1 ) = f ( n ) ∗ ( 4 n − 6 ) n , f ( 2 ) = 1 , n ≥ 2 f(n+1)= \frac{f(n)*(4n-6)}{n},f(2)=1,n \geq 2 f(n+1)=nf(n)∗(4n−6),f(2)=1,n≥2
计算
递推法
ll a[1005];
ll solve(int n){
a[0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++){
a[i]+=(a[j]*a[i-1-j])%Mod;
a[i]%=Mod;
}
return a[n];
}
组合数法
ll C[1005][1005];
ll cal(int n){
C[0][0]=1;
for(int i=1;i<1005;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<=(i>>1);j++){
C[i][j]=C[i][i-j]=(C[i-1][j-1]+C[i-1][j])%Mod;
}
}
return (C[2*n][n]-C[2*n][n-1]+Mod)%Mod; //不要忘记减法的取模
}
线性求法
ll f[maxn],inv[maxn];
ll solve(int n,int p){ //p是取模的数
f[2]=inv[1]=1LL;
for(int i=2;i<n+2;i++) //线性求i的逆元
inv[i]=(p-p/i)*inv[p%i]%p;
for(int i=2;i<n+2;i++)
f[i+1]=(4*i-6)*f[i]%p*inv[i]%p;
return f[n+2];
}
应用
建议参考紫书和B站此视频，以及此博客
- n n n个节点的二叉树形态个数
- n n n对括号的匹配个数问题
- n n n个数入栈后出栈的排列总数
- 对凸 n + 2 n+2 n+2边形进行三角剖分的方案个数
- n × n n×n n×n的网格中从 ( 1 , 1 ) (1,1) (1,1)走到 ( n , n ) (n,n) (n,n)且不越过第一象限平分线的移动方案数