组合数学

组合数学

二项式定理

​ $ (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. 考虑容斥，