算法学习笔记(16): 组合数学基础

组合数学基础

组合数学非常有用！我们先从一点点简单的性质开始

简单原理

• 加法原理

  这非常简单，我们举一个例子即可：考虑我有 (5) 个红苹果和 (3) 个绿苹果，如果你要选一个苹果去吃，那么你一共有 (5 + 3 = 8) 种选择的方法

• 乘法原理

  同样非常简单：考虑我有 (5) 个苹果，涵儿有 (6) 个苹果，我们各自拿出一个苹果，那么一共有 (5 times 6 = 30) 种拿出的方案

• 减法原理和除法原理

  本质与加法原理和乘法原理相似，这里不做展开

• 抽屉原理

  (广义）如果 (n) 个物品一共有 (k) 种状态，那么至少有 (lceil frac nk rceil) 种物品处于一个状态

  推论：一个从有 (> k) 个元素的集合映射到 (k) 个元素的集合的函数一定不是一对一函数。

终于正式开始将排列组合了！

排列

定理：具有 (n) 个元素的集合，选出 (r) 个排列的可能数（顺序相关）

[P(n, r) = n(n - 1)(n - 2)cdots(n - r + 1) ]

证明：由于顺序相关，不能选择同一个数多次，那么第一个位置有 (n) 种选法，第二个位置有 (n - 1) 中选法，以此类推，第 (i) 个位置有 (n - i + 1) 种选法。考虑乘法原理，那么就得出了上述结论。

特殊的：只要 (n) 是一个非负整数，那么 (P(n, 0) = 1)，因为恰好有一种方法来排列 (0) 个元素

简写公式：一般来说，我们不会写成上述形式，而是

[P(n, r) = frac {n!}{(n - r)!} ]

多重排列

考虑这样一个问题：我有 (7) 个盘子，(2) 个苹果，(3) 个橘子和 (2) 个桃子，分别在一个盘子中放一个水果，一共有多少种放法（我们认为同一种水果是相同的）？

经过计算，一共有 (frac {7!}{2!3!2!} = 210) 种放法。

抽象来说，我们将 (k) 个元素进行排列，对于第 (i) 个元素一共有 (x_i) 个。那么总的排列方案数为

[frac {(x_1 + x_2 + cdots + x_k)!}{x_1!x_2!cdots x_k!} ]

组合

其实就是顺序无关的排列

定理：具有 (n) 个元素的集合，选出 (r) 个数组成新的集合，本质不同的集合数为

[C(n,r) = {n choose r} = frac {n!}{r!(n-r)!} ]

由于顺序无关，我们考虑通过排列推导。

证明：为了得出所有集合，我们先考虑顺序相关，也就是有 (P(n, r)) 个排列，而对于每一个排列，如果不考虑顺序，一共重复计算了 (P(r, r)) 次，所以

[C(n, r) = frac{P(n, r)}{P(r,r)} = frac {frac {n!}{(n-r)!}}{frac{r!}{(r-r)!}} = frac {n!}{r!(n-r)!} ]

性质

接下来我们考虑组合的各种性质

---

[{n choose m} = {n choose n - m} = frac nm {n - 1 choose m - 1} = {n-1 choose m} + {n - 1 choose m - 1} ]

• 前两个等式，考虑按照定义展开化简即可

• 考虑最后一个等式，其实就是杨辉三角的递推，我们钦定 (n) 中的一个元素，分情况讨论

  • 如果不选择这个数，也就是在剩下的数中选择 (m) 个数，那么一共有 ({n-1 choose m}) 种情况

  • 如果选择这个数，那么只需要在剩下的数种选择 (m - 1) 个数即可，那么一共有 (n - 1 choose m - 1) 种情况

---

[binom nk binom km = binom nm binom {n-k}{m-k} ]

证明：展开即可

---

[sum_{i=k}^n binom ik = binom {n+1}{k+1} ]

证明：还是考虑展开

[sum_{i=k}^n binom ik = binom k {k+1} + binom kk + binom {k+1} k + cdots + binom nk ]

(binom k {k+1}) 是不合法的，所以其值为 0，加上去之后不会对结果产生影响

我们通过公式 (binom nm = {n-1 choose m} + {n - 1 choose m - 1}) 两两合并即可。

推论：我们将 (i) 平移，那么得出

[sum_{i=0}^m binom {k+i}i = {k + m + 1 choose m + 1} ]

---

[sum_{i=0}^n i binom ni = n 2^{n-1} ]

证明：

考虑代数展开，通过 ({n choose m} = {n choose n - m}) 变化即可。

[begin{aligned} sum_{i=0}^n i binom ni &= 0 binom n0 + 1 binom n1 + dots + (n-1) binom n {n-1} + n binom nn \ end{aligned} ]

但是，其实可以通过生成函数推导。推导步骤如下：

生成函数可以参考另外一篇博客：普通型生成函数 - Ricky2007 - 博客园

我认为讲的不错

我们先展开，得到

[0 + 1 binom n1 + 2 binom n2 + cdots + n binom nn ]

我们可以由此联想到生成函数求导的公式

[<a_1, a_2, a_3, dots> to <a_2, 2a_3, 3a_4, dots> ]

那么我们考虑求导前的生成函数序列：

[<binom n0, binom n1, binom n2, dots, binom nn, 0, dots> ]

显然，其生成函数展开之前为 (F(x) = (1+x)^n)

那么我们对其求导得到 (F'(x) = n(1+x)^{n-1})

展开之后为

[<1binom n1, 2binom n2, 3binom n3, dots, n binom nn, 0, dots> ]

我们考虑需要把所有的系数加起来，那么我们令 (x = 1) 即可

所以，得出

[sum_{i=0}^n i binom ni = F'(1) = n (1+1)^{n-1} = n 2^{n-1} ]

---

我们考虑扩展一下上述式子

[sum_{i=0}^n i^2 binom ni = n 2^{n-1} + (n-1)n2^{n-2} ]

考虑还是利用生成函数的思路。

将生成函数 (F'(x) = n(1+x)^{n-1}) 向右平移一位并再次求导：

[begin{aligned} G(x) &= xF'(x) = nx(1+x)^{n-1} \ G'(x) &= n(1+x)^{n-1} + (n-1)nx(1+x)^{n-2} \ end{aligned} ]

那么我们还是借上面的思路，令 (x = 1)，所以

[begin{aligned} sum_{i=0}^n i^2 binom ni &= G'(1) \ &= n2^{n-1} + (n-1)nx(1+x)^{n-2} \ &= n 2^{n-1} + (n-1)n2^{n-2} \ end{aligned} ]

二项式定理

定理：令 (n) 是非负整数，那么有

[begin{aligned} (x+y)^n & = sum_{i = 0}^n x^{n - i}y^i \ & = binom{n}{0}x^ny^0 + binom n1 x^{n-1}y^1 + cdots + binom n {n-1} x^1y^{n-1} + binom nn x^0 y^n end{aligned} ]

考虑展开之后每一项都应该是 (n) 次的，所以 (x) 为 (i) 次一共有 (binom ni) 种情况

我们利用这个找到一些有用的性质：

推论：令 (n) 为非负整数，那么

[sum_{i=0}^n binom ni = 2^n ]

证明：用二项式定理，令 (x = y = 1)，那么

[2^n = (1 + 1)^n = sum_{i=0}^n binom ni 1^i1^{n-i} = sum_{i=0}^n binom ni ]

推论：令 (n) 为非负整数，那么

[sum_{i=0}^n (-1)^i binom ni = 0 ]

证明：令 (x = -1, y = 1) 即可

范德蒙卷积

已知 (n, m, t)

[sum_{i=0}^t binom ni binom m {t-i} = binom{n + m} t ]

证明：在组合意义上，相当于在 (n) 中选 (i) 个，在 (m) 中选剩下的，也就是在 (n + m) 中选择 (t) 个。

而二项式证明这里就不展开了。

例题

请证明：

[sum_{i=0}^n {binom ni}^2 = binom {2n} n ]

Lucas定理

定理：

[binom nm equiv binom {lfloor frac np rfloor}{lfloor frac mp rfloor} binom {n % p}{m % p} pmod p ]

这个证明相对复杂，请酌情食用

证明：

我们考虑通过带余方程改写上述式子：

[binom {sp + t}{kp + r} equiv binom sk binom tr pmod p ]

我们通过生成函数 (F(x) = (1+x)^{sp+t}) 的第 (kp+r) 次项的系数求。

我们先求一个推导的时候需要的东西：

[begin{aligned} (1+x)^p & equiv 1 + binom p1 x + binom p2 x^2 + binom p3 x^3 + cdots + binom p {p-1} x^{p-1} + x^p pmod p \ & equiv 1 + x^p pmod p end{aligned} ]

那么我们正式开始推导：

[begin{aligned} (1+x)^{sp+t} & equiv (1+x)^{sp} cdot (1+x)^t pmod p \ & equiv ((1+x)^p)^s cdot (1+x)^t \ & equiv (1+x^p)^s cdot (1+x)^t \ & equiv sum_{i=0}^s binom si x^{pi} cdot sum_{j=0}^t binom tj x^j end{aligned} ]

我们取 (x^{kp+r}) 项

那么当且仅当 (i = k, j = r) 时，就可以取出 (x^{kp+r}) 项的系数。

考虑为什么当且仅当？

可知，我们需要 (ip+j = kp + r)

[begin{aligned} & because j in [0, t], t in [0, p), r in [0, p) \ & therefore j = r, i = k end{aligned} ]

那么，其系数为

[binom sk binom tr ]

所以，可知

[binom sk binom tr equiv binom {sp+t} {kp+r} pmod p ]

得证：

[binom nm equiv binom {lfloor frac np rfloor}{lfloor frac mp rfloor} binom {n % p}{m % p} pmod p ]

程序实现：

这里还是稍微讲一下吧

首先，我们需要求出组合数，那么我们先预处理一下模数以内的阶乘和阶乘逆元：

long long fac[N] = {1}, ifac[N]; for (int i = 1; i < MOD; ++i) fac[i] = (i * fac[i - 1]) % MOD; ifac[MOD - 1] = quickPow(fac[MOD - 1], MOD - 2, MOD); for (int i = MOD - 1; i; --i) ifac[i - 1] = ifac[i] * i % MOD; 

考虑一下组合数的特殊情况，如果 (n < m) 那么 (binom nm = 0)

所以我们求模数以内的组合数方法如下：

inline int C(int i, int j) {     if (i > j) return 0;     return fac[j] * ifac[i] % MOD * ifac[j - i] % MOD; } 

那么Lucas定理呢？我们处理一下 (n = 0) 的特殊情况即可

inline int Lucas(int i, int j) {     if (i == 0) return 1;     return Lucas(i / MOD, j / MOD) * C(i % MOD, j % MOD) % MOD; } 

广义容斥与二项式反演

这个部分相对较复杂，我给出反演公式

令 (f_n) 表示之多拥有 (n) 个属性的集合个数，(g_n) 表示恰好拥有 (n) 个属性的集合

那么

[begin{aligned} f_n &= sum_{i=0}^n binom ni g_i \ g_n &= sum_{i=0}^n (-1)^{n-i} binom ni f_i end{aligned} ]

反演推导证明

[begin{aligned} g_n &= sum_{i=0}^n (-1)^{n-i} binom ni sum_{j=0}^i binom ij g_j \ & 求和符号变换: \ &= sum_{j=0}^n g_j sum_{i = j}^n binom ni binom ij (-1)^{n - i} \ &= sum_{j=0}^n g_j sum_{i = j}^n binom nj binom {n-j}{i-j} (-1)^{n-i} \ &= sum_{j=0}^n g_j binom nj sum_{i = j}^n binom {n-j}{i-j} (-1)^{n-i} \ &= sum_{j=0}^n g_j binom nj sum_{i=0}^{n-j} binom {n-j}i (-1)^{n-i} \ &= sum_{j=0}^n g_j binom nj (1 + (-1))^{n-j} \ & [当且仅当 n=j 时有贡献: (1+(-1))^{n-j} ne 0] \ &= g_j binom nj [n=j] \ &= g_n end{aligned} ]