WIKI

卡特兰数

卡特兰数 是一个数列

通项公式为
$$ C_n=\frac 1 {n+1}\binom{2n}{n}\quad n\in N $$
卡特兰数有三种计算方式
$$ C_n=\frac 1 {n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n+1}=\binom{2n}{n-1} $$

$$ C_n=C_0C_n-1+C_1C_{n-2}+\dots+C_{n-2}C_1+C_{n-1}C_0=\sum\limits_{k=0}^{n-1}C_kC_{n-k}\quad C_0=1 $$

$$ C_n=\frac {4n-2}{n+1}C_{n-1} ,C_0=1 $$

那么这个东西的用途是什么呢

棋盘问题

一个 $n$ 行 $n$ 列的棋盘，从左下角 走到右上角， 始终保持在对角线右下方走，不穿过主对角线的走法有多少种

$n=4$ 时 ，答案为$14$

设向上走为0 ，向右为1

总路线数为在$2n$ 个位置放 $n$ 个$1$ 的方案数
$$ X_n=\binom{2n}{n} $$
求越界的方案数

如果越界了，那么一定是向上越过分界线

那么将分界线向上 平移一格使得现在的位置落在分界线上

终点变为(n-1,n+1)

越界的方案数为$Y_n=\binom{2n}{n-1}$

所求方案数为
$$ C_n=X_n-Y_n=\binom{2n}{n}-\binom{2n}{n-1} $$

AHOI2012 树屋阶梯

think

因为只有$n$ 个阶梯,而且有 $n$ 个拐角, 那么一定是 一个阶梯对应一个拐角,

然后我们枚举从左下角的矩形覆盖到了哪个拐角

我们发现枚举完以后变成了两个小任务

然后我们就可以推出公式
$$ C_n=C_0C_n-1+C_1C_{n-2}+\dots+C_{n-2}C_1+C_{n-1}C_0=\sum\limits_{k=0}^{n-1}C_kC_{n-k}\quad C_0=1 $$
然后就是卡特兰数了

因为涉及到高精度所以写的python

code

n=int(input())
C=[0]*(n+1)
C[0]=1
for i in range(1,n+1):
    r=i-1
    for l in range(0,i):
        C[i]+=C[l]*C[r]
        r-=1
print(C[n])