真的，学了组合数学你会克服公式恐惧症0.0深有体会……
容斥原理
设 A1,A2,…,An 为有限集合，用 |Ai| 表示集合 Ai 中的元素个数那么有这样的结论：
|A1∪A2∪…∪An|=∑i=1n|Ai|?∑1≤i<j≤n|Ai∩Aj|+∑1≤i<j<k≤n|Ai∩Aj∩Ak|?…+(?1)n?1|A1∩A2∩…∩An|.
(总的概括就是奇数个集合的并集累加和 减去 偶数个集合的并集累加和)
证明
若 a∈A1∩A2∩…∩An ，则 a 至少属于A1,A2,…,An中一个集合。
不妨设 a 属于A1,A2,…,Ak(1≤k≤n)而不属于其它集合。
于是 a 在1式左端计算了一次，而a在右端第一个和中算了 C1k 次，在第二个和中计算了 C2k ，…，可见， a 在右端算式中它被计算的总次数是：
C1k?C2k+C3k?…+(?1)k?1Ckk=1
顺带提一句，这种证明方式是“贡献法”
容斥原理加强版
这个加强版是博主和数学竞赛的小伙伴（ckh&yzc）一起讨论组合数学的时候搞出来的，欢迎大家来找出不严谨的地方！
加强版：原容斥原理针对的是集合中元素的个数，而我们拓宽到整个集合，加号改为∪号；而我们定义 A?B 得到的集合就是把A中所有B的元素都去掉后的结果。
例如，若 A={1,2,3,4,5}
B={1,2,4}
那么 A?B={3,5}
证明
以下的证明来自ckh（数学竞赛大佬%%%%%%%）
看不懂的同学在纸上画一画，就能看懂了。
设 S=?ni=1Ai
设 Bi=CSAi （补集的意思）
设 S′=?ni=1Bi
再令 Bi=S′+Ci
所以 |B1∩…∩Bi|=|S′|
C1∩C2∩…∩Cn=?
Ai=S?S′?Ci
所以 ?ni=1Ai=S?S′?(?ni=1Ci)=S?S′
代入前面的设，得证。
德.摩根律
设P和Q都是S的子集。
则有：
CS(P∩Q)=(CSP)∪(CSQ)
CS(P∪Q)=(CSP)∩(CSQ)
逐步淘汰原理（筛法公式）
设 S 是有限集合，Ai都包含于 S(i1,2,…,n) ， Ai 在 S 中的补集为CSAi(i=1,2,…,n)则
|CSA1∩CSA2∩…CSAn|=|S|?∑i=1n|Ai|+∑1≤i<j≤n|Ai∩Aj|?∑1≤<i<j<k≤n|Ai∪Aj∪Ak|+…+(?1)n|?i=1nAi|
证明
因为 |?ni=1Ai|=|S|?|CS(?ni=1)Ai| .
根据德.摩根律，我们有便宜美国vps
CS(?i=1nAi)=?i=1nCSAi
再根据容斥原理就能得到逐步淘汰公式。
置换及其不动点
给定集合 X={1,2,3,…,n} ， φ 是从X到X上的一一映射，通常记为:
φ={1?????????2?????????3?????????4?????????5φ(1)???φ(2)???φ(3)???φ(4)???φ(5)
则称 φ 是 X 上的置换，其中φ(i)是元素 i 在映射φ下的象。因为是一一映射，所以 φ(1),φ(2),…,φ(n) 实际上是 1,2,…,n 的一个排列。满足 φ(i)=i 的数 i 称为φ的一个不动点。
错位排列
在集合 X={1,2,…,n} 上没有任何不动点的置换 φ 的个数是 Dn=n!(1?11!+12!?13!+…+(?1)nn!)
例题3
设 φ 是集合 X={1,2,…,n} 上的置换，将 X 上没有不动点的置换个数记为fn，恰有一个不动点的置换个数记为 gn ，求证： |fn?gn|=1. (14届加拿大数学奥林匹克试题)
证明：
设 gn(i=1,2,…,n) 表示 X 上恰有唯一不动点i的置换个数。
于是
gn=gn1+gn2+…+gnn,
由上述推论，有 fn=Dn,gn=Dn?1(i=1,2,3,…,n),
故 gn=nDn?1,
所以
|fn?gn|=|Dn?nDn?1|=|n!(1?11!+12!?…+(?1)nn!)|?n×(n?1)!(1?11!+12!?…+(?1)n?1(n?1)!)=|n!×(?1)nn!|=1
得证
59956414
