组合数学
排列数
$$A_n^m = m^{\underline{n}} = \frac{n!}{(n - m)!}$$
表示从 $n$ 个不同元素中选出 $m$ 个元素(有序).
多重集排列数
当 $n$ 个元素中含有相同元素, 记不同元素的种类共 $k$ 个, 第 $k$ 种元素具有 $c_k$ 个. 则形成的排列数为
$$\frac{n!}{\prod_{i = 1}^{k} c_i!}$$
组合数
$$C_n^m = \binom{n}{m} = \frac{n!}{m! \times (n - m)!} = \frac{A_n^m}{A_m^m}.$$
表示从 $n$ 个元素中选出 $m$ 个元素(无序).
多重集组合数
多重组合数
需要与多重集组合数做区分.
$$\binom{n}{c_1, c_2, \cdots, c_k} = \frac{n!}{\prod_{i = 1}^{k} c_i!}$$
组合意义为从 $n$ 个不同物品中不放回地选 $c_i$ 个, 共取 $k$ 次.
组合数线性递推式
$$ \binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}$$
组合意义
动态规划: 当前第 $i$ 个物品选 / 不选.
数学证明
但由于
组合意义灭天地, 代数推导保平安
因此我们尝试下严谨的公式证明.
圆排列
组合意义为 $n$ 个人全部来围成一圈，所有的排列数记为
$\mathrm Q_n^n$。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。 所以有
组合恒等式
二项式定理
$$(x + y)^n = \sum\limits_{i = 1}^{n} \binom{n}{i} x^i y^{n - i}.$$
应用:
求 $\sum i \times \binom{n}{i}.$
$Solutions$:
$$\sum i \times \binom{n}{i} = \sum\limits_{i = 1}^{n} n \times \binom{n - 1}{i - 1} = n \times 2^n.$$
杨辉三角列前缀求和
范德蒙德恒等式
组合连乘
$$\binom{n}{i} \times \binom{i}{k} = $$
吸收公式
$$\binom{n}{k} \times k^{\underline{i}} = \binom{}{}$$
同时使用下降幂到幂的转化, 使用第二类斯特林数, 可以吸收线性式.
二项式定理
$$(x + y)^n = \sum \limits_{i = 0}^n \binom{n}{i} x^{n - i} y^i$$
球盒模型
小球与盒子是组合数学的经典问题, 按照限制属性的不同可以分为共计 $12$ 中情况：
（注：在下文陈述中, 使用 $n$ 表示球的个数, $m$ 表示盒子个数）
1. 球无编号, 盒子有编号, 每个盒子至少放一个球
题面也可以表述为: 求不定方程
$$x_1 + x_2 + \cdots + x_m = n.$$
的正整数解个数.
由于每个球完全相同, 可以考虑将所有球排成一列, 进行若干分割得到答案, 这种方法被称为插板法.
$n$ 个球排成一列共有 $n - 1$ 个空位, 在这些空位中插入 $m - 1$ 个板得到 $m$ 组球, 并且相邻两个空位之间必有一个球, 保证了题意所述 “每个盒子至少放一个球”.
即答案为
$$\binom{n - 1}{m - 1}$$
2. 球无编号, 盒子有编号, 不限制个数
发现情况 $1$ 无法处理盒子为空的情况. 于是考虑把插板操作视为在 $n + m - 1$ 个球中选择 $m - 1$ 个作为板, 选择相邻的球则产生了一个空盒子, 满足题目限制条件.
即答案为
$$\binom{n + m - 1}{m - 1}$$
2. 球无编号, 盒子有编号, 每个盒子至多放一个球
由于每个球相同, 因此问题等价于选出 $n$ 个盒子放球, 即答案为
$$\binom{m}{n}$$
4. 球有编号, 盒子有编号, 不限制个数
每个球都有 $m$ 种放法, 显然总方案数为 $m^n$.
5. 球有编号, 盒子有编号, 每个盒子至多放一个
对于 $m < n$ 的情况显然无解.
依次考虑放 $1 \sim n$ 个球的过程中, 每次可选的盒子减少 $1$ 个, 因此总方案数为 $n^{\underline m}$.
6. 球有编号, 盒子有编号, 每个盒子至少放一个
前置知识：二项式反演, 如果你还不会, 可以通过链接跳转到下面先学习二项式反演.
每个盒子至少放一个的限制不方便处理, 可以尝试转化为有 $0$ 个盒子没有放球.
7. 球有编号, 盒子无编号, 不限制个数
第二类斯特林数.
8. 球有编号, 盒子无编号, 每个盒子至少放一个
9. 球有编号, 盒子无编号, 每个盒子至多放一个
由于盒子全部相同, 这些球放在任何一个盒子都是同一种情况, 于是答案为
$$[ m \geqslant n ]$$
10. 球无编号, 盒子无编号, 不限制个数
拆分数, 不会捏.
11. 球无编号, 盒子无编号, 每个盒子至多放入一个球
与 $9$ 情况相同, 答案为
$$[ m \geqslant n ]$$
12. 球无编号, 盒子无编号, 每个盒子至少放入一个球
先在每个盒子中放入一个球, 转化为情况 $10$, 答案为 $p_{n - m, m}$.
扩展: 盒子容量有上限: [CEOI2004] Sweets
容斥原理
引入
这里通过一个简单的例子来引入容斥原理.
给定 $n$, 求 $1 \sim n$ 中所有能被 $3$, $5$ 或 $7$ 整除的数.
$Solutions$
设 $A$ 集合表示所有能被 $3$ 整除的数, $B$ 集合表示所有能被 $5$ 整除的数, $C$ 集合表示所有能被 $7$ 整除的数.
则有
$$A \cup B \cup C = A + B + C - A \cap B - A \cap C - B \cap C + A \cap B \cap C$$
公式化定义
尝试以公式定义我们最常见的子集容斥：
若
$$g_T = \sum \limits_{T \in S} f_S$$
则有
$$f_S = $$
二项式反演
设 $f_x$ 表示
同理, 也有类似形式的子集反演
简单应用
有 $n$ 个白球和 $m$ 个黑球, 每次取出一个球, 不放回. 如果是白球在序列中插入 $0$, 如果是黑球在序列中插入 $1$, 求 $01$ 的期望个数. $n \leqslant 5 \times 10^3.$
扩展: $n \leqslant 1e18$
答案为
$$\frac{(n + m - 1) \times \binom{n + m - 2}{n - 1}}{\binom{n + m}{m}} = \frac{n \times m}{n + m}$$
斯特林数
置换与圆排列对应.
第一类斯特林数
递推公式
$$\brack{}{}$$
FJOI2016 建筑师
第二类斯特林数
递推式
$$\brace{}{}$$
