Logo

菜单

狼群狼某人
发布于 2025-06-20 / 36 阅读
0
2

组合数学学习笔记

排列组合

加法 & 乘法原理

加法原理

一个人有 n 种上衣，第 i 种上衣有 a_i 件，则他有 S=a_1+a_2+ \cdots +a_n 种选择。

乘法原理

一个人有很多件衣服，比如衣服、鞋子、帽子等，第 i 种衣服有 a_i 件，则他有 S=a_1 \times a_2 \cdots \times a_n 种搭配方式。

总而言之，一个步骤内部使用加法原理，多个步骤之间使用乘法原理。

排列数和组合数

排列数

从 n 个不同元素中取出 m 个数（m \leq n）有顺序地排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。

从 n 个不同元素中取出 m 个元素的所有排列的个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用符号 A_n^m 表示。

我们考虑，选取第一个元素时有 n 个元素可以选择，第二个时有 n-1 个可以选择……直到第 m 个时，有 n-m+1 个可以选择，所以可以得到排列的计算公式：

\begin{aligned} A_n^m &= n(n-1)(n-2) \cdots (n-m+1) \\ &= \dfrac{n(n-1)(n-2) \cdots (n-m+1)(n-m)(n-m-1) \cdots 1}{(n-m)(n-m-1) \cdots 1} \\ &= \dfrac{n!}{(n-m)!} \end{aligned}

当 m=n 时，称这种情况为全排列，选取第一个元素时有 n 个元素可以选择，第二个时有 n-1 个可以选择……直到第 n 个时，有 1 个可以选择，所以可以得到全排列的计算公式：

A_m^m=n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n!

组合数

从 n 个不同元素中取出 m 个数（m \leq n）无顺序地排成一列，叫做从 n 个不同元素中取出 m 个元素的一个组合。

从 n 个不同元素中取出 m 个元素的所有组合的个数，叫做从 n 个不同元素中取出 m 个元素的组合数，用符号 C_n^m 表示。

组合数是无序的，所以如果能够删去 A_n^m 中重复的组合，就可以得到 C_n^m。

考虑对于 m 个元素，其一共有 A_m^m 即 m! 种排列方式，也就是对于 m 个元素，其有 m! 种重复组合，所以可以得到：

C_n^m = \dfrac{A_n^m}{m!} = \dfrac{n!}{m!(n-m)!}

插板法

不存在 0 的分组

现在有 n 个相同的鸡蛋，要求将其放到 k 个篮子中，且篮子不能为空，一共有多少种分法？

我们可以将问题抽象化，将鸡蛋排成一条线，篮子变成长板，则问题可以转化为将板子插到鸡蛋的间隔之间，有多少种插法。

重新考虑原始问题，发现如果把每个板子左边部分的鸡蛋放到篮子里，那么最右边会有几个鸡蛋没有被放进篮子，所以我们先拿出一个板子放在最右边，用来承接这部分鸡蛋。

那么问题就可以转化为将 k-1 个板子插到 n 个鸡蛋形成的 n-1 个间隔中，故答案为：

C_{n-1}^{k-1}

可以感性理解到其本质是求 x_1+x_2+ \cdots +x_k=n 的解的个数（x > 0）。

存在 0 的分组

在上一种情况的基础上，让篮子可以为空，一共有多少种分法？

发现没有办法直接插板。

我们考虑额外拿出 k 个虚拟的鸡蛋，此时有 n+k 个鸡蛋和 k 个篮子，鸡蛋间有 n+k-1 个间隔，我们对其进行插板法，插板结束后将那 k 个虚拟的鸡蛋拿出来，此时之前只被分到一个虚拟鸡蛋的篮子就变成了空的，答案为：

C_{n+k-1}^{k-1}

因为组合数学的神秘性质，我们可以知道，在 n 个数中选 m 个数，等价于在 n 个数中不选 n-m 个数，即 C_n^m=C_n^{n-m}。

所以答案也可以化为：

C_{n+k-1}^{n}

可以感性理解到其本质是求 x_1+x_2+ \cdots +x_k=n 的解的个数（x \geq 0）。

每组有最小限制的分组

如果，对于第 i 个篮子，至少要分到 a_i 个鸡蛋呢？

可以感性理解到其本质是求 x_1+x_2+ \cdots +x_k=n 的解的个数（x_i \geq a_i）。

类比上面的情况，我们可以借 \sum{a_i} 个虚拟的鸡蛋，设 x_i' = x_i - a_i，因为 x_i \geq a_i，易得 x_i' >= 0。

那么方程就可以进行转化：

\begin{aligned} x_1 + x_2 + \cdots + x_k &= n \\ (x_1'+a_1) + (x_2'+a_2) + \cdots +(x_k'+a_k) &= n \\ x_1' + x_2' + \cdots + x_k' &= n - (a_1 + a_2 \cdots + a_k) \\ x_1' + x_2' + \cdots + x_k' &= n - \sum{a_i} \\ \end{aligned}

因为 x_i' >= 0，所以这个问题就就转化为了上文篮子可以为空的问题，带入上文求出的公式（将 n 替换为 n-\sum{a_i}），得到：

C_{n - \sum{a_i} +k -1}^{n - \sum{a_i}}

不相邻的排列

在 1 \sim n 这 n 个数中，选 k 个，其中两两不相邻的组合有多少种？

能够选择 k 个，说明其中分开了 k-1 个间隔，不同的是，为了两两不相邻，这次的“间隔”是具体的数。

所以问题转化为有 n-k+1 个数，选择其中 k 个数，求有多少种组合。答案为：

C_{n-k+1}^{k}

二项式定理

二项式定理阐明了一个展开式的系数：

(a+b)^n = \sum_{i=0}^{n} C_n^i a^{n-i} b^i

其意义是 (a+b)^n 展开后，等于 n+1 个单项式的和，其中在第 i 个单项式中，单项式的系数为 C_n^i，a 的幂数为 n-i，b 的幂数为 i。

二项式定理也可以推广到多项式：

(x_1 + x_2 + \dots x_k)^n = \sum_{n_1 + n_2 + \cdots + n_k = n}^{n} C_{n}^{n_1,n_2,\cdots,n_k} x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k}
  • 其中 C_{n}^{n_1,n_2,\cdots,n_k} 是组合数的扩展形式，其等价于 \dfrac{n!}{n_1!n_2! \cdots n_k!}。
  • 其中 n_1,n_2 \cdots n_k > 0。

排列组合进阶

多重集的排列数（多重组合数）

当一个集合出现重复元素​时，我们计算它的全排列就不能再直接使用 n! 了。

当一个有 n 个元素的多重集 S 中的元素个数为 n_1,n_2 \cdots n_k 的时候，我们可以这么考虑：

之所以不能直接使用 n! 计算排列数，是因为有了重复元素，这些重复元素相互交换位置依旧是一种情况。

那么，可以考虑先计算 n!，然后再将重复的情况除去，有多少种重复的情况呢？

对于第 i 种元素，其全排列为 n_i!，这些都是重复情况，那么可以简单地得到 S 的全排列计算公式：

\dfrac{n!}{n_1!n_2! \cdots n_k!} = \dfrac{n!}{\prod_{i=1}^{k} n_i!}

我们发现，这个公式似乎和上文的 C_{n}^{n_1,n_2,\cdots,n_k} 是一样的，这是因为多重集的排列数也可以用组合数的方式理解：

  • 现在有 n 个位置，在其中放 n_1 个相同的数，有 C_n^{n_1} 种方法。
  • 现在有 n-n_1 个位置，在其中放 n_2 个相同的数，有 C_{n-n_1}^{n_2} 种方法。
  • \cdots
  • 现在有 n-n_1-n_2 \cdots -n_{k-1} 个位置，在其中放 n_k 个相同的数，有 C_{n-n_1-n_2 \cdots -n_{k-1}}^{n_k} 种方法。

根据乘法原理，将其全部相乘就是答案，可以得到：

\begin{aligned} C_n^{n_1} \times C_{n-n_1}^{n_2} \times \cdots \times C_{n-n_1-n_2 \cdots -n_{k-1}}^{n_k} &= \dfrac{n!}{n_1! (n-n_1)!} \times \dfrac{(n-n_1)!}{n_2! (n-n_1-n_2)!} \times \cdots \times \dfrac{(n-n_1-n_2 \cdots -n_{k-1})!}{n_k! (n-n_1-n_2 \cdots -n_k)!} \\ &= \dfrac{n!}{n_1! n_2! \cdots n_k! \times 0!} \\ &= \dfrac{n!}{n_1! n_2! \cdots n_k!} \\ &= \dfrac{n!}{\prod_{i=1}^{k} n_i!} \end{aligned}

多重集的组合数 1

请注意：多重集的组合数和多重组合数不是一个东西。

当一个有 n 个元素的多重集 S 中的元素个数为 n_1,n_2 \cdots n_k 的时候，选取其中的 r(r \leq n_i,\forall i \in [1,k]) 个数，有多少种方法？

观察其本质，发现等价于 x_1 +x_2 + \cdots + x_k = r 的解的个数（x_i \geq 0），所以可以使用上文的插板法解决，答案为：

C_{r+k-1}^{r} 或 C_{r+k-1}^{k-1}

多重集的组合数 2 待补

看不懂，以后再说。

圆排列

有 n 个人围成一圈，求排列数 Q_n^n。

我们考虑把圆拆成列，则此时有 A_n^n 种排列数。

在环中时，所有人可以一起向一个方向移动而排列不变，所以要除以 n，所以：

Q_n^n=\dfrac{A_n^n}{n}=(n-1)!

那么，如果是从 n 个人中选出 m 个人呢？

其实就是先求 C_n^m，再乘 m 的圆排列，答案是：

Q_n^m=C_n^m \times Q_m^m = \dfrac{n!}{m!(n-m)!} \times \dfrac{m!}{m} = \dfrac{n!}{m \times (n-m)!}

组合数性质（二项式推论）

  1. 因为选 m 个数等价于不选 n-m 个数，所以有：
C_n^m = C_n^{n-m}
  1. 组合数的递推式（杨辉三角的公式表达），可以利用它在 O(n^2) 的复杂度下递推组合数：
\begin{aligned} C_n^m &= \dfrac{n!}{m!(n-m)!} \\ &= \dfrac{(n-1)!}{m!(n-m)!} \times n \\ &= \dfrac{(n-1)!}{m!(n-m)!} \times (m+(n-m)) \\ &= \dfrac{(n-1)! \times m}{m!(n-m)!} + \dfrac{(n-1)! \times (n-m)}{m!(n-m)!} \\ &= \dfrac{(n-1)!}{(m-1)!(n-m)!} + \dfrac{(n-1)!}{m!(n-m-1)!} \\ &= C_{n-1}^{m-1} + C_{n-1}^{m} \end{aligned}

  1. 范德蒙恒等式，可以用于把一个大的组合数拆成多个小的（OI Wiki 的公式有误）：

    \sum_{i=0}^{k} C_m^{k-i} C_n^i = C_{n+m}^k

    其证明可以按照组合数的方式理解，现在从有 n,m 个鸡蛋的两个篮子 A,B 中拿出 k 个鸡蛋，则有 C_{n+m}^k 种选法。

    换一种思考方式，如果从 A 中拿出 i 个，B 中就要拿出 k-i 个，则有 C_m^{k-i} C_n^i 中方法，这个式子对于 i \in [0,k] 都成立，所以需要累加，得到 \sum_{i=0}^{k} C_m^{k-i} C_n^i 种选法。

  2. 在 3 中，当 n=m=k 时，存在：

    \sum_{i=0}^{k} C_m^{k-i} C_n^i = \sum_{i=0}^n (C_n^i)^2 = C_{2n}^n

二项式反演

我们设 f_i 表示使用 i 个元素形成特定结构的方案数，g_n 表示从 n 个元素中选出 i(i \geq 0) 个元素形成特定结构的方案书的总数。

如果已知 f_i 求 g_n，那么显然存在：

g_n = \sum_{i=0}^{n} C_n f_i

如果已知 g_i 求 f_n，那么有：

f_n = \sum_{i=0}^n C_n^i (-1)^{n-i} g_i

这样子已知 g_i 求 f_n 的过程，就叫做二项式反演。

证明

容斥原理

定义

班里有 10 个学生喜欢数学，15 个喜欢语文，21 个喜欢编程，班里喜欢至少一门学科的学生有多少呢？

很明显，答案不是 10+15+21=46，因为有的学生会同时喜欢多门学科，计数重复了。

我们定义喜欢这三科的学生集合为 A,B,C，那么学生总数就是 \mid A \cup B \cup C \mid，如果直接计算 \mid A \mid + \mid B \mid + \mid C \mid，就会有一部分重复计算，所以要减去 \mid A \cap B \mid + \mid B \cap C \mid + \mid A \cap C \mid，但是这样又多扣了一些，所以再加上 \mid A \cap B \cap C\mid，所以得到：

\mid A \cup B \cup C \mid = \mid A \mid + \mid B \mid + \mid C \mid - \mid A \cap B \mid - \mid B \cap C \mid - \mid A \cap C \mid + \mid A \cap B \cap C\mid

后面待补，这公式我死活看不懂。

Slope Trick 学习笔记
P8340 [AHOI2022] ...

评论