Intro
容斥原理是表示集合元素个数之间的关系
公式如下：
\[|\bigcup_{i=1}^{n}(A_i)|=\sum_{i=1}^n |A_i|-\sum_{i<j} |A_iA_j|+\sum_{i<j<k} |A_iA_jA_k|-...+(-1)^{n-1} |A_1A_2...A_n| \]其中，\(|A_n|\)表示集合\(A_n\)的元素个数
证明思路：
每个元素\(a\)在\(|\bigcup_{i=1}^{n}(A_i)|\)中的个数只算作一次，只要证明某元素\(a\in A\)在右侧的个数只算作一次即可。
证明：
设元素\(a\)包含在\(k\)个集合中出现
在右边公式第一项里，只要在该\(k\)个集合中某一个出现，就会计数一次，因此为\(k=\mathrm{C}_k^1\)
在右边公式第二项里，其为两个集合的交集，因此必须挑出该\(k\)个集合中的两个，其组成的交集才会计数一次，因此为\(\mathrm{C}_k^2\)
同理，第三项，其为三个集合的交集，因此必须在该\(k\)个集合中三个的交集组合，才会被计数一次，因此为\(\mathrm{C}_k^3\)
以此类推，在右边计数次数为\(\mathrm{C}_k^1-\mathrm{C}_k^2+\mathrm{C}_k^3-\mathrm{C}_k^4+...+(-1)^{n-1}\mathrm{C}_k^k=\sum_{i=0}^k(-1)^{i+1}\mathrm{C}_k^i+1=1\)
即证
\[|\bigcup_{i=1}^{n}(A_i)|=\sum_{i=1}^n |A_i|-\sum_{i<j} |A_iA_j|+\sum_{i<j<k} |A_iA_jA_k|-...+(-1)^{n-1} |A_1A_2...A_n| \]其中，\(|A_n|\)表示集合\(A_n\)的元素个数
应用
错位排列
聚会上，n位同学将各自的名片放到桌子上，再将名片打乱后随机分配给这些同学，有多少种方式使他们中没有人能够拿到自己的名片？
首先需要对题目进行翻译，即相当于名片原来放在桌子上排成一列，现重新打乱顺序，而且要求新的顺序和旧的顺序没有一个重叠，即没有一个位置和原来是一样的。 不妨设\(|A_i|\)为第\(i\)个名片是在原来位置上的排列
则本题目等价于求解\(|\overline{A_1}\cap \overline{A_2}\cdots\cap\overline{A_n}|=|\overline{A_1\cup A_2\cdots \cup A_n}|\)
https://zhuanlan.zhihu.com/p/137941999