卡特兰数学习笔记

1.定义

设 $f(n)$ 为卡特兰数，则有：

f(n)=\binom{n}{2n}-\binom{n-1}{2n}

存在递推式：

f(n)=\sum_{i=0}^{n-1}\binom i n\binom {n-i-1} n

证明：

\binom{2n}n-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}

2.应用

1.求在网格图从 $(0,0)$ 到 $(n,n)$ 不经过对角线的方案总数。

2.凸多边形的带标号三角剖分数。

3.n个节点构成的完全二叉树数目。

4.n个数进栈的不同出栈次序。

证明：

对于1，所有经过对角线的路线都可以一一映射到 $(n-1,n+1)$ 。

2.还不会证明。

3.可以递归考虑，对于每棵子树，左子树分i个点，右子树必定n-1-i个点。

3.例题

1.P1044 栈

很简单，根据应用4直接做就可以。

注意不要用通项，会爆longlong。

2.[SCOI2010]生成字符串

虽然不是卡特兰数，但运用了类似的思想。

将n+m的串看成由 $(0,0)$ 走到 $(n+m,n-m)$ 的方案数。

这样可以很好的控制n>m的条件，即不经过y=-1。

类似应用1，直接把不合法的映射到 $(0,-2)$ 到 $(n+m,n-m)$ 。

最终答案：

\binom {n+m}{m}-\binom{n+m}{m-1}

Code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=20100403;
ll n,m,fac[2000009],inv[2000009];
inline ll C(ll n,ll m)
{
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int main()
{
	scanf("%lld%lld",&n,&m);
	fac[0]=1;inv[1]=1;
	for(int i=1;i<=n+m;i++) fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=2;i<=n+m;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=n+m;i++) inv[i]=1ll*inv[i-1]*inv[i]%mod;
	printf("%lld",(C(n+m,m)-C(n+m,m-1)+mod)%mod);
	return 0;
}

3.[TJOI2015]概率论

~~大概是恶评题？qwq~~

二叉树数目直接卡特兰数。

问题在于叶子数。

根据_rqy神犇的解释，n个节点树去掉一个叶子可以变成n-1个节点的树。

满足满射。

所以答案为 $\frac {n\times f_{n-1}}{f_n}$ 。

根据通项化简即可。（注释）

#include <bits/stdc++.h>
using namespace std;
long long n;
long double ans;
//n*n*(n+1)÷(2n-1)*2n
int main()
{
	scanf("%lld",&n);
	ans=(long double)n*(n+1)/((2*n-1)*2);
	printf("%.9Lf",ans);
	return 0;
}