学习笔记：组合数学

参考文献

[专题总结]组合计数、容斥（理论篇）

前置知识

1. 第二类斯特林数：用 $\displaystyle {n\brace m}$​ 表示，表示表示将 $n$ 个两两不同的元素划分为 $m$ 个非空子集的方案数，有递推式为 $\displaystyle{n\brace k}={n-1\brace k-1}+k{n-1\brace k}$，通项公式为 $\displaystyle{n\brace m}=\sum^{m}_{i=0}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$。
2. 组合数：从 $n$ 个不同元素中，选出 $m$ 个组成一个集合，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组。从 $n$ 个不同元素中取出 $m$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，用符号 $\displaystyle\binom{n}{m}$ 来表示，读作「 $n$ 选 $m$ 」。计算公式为 $\dfrac{n!}{m!(n-m)!}$。特别地，规定当 $m>n$ 时，$\displaystyle\binom{n}{m}=0$。

问题类型

设有 $n$ 个球，$m$ 个盒子，将有标号记为L(labelled) 无标号记为U(unlabelled) 那么一个问题可以用缩写代替。

• A、无限制

• B、每个盒子至少有一个球

• C、每个盒子至多有一个球

• LL 型 ：两种方案，若有任意一对点，编号相同，所处的集合编号不同，就视为不同。

• LU 型 ：先分配球，之后把盒子按照某种方式排序后编号，使得一种分配方式只有一种编号方式。 若有任意一对点，编号相同，所处的集合编号不同，就视为不同。 这是处理不标号的基本方法，人工制造一个排序方式，使得一种集合只会被统计一次。

• UL 型 ：$n$ 个球全部不可区分，先分配球，再把球按照某种方式排序后编号，使得一种分配方式只有一种编号方式。 若有任意一对点，编号相同，所处的集合编号不同，就视为不同。

• UU 型：先分配球，之后把盒子按照某种方式排序后编号，把球按照某种方式排序后编号，使得一种分配方式只有一种编号方式（先给谁编号不重要）。 若有任意一对点，编号相同，所处的集合编号不同，就视为不同。

1. LLA 型：球和球之间相互不同，盒子与盒子之间相互不同，没有多余限制。

   方案数是 $m^n$（直接计算）或 $\displaystyle\sum^{min(n,m)}_{i=1}\binom{m}{i}{n\brace i}i！$（先枚举哪些盒子有球，用斯特林数分配，再给盒子添加顺序）。

2. LUA 型：球与球之间相互不同，盒子之间相同，没有多余限制。

   方案数是 $\displaystyle\sum^{m}_{i=1}{n\brace i}$（枚举非空盒子数量，随意分配）。

3. ULA 型：球之间相同，盒子与盒子之间相互不同，没有多余限制。

   方案数是 $\displaystyle\binom{n+m-1}{n-1}$(插板法，先制造 $m$ 个空球，不与原先的球区分，中间选出 $n-1$ 个位置插板拆分)。

4. UUA 型：球之间相同，盒子之间也相同，没有多余限制。

   方案数是 $\displaystyle\sum^{m}_{i=1}P_{i,j}$，$P_{i,j}$ 表示将 $i$ 个元素划分为 $j$ 个集合的方案数，可以由递推公式 $P_{i,j}=P_{i-1,j}+P_{i-j,j}$ 得到。

5. LLB 型：球和球之间相互不同，盒子与盒子之间相互不同，每个盒子至少有一个球。

   方案数是 LLA 对空集合容斥，$\displaystyle\sum^{m}_{i=0}\binom{m}{i}(-1)^i(m-i)^n$。

6. LUB 型：简化版 LUA，方案数是 $\displaystyle{n\brace m}$。

7. ULB 型：简化版 ULA，方案数是 $\displaystyle\binom{n-1}{m-1}$。

8. UUB 型：$P_{n,m}$。

9. LLC 型：$\displaystyle\binom{n}{m}*m!$。

10. LUC 型：放得下就是 $1$ 放不下就是 $0$。

11. ULC 型：放得下就是 $\displaystyle\binom{m}{n}$ 选，放不下就是 $0$。

12. UUC 型：放得下就是 $1$ 放不下就是 $0$。

组合恒等式

• $\displaystyle\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$ 先选 $m$ 再选 $k$ 相当于先选 $k$ 再在 $n-k$ 中选剩下的 $m-k$。
• $\displaystyle\prod^{k}_{i+1}\binom{a_i}{a_{i+1}}=\binom{a_1}{a_1-a_2,a_2-a_3,…,a_k-a_{k+1}}$ 多重集排列。
• $\displaystyle\sum^{n}_{i=m}\binom{i}{m}=\binom{n+1}{m+1}$ 上指标求和公式，可以不断用递归式展开组合数简单证明，组合意义就是走到 $\displaystyle(n-m,m+1)$，在 $\displaystyle(x,m)$ 的时候枚举 $x$ 的值。
• $\displaystyle\sum^{n}_{k=0}\binom{x+k}{k}=\binom{x+n+1}{x+}$ 平行求和法，上指标求和公式用 $\displaystyle\binom{n}{m}=\binom{n}{n-m}$ 凑数。
• $\displaystyle\sum^{n}_{i=0}\binom{n-i}{i}=Fib_{n+1}$ 负号平行求和法，$\displaystyle Fib$ 的含义是每步走 $1$ 或 $2$，最后走到 $n$ 的方案数，式子相当于枚举走了几个 $2$，然后把 $1,2$ 分配。
• $\displaystyle\sum^{n}_{i=0}\binom{n}{i}x^iy^{n-i}=(x+y)^n$ 二项式定理。
• $\displaystyle\sum^{n}{i=0}\binom{x}{i}\binom{y}{n-i}=\binom{x+y}{n}$ 范德蒙德卷积，共 $x+y$ 个选择 $n$ 个 ，枚举前 $x$ 个选了几个。
• $\displaystyle\sum^{n}_{i=0}\binom{i}{x}\binom{n-i}{y}=\binom{n+1}{x+y+1}$ 上指标版范德蒙德卷积，共 $n+1$ 个选 $x+y+1$ 个，相当于枚举第 $x+1$ 个的位置。
• $\displaystyle\sum^{min(a,b)}_{k=-min(a+b)}\binom{a+b}{a+k}\binom{a+b}{b+k}(-1)^k=\binom{a+b}{b}$，$\displaystyle\sum^{min(a,b,c)}_{-min(a,b,c)}\binom{a+b}{a+k}\binom{b+c}{b+k}\binom{c+a}{c+k}=\binom{a+b+c}{a,b,c}$ 只有这两个成立。证明考虑将组合数拆成 $\displaystyle\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$。

容斥-基础反演

子集反演，二项式反演，莫比乌斯反演，斯特林反演。

基于一个恰好算一遍的公式，让不合法的部分算零遍。

通过简化限制来减少条件（时刻记住目的）。

概率和期望

首先介绍 样本空间 Ω，事件集合 F，概率测度 P

样本空间是一个集合，一个事件就是样本空间的一个子集，所有事件的集合是 $F$。

每个事件都有它发生的概率，$P(S)$的定义就是 $S$ 发生的概率。

再介绍随机变量 $X$，他是一个由 $Ω→R$ 的函数，也就是给了每个事件一个权值。

一个随机变量的期望是 $\sum_w P(w)X(w)$，也就是按概率加权之后每个事件的权值之和。

有了这个东西，一些比较困扰我们的东西就自然清楚了。

比如 $E(x)^2\neq E(x^2)$，前者是求出按概率加权的权值和再平方，后者是按概率加权的权值的平方的和。

又比如期望的线性性，期望是把权值按概率加权求和，你把权值拆成很多份，只要保证加的权不变，就不会出任何问题。

一般的期望题目都是给你一个随机变量，在你知道样本空间和概率测度的情况下求它的期望。

容斥-min-max容斥及扩展

考虑我们现在有一个集合 $S$。

$$\min_{a_i\in S}=\sum_{T\subseteq S}(-1)^{|T|+1}max_{a_i\in T},\max_{a_i\in S}=\sum_{T\subseteq S}(-1)^{|T|+1}min_{a_i\in T}$$

以第一个式子为例，每个元素会被统计 $\sum^{kth-1}_{i=0}(-1)^i\binom{n}{i}=[kth==1]$。

在期望中，这个东西很有用。

期望有线性，在每个单独的样本中都满足上述式子，可以带上概率加权去统计。

注意，最大值的期望并不等于期望的最大值，最大值的期望是每种样本里面的最大值按概率加权之后的结果。

所以，我们有 $\displaystyle E(\min_{a_i\in S})=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min_{a_i\in T}$

min−max容斥还有 $kth$ 的形式，跟 min-max容斥的关系就像是 二项式反演 和 原始容斥 一样。

$$KthMax_k(S)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min_{a_i\in T}$$

证明方式相同，考虑每个元素被算的次数，每个数的极大的作为 min 的集合的大小就是它的 kth，由此容斥。

当然，min-max容斥还有在质因子上的情况，将 $\sum→\prod\,,\,min,max→gcd,lcm$ 即可。