组合数学-526互联

组合数学

二项式定理

$ (a + b)^n = \sum \limits_{i = 0}^{n} \dbinom {n} {i} a^i b^{n - i} $

证明：考虑组合意义，对于一项 $a^i b^{n - i}$ ，需要在 $n$ 个 $(a + b)$ 中选出 $i$ 个 $a$ ，剩余全部选 $b$ 乘起来得到，故系数为 $\dbinom{n}{i}$。

常见组合恒等式

$\dbinom{n}{m} = \dbinom{n}{m - 1} + \dbinom{n - 1}{m - 1}$
$ \dbinom{n}{m} \dbinom{m}{k} = \dbinom{n}{k} \dbinom{n - k}{m - k} \qquad (n \ge m \ge k)$

证明：组合意义上考虑，在 $n$ 个中选 $m$ 个，再从 $m$ 个里选 $k$ 个，与从 $n$ 个中先选出 $k$ 个，再从 $n - k$ 个中选出剩余 $m - k$ 个等价。
$ i \dbinom{n}{i} = n \dbinom{n - 1}{i - 1}$

证明：直接展开即可，同时是上式在 $m = i, k = 1$ 时的特殊情况。
$\sum \limits_{i = 0}^{m} \dbinom{n + i}{n} = \dbinom{n + m + 1}{n + 1}$

证明：上指标求和，考虑 $n + 1$ 个数中最后一个放在了哪里。假设放在了第 $k$ 个数，那么说明 $n$ 个数全部放在了前 $k - 1$ 个位置中，此时贡献就是 $\dbinom{k - 1}{n}$ ，那么对于 $\dbinom{n + m + 1}{n + 1}$ ，最后一个数可以放在 $[n + 1,n + m + 1]$ 中任意的位置上，所以总和就是 $\sum \limits_{k = n + 1}^{n + m + 1} \dbinom{k - 1}{n} =\sum \limits_{i = 0}^{m} \dbinom{n + i}{n}$。
$\sum \limits_{i=0}^{k} \dbinom{n}{i} \dbinom{m}{k - i} = \dbinom{n + m}{k}$

证明：范德蒙德卷积， $n$ 个里面选 $i$ 个，$m$ 个里选 $k - i$ 个，枚举 $i \in [0,k]$ ，总和显然等于 $\dbinom{n + m}{k}$。

常见组合模型

设多重集 $S = {n_1 \cdot a_1, n_2 \cdot a_2, \dots, n_k \cdot a_k}$ ，记 $n = \sum \limits_{i = 1}^{k} n_i$ ，则 $S$ 的全排列个数为 $\dfrac{n!}{\prod_{i = 1}^{k} n_i!}$ 。
插板法
- $n$ 个物品，分成 $m$ 组，要求每组非空。等价于 $n - 1$ 个空里插 $m - 1$ 个板子，方案数为 $\dbinom{n - 1}{m - 1}$。
  
  本质是求 $x_1 + x_2 + \dots + x_m = n$ 的正整数解的个数。
- $n$ 个物品，分成 $m$ 组，每组可以为空。考虑借 $m$ 个虚拟物品，在 $n + m$ 个物品里插板，插完后去掉虚拟物品，方案数为 $\dbinom{n + m - 1}{m - 1} = \dbinom{n + m - 1}{n}$ 。
  
  本质是求 $x_1 + x_2 + \dots + x_m = n$ 的非负整数解的个数。
- $n$ 个物品，分成 $m$ 组，每组至少 $a_i$ 个物品。直接从方程角度考虑，等价于求 $x_1 + x_2 + \dots + x_m = n$ 的整数解的个数，其中 $x_i \ge a_i$。
  
  类似的，借 $\sum a_i$ 个物品，使得每一组至少有 $a_i$ 个物品，设 $t_i = x_i - a_i$，则原方程转化为求 $t_1 + t_2 + \dots + t_m = n - \sum a_i$ 的非负整数解的个数，这就转化成了第二个问题。直接代入得到答案为 $\dbinom{n - \sum a_i + m - 1}{n - \sum a_i}$。
- $n$ 个物品，分成 $m$ 组，每组至多 $a_i$ 个物品。
  1. 考虑 dp，设 $f_{i,j}$ 表示考虑到第 $i$ 组，当前选了 $j$ 个物品的方案数，方程为 $f_{i,j} = \sum_{k = 0}^{min(a_i,j)} f_{i - 1,j - k}$ 。
    
    时间复杂度 $O(nm)$。
  2. 考虑容斥，