10.容斥原理拓展
10.1 二项式反演
\[P.10.1(1) \]设 \(U=\{S_1,S_2,S_3...S_n\}\)，且任意 \(i\) 个元素的交集都相等
定义 \(g(x)\) 为 \(x\) 个集合的交集，\(f(x)\) 为 \(x\) 个集合补集的交集（定义 \(f(0)=g(0)=U\)），则：
\[\mid\bigcap^{n}_{i}S_{i}\mid=\mid U\mid+\sum_{i}\{(-1)^{i}\times\mid f(i)\mid\} \]可知对 \(g(i)\)，符合要求的 \(f(i)\) 组合共有 \(C^{i}_{n}\) 种，即原式可以化为：
\[\mid\bigcap^{n}_{i}S_{i}\mid=\sum^{n}_{i}(-1)^{i}C^{i}_{n}\mid f(i)\mid \]同理有
\[\mid\bigcap^{n}_{i}\complement_{U}S_{i}\mid=\sum^{n}_{i}(-1)^{i}C^{i}_{n}\mid g(i)\mid \]因为
\[\mid f(n)\mid=\mid\bigcap^{n}_{i}\complement_{U}S_{i}\mid,\mid g(n)\mid=\mid\bigcap^{n}_{i}S_{i}\mid \]因此得出结论：
\[g(n)=\sum^{n}_{i=0}(-1)^{i}C^{i}_{n}f(i)\iff f(n)=\sum^{n}_{i=0}(-1)^{i}C^{i}_{n}g(i) \]\[P.10.1(2) \]因为
\[C^{i}_{n}\times C^{j}_{i}=\dfrac{n!}{(n-i)!i!}\times \dfrac{i!}{(i-j)!j!}=\dfrac{n!}{(n-j)!j!}\times\dfrac{(n-j)!}{[(n-j)-(n-i)]!(i-j)!}=C^{j}_{n}\times C^{n-1}_{n-j} \]因此
\[\sum^{n}_{i=j}\{(-1)^{i}\times C^{i}_{n}\times(-1)^{j}\times C^{j}_{i}\}=C^{j}_{n}(-1)^{j}\sum^{n-j}_{i=0}C^{i}_{n-j}=C^{j}_{n}\times (1-1)^{n-j}=C^{j}_{n}\times 0^{n-j} \]当 \(j\neq n\) 时，原式值为 \(0\)，否则值为 \(1\).
当 \(g(n)=\sum\limits^{n}_{i=0}(-1)^{i}C^{i}_{n}f(i)\iff f(n)=\sum\limits^{n}_{i=0}(-1)^{i}C^{i}_{n}g(i)\) 成立时，可以推知
\[f(n)=\sum^{n}_{i=0}(-1)^{i}C^{i}_{n}=\sum^{n}_{i=0}(-1)^{i}C^{i}_{n}\sum^{n}_{i=j}(-1)^{j}C^{j}_{i}f(j)=\sum^{n}_{j=0}f(j)\sum^{n}_{i=j}\{(-1)^{i}\times C^{i}_{n}\times(-1)^{j}\times C^{j}_{i}\} \]该式末项 \(\sum\limits^{n}_{i=j}\{(-1)^{i}\times C^{i}_{n}\times(-1)^{j}\times C^{j}_{i}\}\) 已有上述结论，故当 \(j\neq n\) 和 \(j=n\) 时分别带入讨论，发现原式均成立，证毕.
事实上，二项式反演还有一个更常用的推导式：
\[g(n)=\sum\limits_{i=0}^nC^{i}_{n}f(i)\iff f(n)=\sum\limits_{i=0}^n(-1)^{n-i}C^{i}_{n}g(i) \]根据二项式反演的性质，我们通常会构造一组 \(\{ f(i),g(i)\}\)，使得两者之间存在包含关系并且有一者很方便求出，通过反演来快速得到另一者的值.
二项式反演还有其他形式：
\[g(n)=\sum\limits_{i=n}^N(-1)^iC^{i}_{n}f(i)\iff f(n)=\sum\limits_{i=n}^N(-1)^{i}C^{i}_{n}g(i) \]\[g(n)=\sum\limits_{i=n}^NC^{i}_{n}f(i)\iff f(n)=\sum\limits_{i=n}^N(-1)^{i-n}C^{i}_{n}g(i) \]10.2 Min-Max 容斥
对于满足全序关系并且其中元素满足可加减性的序列 \(\{x_i\}\)，设其长度为 \(n\)，并设 \(S=\{1,2,3,\cdots,n\}\) ，则有：
\[\max_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\min_{j\in T}{x_j}} \]\[\min_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\max_{j\in T}{x_j}} \]一个常用的实际应用为 Min-Max 容斥的低维版本：\(\min(a,b)=a+b-\max(a,b)\)
证明略.
10.3 错位排列
满足 \(\forall i\neq a_{i}\) 的排列被称为错位排列.
10.3.1 公式
套用补集的公式，问题变成求
\[\left|\bigcup_{i=1}^n\overline{S_i}\right| \]可以知道，\(\overline{S_i}\) 的含义是满足 \(P_i=i\) 的排列的数量。用容斥原理把问题式子展开，需要对若干个特定的集合的交集求大小，即：
\[\left|\bigcap_{i=1}^{k}S_{a_i}\right| \]其中省略了 \(a_i<a_{i+1}\) 的条件以方便表示
上述 \(k\) 个集合的交集表示有 \(k\) 个变量满足 \(P_{a_i}=a_i\) 的排列数，而剩下 \(n-k\) 个数的位置任意，因此排列数：
\[\left|\bigcap_{i=1}^{k}S_{a_i}\right|=(n-k)! \]那么选择 $k4 个元素的方案数为
\(C^{k}_{n}\)，因此有：
\[\begin{aligned} \left|\bigcup_{i=1}^n\overline{S_i}\right| &=\sum_{k=1}^n(-1)^{k-1}\sum_{a_{1,\cdots,k} }\left|\bigcap_{i=1}^{k}S_{a_i}\right|\\ &=\sum_{k=1}^n(-1)^{k-1}C^{k}_{n}(n-k)!\\ &=\sum_{k=1}^n(-1)^{k-1}\frac{n!}{k!}\\ &=n!\sum_{k=1}^n\frac{(-1)^{k-1} }{k!} \end{aligned}\]因此 \(n\) 的错位排列数为：
\[D_n=n!-n!\sum_{k=1}^n\frac{(-1)^{k-1} }{k!}=n!\sum_{k=0}^n\frac{(-1)^k}{k!} \]10.3.2 递推式
\[D_{n}=(n-1)(D_{n-1}+D_{n-2}) \]\[D_{n}=nD_{n-1}+(-1)^{n}) \]待证明
10.4 Catalan 数
1 1 2 5 14 42 132
关于 Catalan 数的常见公式：
\[H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases}\]\[H_n = \frac{H_{n-1} (4n-2)}{n+1} \]\[H_n = C^{n}_{2n} - C^{n-1}_{2n} \] 标签：frac,limits,OI,sum,容斥,mid,拓展,times,bigcap From： https://www.cnblogs.com/HaneDaCafe/p/18317830