2019-12-07 08:27 C++

关注

组合数学总结

I.组合数

1.定义：用 $\displaystyle \binom{n}{m}$ 表示 $n$ 个物品选 $m$ 个（不排序）的方案数。

2.性质：

1> $\displaystyle \binom{n}{m}=\binom{n}{n-m}$

2> $\displaystyle \binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$

3> $\displaystyle \sum_{i=m}^{n+m}\binom{i}{m}=\binom{m+n+1}{m+1}$ （证明：利用性质2）

$\displaystyle \frac{7}{2}$ > $\displaystyle \sum_{i=l}^{r}\binom{i}{m}=\binom{r+1}{m+1}-\binom{l}{m+1}$ （性质3的扩展）

4> $\displaystyle \sum_{i=0}^{n}\binom{n}{i}=2^n$

3.求法：

1>递推。使用性质2， $O(N^2)$ 。
2>Lucas定理。适用于%一个质数 $p$ 的情况， $\displaystyle \binom{n}{m}=\binom{n\mod p}{m\mod p}\cdot\binom{n/p}{m/p}$ ，注意其中 $\displaystyle \binom{n/p}{m/p}$ 还可以再分。
3>扩展Lucas定理。将模数 $p$ 分解为 $\displaystyle \prod_{i=1}^{k}{b_i}^{e_i}$ ，就只需要求 $\displaystyle \binom{n}{m}\mod {b_i}^{e_i}$ ，然后用CRT合并即可。

II.第一类斯特林（Stirling I）数

1.定义：用 $[^n_k]$ 表示把 $n$ 个不同物品分成 $k$ 个圆排列的方案数，亦写作S1[n,k]。

2.递推式： $[^n_k]=[^{n-1}_{k-1}]+(n-1)\cdot[^{n-1}_k]$

$\displaystyle \frac{5}{2}$ .分析：
1>在一个圆圈里只有编号为n的人。排法有 $[^{n-1}_{k-1}]$ 个。
2>n至少和另外一个人在一个圆圈里。这些排法可以通过把1，2.....n-1排成k个圆圈，再把n放在1，2，......，n-1任意一个人的左边。因此，第二种类型的排法有 $(n-1)\cdot[^{n-1}_k]$ 种。

III.第二类斯特林（Stirling II）数

1.定义：把 $n$ 个物品分成 $k$ 个集合的方案数叫第二类斯特林数，用{ ${^n_k}$ }表示。其中 $n$ 个物品互不相同， $k$ 个集合相同。亦写作S2{n,k}。

2.递推式：{ ${^n_k}$ } $=$ { ${^{n-1}_{k-1}}$ } $+k\cdot$ { ${^{n-1}_k}$ }

$\displaystyle \frac{5}{2}$ .分析：略，同第一类斯特林数。

IV.卡特兰（Catalan）数

1.定义：
1>有 $n$ 对括号的合法括号序列匹配方案数。
2> $1$ ， $2$ ，...， $n$ 顺次入栈，出栈序列方案数。
3>边数为 $n+2$ 凸多边形三角划分方案数。
4> $n$ 个节点的二叉树种数。

2.求法：
1>递推。 $C_n=\sum_{i=1}^{n}C_{i-1}\cdot C_{n-i}$ ，其中 $C_0=1$ 。
2>公式。 $\displaystyle C_n=\binom{2n}{n}\div(n+1)$

3.扩展卡特兰数 $Eg.$ BSOJ P2726 【SCOI2010】字符串

要求使组成 01 串中任意前缀中 1 的个数比 0 多，而 0 和 1 的个数不等。
那么我们假设向右上走表示这个字符选择 1 ，向右下走表示这个字符选择 0 ，问题即化为从 $(0,0)$ 走到 $(n+m,n-m)$ 的总方案数（不考虑不合法时）。
本题即可化为总方案数 - 不合法方案数，不合法方案数即为触碰到 $y=-1$ 的方案数，即 $\displaystyle \binom{n+m}{m} - \binom{n+m}{m-1} = \frac{(n+m)!} {n!\space m!} - \frac{(n+m)!}{(n+1)!\space (m-1)!}\mod sth.$
也可以看Luogu Solution，戳

V.斐波那契（Fibonacci）数列

1.定义：略

2.性质：
1> $F(n)=F(m)\cdot F(n-m+1)+F(m-1)\cdot F(n-m)$
2> $F(n-1)\cdot F(n+1)=F(n)^2+(-1)^n$
3> $gcd(F(n),F(m)) = F( gcd(n,m))$
4> $n\mid m\leftrightarrow F(n){\LARGE \mid} F(m)$