Catalan数列

2020-08-04 本文已影响0人 dachengquan

Catalan数列
给定n个0和n个1，它们按照某种顺序排列成长度为2n的序列，满足任意前缀和中0的个数都不少于1的个数的序列的数量为：
$H_n = \frac {C^n_{2n}} {n+1}$
证明：
令n个0和n个1排成的序列，如果某个位置p前，1的数量等于0的数量+1那么将p+1到2n进行取反整个序列变为n+1个1和n-1个0。
对于任意的n+1个1和n-1个0组成的序列，如果前1到p中1的数量等于0的数量+1，那么将后面的去翻。得到的整个序列就是n个1和n个0排列的某个序列
所以二者一一对应。根据多重集的全排列可知，n个0，n个1排列有 $C^{n}_{2n}$ ,n-1个0，n+1个1有 $C^{n-1}_{2n}$
$H_n = C^{n}_{2n} - C^{n-1}_{2n} = \frac {C^n_{2n}} {n+1}$

在来看看其他递推公式
1. $H_n=\sum _{i=1}^{n}H_{i-1}*H_{n-i}$
2. $H_n=\frac {H_{n-1}*{(4*n-2)}} {n+1}$

先看第一个递推公式，我们能够确定数列中第一个数一定0。找到一个位置2*i，使得1~2*i里面的0的个数等于1的个数。我们知道序列第一个是0，第2*i个是1。其他的2*i-2位方案数通过子问题 $H_{i-1}$ 就可以知道。从第2i+1位到第2n位又是一个子问题 $H_{n-i}$ 。以第i位为分界点的卡特兰数就是 $H_{i-1}*H_{n-i}$
只要枚举每个位置i就可以求出第n个卡特兰数 $H_n=\sum _{i=1}^{n}H_{i-1}*H_{n-i}$
其中 $H_0=H_1=1$

第二个递推公式
$H_n = \frac {C^n_{2n}} {n+1}$
单独看 $C^n_{ 2n }$
$C^n_{ 2n } = {\frac {(2n)!} {n!*n!}} = \frac {(2n)*(2n-1)} {n} * \frac {\frac {(2n-2)!} {(n-1)!*(n-1)!} } n$
$=H_{n-1}*(4n-2)$
有了这个公式计算卡特兰数只需要一行代码

f[0]=1
for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);

通过上面求解第二个递推式的过程可以发现这个式子是成立的 $C^m_{ n } = \frac n m *C^{m-1}_{n-1}$

Catalan数列

猜你喜欢

热点阅读