容斥原理
加法原理与减法原理
加法原理是集合之间两两不相交的情况下计算并集的计算公式。
而在一般情况（即集合之间可以有交集的时候），需要使用容斥原理来计算并集当中的对象个数。
减法原理就是一种简单的容斥原理，即两个性质之间的容斥原理。
减法原理的符号描述：设 (A1) 为具有性质 (P1) 的对象集合， (A2) 为 (S) 中具有性质 (P2) 的对象集，则原式为 (large |overline{A1}capoverline{A2}|=|S|-|A1|-|A2|+|A1cap A2|)
-
证明：
分类讨论 $large xin|overline{A1}capoverline{A2}| $ 和 $large x otin|overline{A1}capoverline{A2}| $：
对于任意一个元素 $large xin|overline{A1}capoverline{A2}| $ ，一定有 (xin S) 且 (x otin A1) 和 (x otin A2) ，于是左右贡献都是 (1) 。
对于任意一个元素 (large x otin |overline{A1}cap overline {A2}|) ，此时左侧贡献固定为 (0)：
如果只有性质 (P1) ，那么右侧贡献是 (1-1+0+0=0) ，如果只有性质 (P2) ，那么右侧贡献是 (1+0-1+0=0) ，如果既有性质 (P1) 又有性质 (P2) ，那么右侧贡献是 (1-1-1+1=0)
因此我们可以考虑把减法原理的两个性质的情况推广到多个。
交集容斥&并集容斥
定理1（交集容斥）
公式
设 (large P_1,P_2,P_3...P_m) 是集合对象涉及到的 (m) 个性质， (large A_i={x:xin S) 且 (large x) 具有性质 (large P_i}) ，则集合中不具有性质 (large P_1,P_2...P_m) 的对象个数由下面的交错表达式给出：
(large |overline{A_1}capoverline{A_2}cap...capoverline{A_m}|=|S|-sumlimits_{{i}}{|A_i|}+sumlimits_{{i,j}}{|A_icap A_j|}-sumlimits_{{i,j,k}}{|A_icap A_jcap A_k|}+...+(-1)^m|A_1cap A_2cap ...cap A_m|)
-
右侧第 (i) 个求和符号等于 ({1,2...m}) 的 (i) 子集求和。
因此，右侧的总项数为 (large dbinom m0 +dbinom m1+dbinom m2+...+dbinom mm=2^m)
证明
同样采用双计数的思想，考虑每一个元素对于两边的关系：
直接分类讨论 (x) 具不具有任何一个性质。
如果元素 (x) 不具有任何一个性质，那么这个 (x) 对左边贡献为 (1) ，对右边只有 (S) 有贡献 (1) 。
如果元素 (x) 至少具有一个性质，那么不妨设它具有 (n) 条性质（(nge 1)）。
那么 (x) 对右侧的贡献有：(dbinom n0-dbinom n1 +dbinom n2 -dbinom n3+...+(-1)^mdbinom nm) ，
分别代表这个 (x) 对于元素具有零个，一个，两个(...) 性质的时候 (x) 对这部分集合的贡献。（因为每有一个这样的集合就会有 (x) 对其 (1) 的贡献）
那么显然可以根据交错和公式：
(large dbinom n0-dbinom n1 +dbinom n2 -dbinom n3+...+(-1)^mdbinom nm=dbinom n0-dbinom n1 +dbinom n2 -dbinom n3+...+(-1)^ndbinom nn=0)
于是这样的 (x) 对于右侧的贡献也是 (0) 。
(Q.E.D.)
总结
定理 (1) 给出了求任意相交的集合的并集中对象个数的公式。
-
((-1)^i) 称为容斥系数，满足第奇数项为正，第偶数项为负，简称奇减偶加。
所谓容斥原理，容指加法，斥指减法。
推论1（二项式反演）
公式
如果容斥原理中，集合 (large A_{i_1}cap A_{i_2}cap ... cap A_{i_k}) 的大小仅与子集大小 (k) 有关，而和实际选择哪 (k) 个集合无关（即存在常数 (large alpha_k=left|A_{i_1}cap A_{i_{2}}cap ...cap A_{i_k} ight|) ），那么容斥原理可以简写为：
(large |overline{A_1}cap overline{A_2}cap...cap overline{A_m}|=alpha_0-dbinom m1 alpha_1+dbinom m2alpha_2-...+(-1)^malpha_m)
例： (large [0,99999]) 中有多少个整数含有数字 (large 2,5,8) （三个都有）
设不含有第 (large i) 个数字的性质为 (large P_1) ，则 (large |A_{i_1}cap A_{i_2}cap ...cap A_{i_k}|) 只与 (large k) 有关。（数量只与所处位置有关，与是哪些数字无关）
因此答案为 (large 10^5-3cdot 9^5+3cdot 8^5-7^5)
证明
把
(large |overline{A_1}capoverline{A_2}cap...capoverline{A_m}|=|S|-sumlimits_{{i}}{|A_i|}+sumlimits_{{i,j}}{|A_icap A_j|}-sumlimits_{{i,j,k}}{|A_icap A_jcap A_k|}+...+(-1)^m|A_1cap A_2cap ...cap A_m|)
当中的 (large |A_i|,|A_icap A_j|,|A_icap A_jcap A_k|) 等项写成 (large alpha_1,alpha_2,alpha_3...) 即可。
定理2（摩根定律）
公式
(large overline{Acap B}=overline A cup overline B)
(large overline{Acup B}=overline A cap overline B)
推论3（并集容斥）
公式
集合 (S) 中至少具有性质 (large P_1,P_2,...,P_m) 之一的对象个数为 ：
(large |A_1cup A_2cup ... cup A_m|=sumlimits_{{i}}{|A_i|}-sumlimits_{{i,j}}{|A_icap A_j|}+sumlimits_{{i,j,k}}{|A_icap A_jcap A_k|}+...+(-1)^{m+1}|A_1cap A_2cap ... cap A_m|)
例 (1) ：求 (large [1,1000]) 中不能被 (5,6,8) 整除的整数个数
设 (P_i) 表示被第 (i) 个整数整除的性质，则
(|overline{A_1}cap overline{A_2}cap ... cap overline{A_m}|=1000-(lfloor dfrac{1000}{5} floor+lfloor dfrac{1000}{6} floor+lfloor dfrac{1000}{8} floor)+(lfloor dfrac{1000}{[5,6]} floor+lfloor dfrac{1000}{[5,8]} floor+lfloor dfrac{1000}{[6,8]} floor)-lfloor dfrac{1000}{[5,6,8]} floor=600)
例 (2) ：字母 ({M,A,T,H,I,S,F,U,N}) 的排列中单词 (MATH,IS,FUN) 不作为连续字母出现的排列个数
设 (P_i) 表示出现第 (i) 个单词的性质，那么使用容斥+捆绑法解决即可。
证明
(large |A_1cup A_2cup ... cup A_m|=|S|-overline{|A_1cup A_2cup ... cup A_m|}=|S|-|overline{A_1}cup overline{A_2}cup ... cup overline{A_m}|)
然后根据定理 (1) ，将最后一项代换得证。
例题：
限制个数的多重集合r组合
不同k个元素r子集
(n) 个不同元素的集合 (S) 的 (r) 子集：(dbinom nr =dfrac{n!}{r!(n-r)!})
- 可以看做重复数满足 (n_1=n_2=...=n_k=1)
无限重复k种元素r子集
重复数无限的 (k) 种元素集合 (S) 的 (r) 子集：(dbinom{r+k-1}{r})
- 可以看做重复数满足 (n_1=n_2=...=n_k=r)
限制个数k种元素r子集
对于其它情况，我们考虑通过容斥原理来求解。
具体做法就是把容斥原理应用到无限状态下求解。
例 (1) ：求多重集合 (T={(a,3),(b,4),(c,5)}) 的 (10) 组合数量
设 (P_1) 表示 (a) 的个数超过 (3) 个， (P_2,P_3) 同理。
那么答案就是 (|overline{A_1}cap overline {A_2}cap overline{A_3}|=|S|-(|A_1|+|A_2|+|A_3|)+(|A_1cup A_2|+|A_2cup A_3|+|A_1cup A_3|)-|A_1cup A_2cup A_3|)
其中重点说一下后面的部分怎么计算。
(|A_1|,|A_2|,|A_3|) 显然就是限制了某一个数至少选多少个，根据套路我们可以直接先从总数里面选掉这些数，也就是把这个下界去掉，剩下的转化为无限状态下的选择。
那么 (|A_1cup A_2|) 这样的其实也是同理，只不过限制得多了几个数，我们直接从总数里面减掉这些下界的和即可，剩下的也就转化为无限状态下的选择了。
比如这里举几个例子：(|S|=dbinom{10+3-1}{10},|A_1|=dbinom {6+3-1}{6},|A_1cup A_2|=dbinom{1+3-1}{1})
例题：
非负整数解数量
多重集合的 (r) 组合其实就等价于方程 (x_1+x_2+...+x_k=r) 的非负整数解数量。
因此我们这里使用同样的办法，可以解决限制 (x_i) 上界（(x_ile n_i)）的 (r) 组合问题。
例 (2) ：求 (x_1+x_2+x_3+x_4=18) 的整数解数量，其中 (1le x_1le 5,-2le x_2le 4,0le x_3le 5,3le x_4le 9) 。
首先把下界用等式的性质去掉（或者说换元），然后转化为上述问题，同样的解法即可。
错位排列
咕咕咕~
有绝对禁止位置的错位排列
有相对禁止位置的错位排列
反演
一般的反演
容斥原理与反演的关系
容斥原理，实际是对于条件苛刻的情况数量直接求解困难时，使用条件宽泛的情况数量进行运算后表示出来。
其使用的条件是基于双计数思想，即等式左右的值相同。
实际上，按照正常思路，条件宽泛的情况应该是由若干个条件苛刻的情况组合而成。
反演的定义
即，形式化而言，所求目标为 (large f(n)=sumlimits_k{a_{n,k}cdot g(k)})
例如交集容斥中的情况
然而，往往条件宽泛的情况数也是容易计算的，而条件苛刻的情况大部分时候都难以直接使用计数原理进行统计。
因此我们希望通过函数 (f) 的取值讲 (g) 计算出来，即用 (f) 表示 (g) ，设为 (large g(n)=sumlimits_k{b_{n,k}cdot f(k)})
带入前式可得：(large f(n)=sumlimits_k{a_{n,k}cdot (sumlimits_m{b_{k,m}{f(m)}})}=sumlimits_m{f(m)}sumlimits_k{a_{n,k}b_{k,m}})
要想得到合法的 (B) 数组，那么就需要满足左右相等，即：(large sumlimits_k{a_{n,k}b_{k,m}}=[n=m])
定义：（反演）：通过函数 (f) 以及系数数组 (a) 和 (b) ，求解 (large f(n)=sumlimits_k{a_{n,k}cdot g(k)}) 中的函数 (g) 的过程，称为反演。
- 函数 (g) 求 (f) 的过程称为演绎。
- 函数 (f) 和 (a) 通常已知或易求。
- 对于容斥系数b，(large sumlimits_k{a_{n,k}b_{k,m}}=[n=m]) 是矩阵乘法的形式，我们一般情况下可以通过矩阵求逆来获得(b)
- 对于一些特殊的函数求和式，我们可以快速算出 (b) 。
子集包含的偏序集上的反演
子集反演
子集演绎的概念
如果集合的贡献与选择的具体集合元素相关，此时函数 (f) 和 (g) 的自变量应为实际的集合。
形式化而言，对于 (n) 元素集合 (X_n={1,2,...,n}) 及其子集包含关系的偏序集 ((P(X_n),subseteq))：
设 (G:P(X_n) o R) 是定义在 (P(X_n)) 上的实值函数。
- 即，(G) 函数将某个子集映射到一个实数。
那么我们使用 (G) 定义一个新函数 (F:P(X_n) o R) ，其中 (large F(K)=sumlimits_{Lsubseteq K}{G(L)})
- 即函数 (F) 为某个集合所有子集的 (G) 函数值之和。
子集演绎的常见应用形式
例如，我们设 (f(X)) 表示至多选择集合 (X) 中的元素的方案数，(g(X)) 表示恰好选择集合 (X) 的方案数，则有子集演绎 (large f(S)=sumlimits_{Tsubseteq S}{g(T)})
子集反演公式
子集反演公式证明
首先我们有这样一个柿子：
其实这就是二项式系数交错和的集合表达的形式，这里写一下原式是：
然后我们像二项式反演里面一样做，先转化柿子变成 (large [k=varnothing]) 这样的形式：
然后可以把这个东西换成上面的柿子：
交换一下求和顺序：
发现右边的求和其实就是我们正向子集演绎的 (f) ：
于是再把 (p-r) 换成 (r) ，得到子集反演：
(large Q.E.D.)
超集反演
超集演绎的概念
至多使用子集表示，至少则使用超集表示
使用超集演绎又可以称为反向子集演绎。
这时我们用另一种方式来定义 (F) ：
用 (G) 定义一个新函数 (F:P(X_n) o R) ，其中 (large F(K)=sumlimits_{Lsubseteq K}{G(L)})
- 即函数 (F) 为某个集合所有超集的 (G) 函数值之和。
超集演绎的常见应用形式
如果设 (f(X)) 表示至少选择集合 (X) 中的元素的方案数， (g(X)) 表示恰好选择集合 (X) 的方案数，则有超集演绎 (large f(S)=sumlimits_{Ssubseteq T}{g(T)})
超集反演公式
超集反演公式证明
(large Q.E.D.)
多重子集反演
设 (f(X)) 表示至多选择多重集合 (X) 中的元素的方案数，(g(X)) 表示恰好选择集合 (X) 的方案数，则有子集演绎 (large f(S)=sumlimits_{Tsubseteq S}{g(T)})
在尝试反演之前，首先我们要知道：多重集合中目前我们是没有 ([S=varnothing]) 这样的形式的，所以我们应当找到这样的形式再进行反演！所以，接下来将介绍多重集合中定义的莫比乌斯函数。
多重集合中的莫比乌斯函数
定义多重集合 (S) 的莫比乌斯函数：
那么有：
- 证明：
多重子集反演公式
其中 (large mu(S)=left{egin{matrix}&(-1)^{lvert S vert} &S中无重复元素\ &0 &S 中有重复元素 end{matrix} ight.)
多重子集反演公式证明
权值和只与集合大小有关的反演
二项式反演
概念
二项式反演为一种反演形式，常用于通过 “至多/至少某若干个” 求 “恰好若干个” 的问题。
注意：二项式反演虽然形式上和多步容斥极为相似，但它们并不等价，只是习惯上都称之为多步容斥。
也有很多地方称作“钦定”，但是感觉这样并不能体现出子集二项式反演和超集二项式反演的区别。
子集二项式反演
概念
沿用容斥原理的公式，我们有：
(large |overline{A_1}capoverline{A_2}cap...capoverline{A_m}|=|S|-sumlimits_{{i}}{|A_i|}+sumlimits_{{i,j}}{|A_icap A_j|}-sumlimits_{{i,j,k}}{|A_icap A_jcap A_k|}+...+(-1)^m|A_1cap A_2cap ...cap A_m|)
再根据补集的补集就是交集我们又有：
(large |A_1cap A_2cap...cap A_m|=|S|-sumlimits_{{i}}{|overline{A_i}|}+sumlimits_{{i,j}}{|overline{A_i}cap overline{A_j}|}-sumlimits_{{i,j,k}}{|overline{A_i}cap overline{A_j}cap overline{A_k}|}+...+(-1)^m|overline{A_1}cap overline{A_2}cap ...cap overline{A_m}|)
这时我们考虑一种特殊情况：多重集合的交集大小只和集合的数目有关。
也就是这样：
如果容斥原理中，集合 (large A_{i_1}cap A_{i_2}cap ... cap A_{i_k}) 的大小仅与子集大小 (k) 有关，而和实际选择哪 (k) 个集合无关（即存在常数 (large alpha_k=left|A_{i_1}cap A_{i_{2}}cap ...cap A_{i_k} ight|) ），那么容斥原理可以简写为：
(large |overline{A_1}cap overline{A_2}cap...cap overline{A_m}|=alpha_0-dbinom m1 alpha_1+dbinom m2alpha_2-...+(-1)^malpha_m)
左侧恰好为所有条件均不满足的情况，右侧为至少某些条件满足的情况。
对于这种情况，子集演绎可以特化为子集二项式演绎。
子集二项式演绎的推导
咕咕咕。。先看着组合意义或者容斥原理将就一下。。
子集二项式演绎的组合意义
记 (f(n)) 表示至多满足某 (n) 个条件的权值，(g(n)) 表示恰好大小为 (n) 的集合权值，则(large f(n)=sumlimits_{i=0}^n{dbinom ni g(i)}) 。
组合意义：每一个大小为 (i) 的集合都可以作为某个 (n) 集合的子集产生贡献，每个子集都有 (dbinom ni) 个 (i) 子集。
注意：(f) 函数的意义绝非简单的 (g) 函数的前缀和！
子集二项式演绎/反演公式
子集二项式反演公式证明
根据二项式系数的交错和公式，我们有：
然后是一个形同废话的变形：
于是直接代入得到：
容易发现 (dbinom nm dbinom{n-m}k) 根据组合意义很容易写出：(dbinom nm dbinom{n-m}k=dbinom nk dbinom{n-k}{m})
于是就有：
然后交换求和顺序，就可以把只与 (n) 和 (k) 相关的项提出来了：
发现其实右侧的求和就是 (f) ！于是可以换成：
换个元 (n-k o k)
(Q.E.D.)
子集二项式反演的作用
我们将子集反演特化为子集二项式的目的是为了避免枚举子集，优化时间复杂度。
子集二项式反演的使用条件
任意至少满足 (k) 个和恰好满足 (k) 个的权值相同。
超集二项式反演
概念
和子集二项式反演一样，在超集反演的情况下，我们考虑一种特殊情况：多重集合的交集大小只和集合的数目有关。
这样的话我们可以把超集演绎可以特化为超集二项式演绎。
超集二项式演绎的推导
设全集为 (X_n)
设 (F(K)) 表示至少满足性质 (K={P_{i_1},P_{i_2},...,P_{i_k}}) 的权值。
设 (large h(k)=sumlimits_{lvert K vert=k}F(K)) ，则表示所有至少满足任意 (k) 个性质的权值和。
- 如果情况数只与个数 (k) 有关，则可令 (f(k)=F(K)) （也就是不再关心子集的具体情况只关心个数）
- 此时 (large h(k)=sumlimits_{lvert K vert=k}F(K)=f(k)cdot (sumlimits_{vert Kvert}1)=dbinom nk f(k))
设 (G(M)) 表示恰好满足性质 (M={P_{i_1},P_{i_2},...,P_{i_m}}) 的权值。
- 恰好意味着其余性质均不满足。
根据组合意义：
交换求和符号：
代入 (G(T)=g(t)) 可得 (large h(k)=sumlimits_{t=k}^ndbinom tk sumlimits_{vert Tvert =t}g(t))
如果所有大小恰好为 (t) 的集合的权值和只与集合大小 (t) 有关，则可以设 (large p(t)=sumlimits_{vert Tvert =t}G(T))
因此我们得到： (large h(k)=sumlimits_{t=k}^ndbinom tk p(t))
- 特别的，当 (k=0) 时， (K) 为空集，即至少满足 (0) 个性质的权值和，等价于 (n) 个性质任意选择，此时 (large h(0)=f(0)=sumlimits_{t=0}^np(t))
如果所有大小为 (t) 的集合权值全部相等（即每个集合的权值都只与集合大小有关），则可以令 (g(m)=G(M)) ，此时 (large h(k)=sumlimits_{t=k}^ndbinom tkdbinom ntg(t))
超集二项式演绎的组合意义
设 (f(x)) 为至少满足某 (x) 个条件的权值， (h(x)) 为所有至少满足 (x) 个条件的权值和， (p(x)) 是所有恰好满足 (x) 个条件的权值和，(g(x)) 是恰好满足某 (x) 个条件的权值，则 (large h(k)=sumlimits_{t=k}^ndbinom tk p(t))
组合意义：每选出一个 (g(t)) ，其中的任何一个 (k) 子集都会在左侧计算一次 (g(t)) 的权值，因此总共在 (dbinom tk) 次贡献。
推论 (1) ：如果所有大小为 (t) 的集合的权值全部相等，设 (g(x)) 为恰好满足某 (x) 个条件的权值，则有：
(large h(k)=sumlimits_{t=k}^ndbinom tk dbinom ntg(t))
超集二项式演绎/反演公式
超集二项式反演公式证明
超集二项式反演的作用
我们将超集反演特化为超集二项式的目的是为了避免枚举子集，优化时间复杂度。
超集二项式反演的使用条件
题目所求为任意恰好 (k) 个的权值和。
任意至少 (k) 个的权值和容易求解，且只与 (k) 有关。
一点总结
做题的时候，如果所求恰好情况的条件是条件集合的全集，则我们可以只设置所需要的条件，并使用子集形式的二项式反演。
- 即，设所有条件集合为 (n) ，我们所求的就是 (g(n)) 。
如果所求恰好情况的条件只是条件集合的一个子集，不能删掉其余没有用到的条件，那么我们只能设置所有的条件，并使用超集形式的二项式反演。
- 即，设所有条件集合为 (n) ，我们所求的就是 (g(k),k<n)
或者，根据至少和至多的组合意义谁更好求解，决定使用哪个形式。
说了这么多，其实有这样一点是值得注意的，就是二项式反演里面的子集二项式反演一定要慎用，因为一定要注意到加粗体的那几个字，也就是到底设的是某一个还是和！
做了一点题，其实感觉老是想着套二项式反演反而不太好，因为容斥原理完全可以解决大部分问题。
这里贴一个觉得说的很有道理的话：（是这篇题解里的）
