三個集的情況 容斥原理 （inclusion-exclusion principle）又称排容原理 ，在組合數學 裏，其說明若
A
1
{\displaystyle A_{1}}
A
n
{\displaystyle A_{n}}
有限集 ，則
|
⋃
i
=
1
n
A
i
|
=
∑
i
=
1
n
|
A
i
|
−
∑
1
≤
i
<
j
≤
n
|
A
i
∩
A
j
|
+
∑
1
≤
i
<
j
<
k
≤
n
|
A
i
∩
A
j
∩
A
k
|
−
⋯
+
(
−
1
)
n
−
1
|
A
1
∩
⋯
∩
A
n
|
.
{\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|={}&\sum _{i=1}^{n}|A_{i}|-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}}
其中
|
A
|
{\displaystyle |A|}
A
{\displaystyle A}
基數 。例如在兩個集的情況時，我們可以通過將
|
A
|
{\displaystyle |A|}
|
B
|
{\displaystyle |B|}
交集 的基數，而得到其并集 的基數。
|
A
∪
B
|
=
|
A
|
+
|
B
|
−
|
A
∩
B
|
{\displaystyle \left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|}
|
A
∪
B
∪
C
|
=
|
A
|
+
|
B
|
+
|
C
|
−
|
A
∩
B
|
−
|
A
∩
C
|
−
|
B
∩
C
|
+
|
A
∩
B
∩
C
|
{\displaystyle \left|A\cup B\cup C\right|=\left|A\right|+\left|B\right|+\left|C\right|-\left|A\cap B\right|-\left|A\cap C\right|-\left|B\cap C\right|+\left|A\cap B\cap C\right|}
n
{\displaystyle n}
[ 编辑 ] 要计算几个集合并集的大小，我们要先将所有单个集合 的大小计算出来，然后减去所有两个集合相交 的部分，再加回所有三个集合相交 的部分，再减去所有四个集合相交 的部分，依此类推，一直计算到所有集合相交 的部分。
最终得到公式：
|
⋃
i
=
1
n
A
i
|
=
∑
i
=
1
n
|
A
i
|
−
∑
1
≤
i
<
j
≤
n
|
A
i
∩
A
j
|
+
∑
1
≤
i
<
j
<
k
≤
n
|
A
i
∩
A
j
∩
A
k
|
−
⋯
+
(
−
1
)
n
−
1
|
A
1
∩
⋯
∩
A
n
|
.
{\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|={}&\sum _{i=1}^{n}|A_{i}|-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}}
又可写成
|
⋃
i
=
1
n
A
i
|
=
∑
k
=
1
n
(
−
1
)
k
+
1
(
∑
1
≤
i
1
<
⋯
<
i
k
≤
n
|
A
i
1
∩
⋯
∩
A
i
k
|
)
{\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)}
或
|
⋃
i
=
1
n
A
i
|
=
∑
∅
≠
J
⊆
{
1
,
2
,
…
,
n
}
(
−
1
)
|
J
|
−
1
|
⋂
j
∈
J
A
j
|
.
{\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}}(-1)^{|J|-1}{\Biggl |}\bigcap _{j\in J}A_{j}{\Biggr |}.}
在概率论 中，对于概率空间
(
Ω
,
F
,
P
)
{\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P} )}
A 1 ，……，A n n = 2时容斥原理的公式为：
P
(
A
1
∪
A
2
)
=
P
(
A
1
)
+
P
(
A
2
)
−
P
(
A
1
∩
A
2
)
,
{\displaystyle \mathbb {P} (A_{1}\cup A_{2})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})-\mathbb {P} (A_{1}\cap A_{2}),}
当n = 3时，公式为：
P
(
A
1
∪
A
2
∪
A
3
)
=
P
(
A
1
)
+
P
(
A
2
)
+
P
(
A
3
)
−
P
(
A
1
∩
A
2
)
−
P
(
A
1
∩
A
3
)
−
P
(
A
2
∩
A
3
)
+
P
(
A
1
∩
A
2
∩
A
3
)
{\displaystyle \mathbb {P} (A_{1}\cup A_{2}\cup A_{3})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})+\mathbb {P} (A_{3})-\mathbb {P} (A_{1}\cap A_{2})-\mathbb {P} (A_{1}\cap A_{3})-\mathbb {P} (A_{2}\cap A_{3})+\mathbb {P} (A_{1}\cap A_{2}\cap A_{3})}
一般地：
P
(
⋃
i
=
1
n
A
i
)
=
∑
i
=
1
n
P
(
A
i
)
−
∑
i
,
j
:
i
<
j
P
(
A
i
∩
A
j
)
+
∑
i
,
j
,
k
:
i
<
j
<
k
P
(
A
i
∩
A
j
∩
A
k
)
−
⋯
+
(
−
1
)
n
−
1
P
(
⋂
i
=
1
n
A
i
)
,
{\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{i=1}^{n}\mathbb {P} (A_{i})-\sum _{i,j\,:\,i<j}\mathbb {P} (A_{i}\cap A_{j})+\sum _{i,j,k\,:\,i<j<k}\mathbb {P} (A_{i}\cap A_{j}\cap A_{k})-\ \cdots \ +(-1)^{n-1}\,\mathbb {P} {\biggl (}\bigcap _{i=1}^{n}A_{i}{\biggr )},}
也可以写成：
P
(
⋃
i
=
1
n
A
i
)
=
∑
k
=
1
n
(
−
1
)
k
−
1
∑
I
⊂
{
1
,
…
,
n
}
|
I
|
=
k
P
(
A
I
)
,
{\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,n\} \atop \scriptstyle |I|=k}\mathbb {P} (A_{I}),}
对于一般的测度空间 (S ,Σ ,μ )和有限测度的可测 子集A 1 ，……，An ，上面的恒等式也成立，如果把概率测度
P
{\displaystyle \mathbb {P} }
μ 。
如果在容斥原理的概率形式中，交集AI 的概率只与I 中元素的个数有关，也就是说，对于{1, ..., n }中的每一个k ，都存在一个ak ，使得：
a
k
=
P
(
A
I
)
{\displaystyle a_{k}=\mathbb {P} (A_{I})}
I
⊂
{
1
,
…
,
n
}
(
|
I
|
=
k
)
,
{\displaystyle I\subset \{1,\ldots ,n\}\,\,(|I|=k),}
则以上的公式可以简化为：
P
(
⋃
i
=
1
n
A
i
)
=
∑
k
=
1
n
(
−
1
)
k
−
1
(
n
k
)
a
k
{\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}}
这是由于二项式系数
(
n
k
)
{\displaystyle \scriptstyle {\binom {n}{k}}}
类似地，如果对有限集合A 1 ，……，An 的并集的元素个数感兴趣，且对于{1, ..., n }中的每一个k ，交集
A
I
:=
⋂
i
∈
I
A
i
{\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}
的元素个数都相同，例如ak = |AI |，与{1, ..., n }的k 元素子集I 无关，则：
|
⋃
i
=
1
n
A
i
|
=
∑
k
=
1
n
(
−
1
)
k
−
1
(
n
k
)
a
k
.
{\displaystyle {\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}\,.}
在一般的测度空间(S ,Σ ,μ )和有限测度的可测子集A 1 ，……，An 的情况中，也可以进行类似的简化。
欲证明容斥原理，我们首先要验证以下的关于指示函数 的等式：
1
∪
i
=
1
n
A
i
=
∑
k
=
1
n
(
−
1
)
k
−
1
∑
I
⊂
{
1
,
…
,
n
}
|
I
|
=
k
1
A
I
(
∗
)
{\displaystyle 1_{\cup _{i=1}^{n}A_{i}}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,n\} \atop \scriptstyle |I|=k}1_{A_{I}}\qquad (*)}
至少有两种方法来证明这个等式：
第一种方法 我们只需证明对于A 1 ，……，An 的并集中的每一个x ，等式都成立。假设x 正好属于m 个集合（1 ≤ m ≤ n ），不妨设它们为A 1 ，……，Am 。则x 处的等式化为：
1
=
∑
k
=
1
m
(
−
1
)
k
−
1
∑
I
⊂
{
1
,
…
,
m
}
|
I
|
=
k
1.
{\displaystyle 1=\sum _{k=1}^{m}(-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,m\} \atop \scriptstyle |I|=k}1.}
m 元素集合中的k 元素子集的个数，是二项式系数
(
m
k
)
{\displaystyle \textstyle {\binom {m}{k}}}
1
=
(
m
0
)
{\displaystyle \textstyle 1={\binom {m}{0}}}
(
m
0
)
=
∑
k
=
1
m
(
−
1
)
k
−
1
(
m
k
)
.
{\displaystyle {\binom {m}{0}}=\sum _{k=1}^{m}(-1)^{k-1}{\binom {m}{k}}.}
把所有的项移到等式的左端，我们便得到(1 – 1)m x 成立。
第二种方法 设A 表示集合A 1 ，……，An 的并集。于是：
0
=
(
1
A
−
1
A
1
)
(
1
A
−
1
A
2
)
⋯
(
1
A
−
1
A
n
)
,
{\displaystyle 0=(1_{A}-1_{A_{1}})(1_{A}-1_{A_{2}})\cdots (1_{A}-1_{A_{n}})\,,}
这是因为对于不在A 内的x ，两边都等于零，而如果x 属于其中一个集合，例如Am ，则对应的第m 个因子为零。把右端的乘积展开来，便可得到等式(*)。
设
S
1
=
n
(
A
1
)
+
n
(
A
2
)
+
n
(
A
3
)
+
⋯
+
n
(
A
n
)
{\displaystyle S_{1}=n(A_{1})+n(A_{2})+n(A_{3})+\cdots +n(A_{n})}
S
2
=
n
(
A
1
∩
A
2
)
+
n
(
A
1
∩
A
3
)
+
⋯
+
n
(
A
1
∩
A
n
)
+
n
(
A
2
∩
A
3
)
+
⋯
+
n
(
A
n
−
1
∩
A
n
)
{\displaystyle S_{2}=n(A_{1}\cap A_{2})+n(A_{1}\cap A_{3})+\cdots +n(A_{1}\cap A_{n})\;+\;n(A_{2}\cap A_{3})+\cdots +n(A_{n-1}\cap A_{n})}
S
3
=
n
(
A
1
∩
A
2
∩
A
3
)
+
⋯
+
n
(
A
n
−
2
∩
A
n
−
1
∩
A
n
)
{\displaystyle S_{3}=n(A_{1}\cap A_{2}\cap A_{3})+\cdots +n(A_{n-2}\cap A_{n-1}\cap A_{n})}
⋮
S
n
=
n
(
A
1
∩
A
2
∩
A
3
∩
⋯
∩
A
n
)
{\displaystyle S_{n}=n(A_{1}\cap A_{2}\cap A_{3}\cap \cdots \cap A_{n})}
求证
n
(
A
1
∪
A
2
∪
A
3
∪
⋯
∪
A
n
)
=
S
1
−
S
2
+
S
3
−
⋯
+
(
−
1
)
n
−
1
S
n
.
{\displaystyle n(A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{n-1}S_{n}.}
证明：
当
n
=
2
{\displaystyle n=2}
n
(
A
1
∪
A
2
)
=
n
(
A
1
)
+
n
(
A
2
)
−
n
(
A
1
∩
A
2
)
=
S
1
−
S
2
.
{\displaystyle n(A_{1}\cup A_{2})=n(A_{1})+n(A_{2})-n(A_{1}\cap A_{2})=S_{1}-S_{2}.}
假设当
n
=
k
(
k
≥
2
)
{\displaystyle n=k\ (k\geq 2)}
n
(
A
1
∪
A
2
∪
⋯
∪
A
k
)
=
S
1
−
S
2
+
S
3
−
⋯
+
(
−
1
)
k
−
1
S
k
.
{\displaystyle n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{k-1}S_{k}.}
当
n
=
k
+
1
{\displaystyle n=k+1}
n
(
A
1
∪
A
2
∪
⋯
∪
A
k
∪
A
k
+
1
)
=
n
(
(
A
1
∪
A
2
∪
⋯
∪
A
k
)
∪
A
k
+
1
)
=
n
(
A
1
∪
A
2
∪
⋯
∪
A
k
)
+
n
(
A
k
+
1
)
−
n
(
(
A
1
∪
A
2
∪
⋯
∪
A
k
)
∩
A
k
+
1
)
=
n
(
A
1
∪
A
2
∪
⋯
∪
A
k
)
+
n
(
A
k
+
1
)
−
n
(
(
A
1
∩
A
k
+
1
)
∪
(
A
2
∩
A
k
+
1
)
∪
⋯
∪
(
A
k
∩
A
k
+
1
)
)
.
{\displaystyle {\begin{aligned}n(A_{1}\cup A_{2}\cup \cdots \cup A_{k}\cup A_{k+1})&=n{\Bigl (}(A_{1}\cup A_{2}\cup \cdots \cup A_{k})\cup A_{k+1}{\Bigr )}\\[1ex]&=n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})+n(A_{k+1})\\[1ex]&\quad -n{\Bigl (}(A_{1}\cup A_{2}\cup \cdots \cup A_{k})\cap A_{k+1}{\Bigr )}\\[1ex]&=n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})+n(A_{k+1})\\[1ex]&\quad -n{\Bigl (}(A_{1}\cap A_{k+1})\cup (A_{2}\cap A_{k+1})\cup \cdots \cup (A_{k}\cap A_{k+1}){\Bigr )}.\end{aligned}}}
∵ 当 \(n=k\) 时，上式成立，
∴
n
(
A
1
∪
A
2
∪
⋯
∪
A
k
+
1
)
=
S
1
−
S
2
+
S
3
−
⋯
+
(
−
1
)
k
S
k
+
1
.
{\displaystyle n(A_{1}\cup A_{2}\cup \cdots \cup A_{k+1})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{k}S_{k+1}.}
综上所述，当
n
≥
2
{\displaystyle n\geq 2}
n
(
A
1
∪
A
2
∪
⋯
∪
A
n
)
=
n
(
A
1
)
+
n
(
A
2
)
+
⋯
+
n
(
A
n
)
−
[
n
(
A
1
∩
A
2
)
+
n
(
A
1
∩
A
3
)
+
⋯
+
n
(
A
n
−
1
∩
A
n
)
]
+
[
n
(
A
1
∩
A
2
∩
A
3
)
+
⋯
]
−
⋯
+
(
−
1
)
n
−
1
n
(
A
1
∩
A
2
∩
⋯
∩
A
n
)
.
{\displaystyle {\begin{aligned}n(A_{1}\cup A_{2}\cup \cdots \cup A_{n})=&\;n(A_{1})+n(A_{2})+\cdots +n(A_{n})\\[1ex]&\;-{\Bigl [}n(A_{1}\cap A_{2})+n(A_{1}\cap A_{3})+\cdots +n(A_{n-1}\cap A_{n}){\Bigr ]}\\[1ex]&\;+{\Bigl [}n(A_{1}\cap A_{2}\cap A_{3})+\cdots {\Bigr ]}\\[1ex]&\;-\cdots +(-1)^{n-1}n(A_{1}\cap A_{2}\cap \cdots \cap A_{n}).\end{aligned}}}
有时容斥原理用以下的形式来表述：如果
g
(
A
)
=
∑
S
:
S
⊆
A
f
(
S
)
{\displaystyle g(A)=\sum _{S\,:\,S\subseteq A}f(S)}
那么：
f
(
A
)
=
∑
S
:
S
⊆
A
(
−
1
)
|
A
|
−
|
S
|
g
(
S
)
{\displaystyle f(A)=\sum _{S\,:\,S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)}
在这种形式中可以看出，它是A 的所有子集的偏序集合 的指标代数 的莫比乌斯反演公式 。
在许多情况下，容斥原理都可以给出精确的公式（特别是用埃拉托斯特尼筛法 计算素数 的个数时），但是用处不大，这是因为它里面含有的项太多。即使每一个单独的项都可以准确地估计，误差累积起来仍然意味着容斥原理不能直接应用。在数论 中，这个困难由维戈·布朗 解决。开始时进展很慢，但他的想法逐渐被其他数学家所应用，于是便产生了许多各种各样的筛法 。这些方法是尝试找出被“筛选”的集合的上界，而不是一个确切的公式。
容斥原理的一个著名的应用，是计算一个有限集合的所有乱序 排列的数目。一个集合A 的错排 ，是从A 到A 的没有不动点的双射 。通过容斥原理，我们可以证明，如果A 含有n 个元素，则乱序排列的数目为[n ! / e ]，其中[x ]表示最接近x 的整数。
这也称为n 的子阶乘 ，记为!n 。可以推出，如果所有的双射都有相同的概率，则当n 增大时，一个随机双射是错排的概率迅速趋近于1/e 。
容斥原理与德·摩根定理 结合起来，也可以用于计算集合的交集中元素的数目。设
A
¯
k
{\displaystyle \scriptstyle {\overline {A}}_{k}}
A k A 的补集 ，使得对于每一个k ，都有
A
k
⊆
A
{\displaystyle \scriptstyle A_{k}\,\subseteq \,A}
⋂
i
=
1
n
A
i
=
⋃
i
=
1
n
A
¯
i
¯
{\displaystyle \bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A}}_{i}}}}
这样便把计算交集的问题化为计算并集的问题。
本條目含有来自PlanetMath 《principle of inclusion-exclusion 》的內容，版权遵守知识共享协议：署名-相同方式共享 协议 。
![{\displaystyle {\begin{aligned}n(A_{1}\cup A_{2}\cup \cdots \cup A_{k}\cup A_{k+1})&=n{\Bigl (}(A_{1}\cup A_{2}\cup \cdots \cup A_{k})\cup A_{k+1}{\Bigr )}\\[1ex]&=n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})+n(A_{k+1})\\[1ex]&\quad -n{\Bigl (}(A_{1}\cup A_{2}\cup \cdots \cup A_{k})\cap A_{k+1}{\Bigr )}\\[1ex]&=n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})+n(A_{k+1})\\[1ex]&\quad -n{\Bigl (}(A_{1}\cap A_{k+1})\cup (A_{2}\cap A_{k+1})\cup \cdots \cup (A_{k}\cap A_{k+1}){\Bigr )}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a928bd5379ef560ae1b36d5de985873e250823a)
![{\displaystyle {\begin{aligned}n(A_{1}\cup A_{2}\cup \cdots \cup A_{n})=&\;n(A_{1})+n(A_{2})+\cdots +n(A_{n})\\[1ex]&\;-{\Bigl [}n(A_{1}\cap A_{2})+n(A_{1}\cap A_{3})+\cdots +n(A_{n-1}\cap A_{n}){\Bigr ]}\\[1ex]&\;+{\Bigl [}n(A_{1}\cap A_{2}\cap A_{3})+\cdots {\Bigr ]}\\[1ex]&\;-\cdots +(-1)^{n-1}n(A_{1}\cap A_{2}\cap \cdots \cap A_{n}).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dde2497a1d78a6b55c5cb0d9b27c6648a6efe63a)
