\[一切繁复都洗涤，却染上重叠的星 \]
容斥原理
是容斥原理的基本公式。
但是我们并不经常的使用这个公式本身，我们一般使用这个公式的推论：
具体的理解这个式子，就是在全集 \(\mathbb{U}\) 中，我们有若干个子集 \(A_i\)，其中的元素是坏的。现在我们需要找到不被任何子集包含的元素个数。
容斥原理的证明
使用集合论和数学归纳法，是容易证明的。但是如果从概率的角度来说，我们就有更好的方法证明它。
我们设事件 \(X_i\) 为随机选一个元素，子集 \(A_i\) 中的元素被选中。然后取它的指示随机变量 \(I(X_i)\in\{0,1\}\) 表示事件 \(X_i\) 的发生与否。
然后，又有对于两个随机事件 \(A,B\)，\(I(AB)=I(A)I(B)\)，由于满足结合律，我们就可以推广到 \(I(\bigcap X_i)=\prod I(X_i)\)。
同时，\(I(\overline A)=1-I(A)\)，所以 \(I(\bigcap \overline X_i)=\prod (1-I(X_i))\)。
也就等于 \(\sum_{S\subseteq\mathbb{U}}(-1)^{|S|}\prod_{i\in S}I(X_i)\)。
回代公式 \(\sum_{S\subseteq\mathbb{U}}(-1)^{|S|}I(\bigcap_{i\in S} X_i )\)。
然后对两边取期望，指示随机变量的期望就是该事件的概率
\(P(\bigcap \overline X_i)=\sum_{S\subseteq\mathbb{U}}(-1)^{|S|}P(\bigcap_{i\in S} X_i )\)
\(\dfrac{|\bigcap \overline A_i|}{|\mathbb{U}|}=\sum_{S\subseteq\mathbb{U}}(-1)^{|S|}\dfrac{|\bigcap_{i\in S}A_i|}{\mathbb{|U|}}\)
两边约去 \(\mathbb{U}\)，得到推论公式。
容斥原理和集合划分
我们知道集合划分是斯特林数，等价于满射个数问题，那么我们就来尝试数满射个数。
我们可以设 \(r_k\) 为至少有 \(k\) 个位置没有被射到的映射个数，很容易得到 \(r_k=\begin{pmatrix}n\\k\end{pmatrix}(n-k)^n\)
然后我们就可以直接容斥得到答案 \(\sum_{k\le 0}(-1)^kr_k\)，下标替换 \(k=n-k\) 得到 \(\sum_{k\le 0}(-1)^{n-k}\begin{pmatrix}n\\k\end{pmatrix}k^n\)。
然后斯特林数是不考虑顺序的满射个数，也就是要除以 \(|\pi|\)，那么 \(\begin{Bmatrix}n\\k\end{Bmatrix}=\dfrac{1}{n!}\sum_{k\le 0}(-1)^{n-k}\begin{pmatrix}n\\k\end{pmatrix}k^n=\sum_{k\le 0}\dfrac{(-1)^{n-k}k^n}{k!(n-k)!}\)
容斥原理的优势和劣势
容斥原理的优势在于，我们只需要数“至少有 \(k\) 个位置满足某某条件”的方案个数，而不必要数“恰好有 \(k\) 个位置满足某某条件”的方案个数。也就是，我们不需要考虑算重的问题。
但是，容斥原理的公式形式决定了我们很难得到没有 \(\sum\) 的封闭形式。
错排问题
错排问题可以表述成满足 \(i\neq\pi(i)\) 的排列个数。
我们记 \(r_k\) 为至少有 \(k\) 个位置满足 \(i=\pi(i)\) 的排列个数，那么容易得到 \(r_k=\begin{pmatrix}n\\k\end{pmatrix}(n-k)!\)。然后就可以直接容斥原理求得答案为 \(\sum (-1)^k\begin{pmatrix}n\\k\end{pmatrix}(n-k)!=n!\sum\dfrac{(-1)^k}{k!}\)。
我们发现，\(\sum_k \dfrac{(-1)^k}{k!}\) 其实就是 \(e^{-1}\) 的泰勒展开式的前 \(n\) 项，所以 \(n!\sum\dfrac{(-1)^k}{k!}\sim \dfrac{n!}{e}\)，也就是概率是个常数。
生成函数和容斥原理
我们可以设 \(x_i\) 为选择 \(i\) 的个数的随机变量，然后每个位置可以映射到除了子集以外的所有值，也就是它对答案的贡献是 \(x_1+x_2+\cdots x_{i-1}+x_{i+1}\cdots +x_n\)。但是这样有点麻烦，我们就记 \(s=\sum x_i\)，那么贡献就是 \(s-x_i\)
然后我们要求的答案就是 \(\prod (s-x_i)\) 的第 \(\prod_{i\le n}x_i\) 项系数。那么我们就枚举其中有 \(k\) 个来自 \(-x_i\)，剩下的 \(n-k\) 个自由安排来自某个 \(s\)， 则为 \(\begin{pmatrix}n\\k\end{pmatrix}(n-k)!\)。所有的来自 \(-x_i\) 的都带系数 \(-1\)，所以贡献要乘上 \((-1)^k\)。
我们就用生成函数在不同的含义和相似的形式下求出了错排数。
法兰西晚宴
对于一个圆环，安排 \(1\sim 2n\) 的所有数，使得 \([1,n]\) 的所有数都不相邻，\([n+1,2n]\) 的所有数都不相邻，\(i\) 和 \(i+n\) 不相邻。
我们可以先把 \([n+1,2n]\) 都先安排好，共有 \(2n!\) 种。然后就是对于 \(n\) 个数，每个位置不能选择自己在 \(n\) 长度的圆环上的对应点和其后继的方案数。
我们把这个排列问题映射成棋盘，也就是所有打 \(x\) 的位置不能选择，并且每行每列都只选择一个的方案数。
然后我们发现，我们就只要求出至少 \(k\) 个位置被选择为 \(x\) 的方案数。
然后，我们发现所有不能选的点构成一个长度 \(2n\) 的环，问题转化为求取在 \(m\) 的环上选 \(k\) 个不相邻的数的个数 \(C(m,k)\)。
首先，我们可以算在长度 \(m\) 的链上选择 \(k\) 个不相邻位置的方案数，先把这 \(k\) 个位置选走，我们发现，我们就是在剩下的 \(m-k\) 个位置种插板，方案数 \(L(m-k)=\begin{pmatrix}m-k+1\\k\end{pmatrix}\)。
然后，我们发现，如果把环上没有选取的位置断开一个得到的结果，和在链上的某个位置插入一个未选择的位置是相同的。那么就有 \((m-k)C(m-k)=mL(m-1,k)\)
解出 \(C(m,k)=\dfrac{m}{m-k}\begin{pmatrix}m-k\\k\end{pmatrix}\)
然后 \(r_k=\dfrac{2n}{2n-k}\begin{pmatrix}2n-k\\k\end{pmatrix}\)
也就得到答案为
