排容原理

-{T|zh-hans:容斥原理;zh-hant:排容原理}-

-{A|zh-hans:容斥原理;zh-hant:排容原理}-（inclusion-exclusion principle）又称-{zh-hans:排容原理;zh-hant:容斥原理}-，在組合數學裏，其說明若 $A_{1}$ , ..., $A_{n}$ 為有限集，則 $\begin{matrix} | ⋃_{i = 1}^{n} A_{i} | = & \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} | - \dots + (- 1)^{n - 1} | A_{1} \cap \dots \cap A_{n} | . \end{matrix}$

其中 $| A |$ 表示 $A$ 的基數。例如在兩個集的情況時，我們可以通過將 $| A |$ 和 $| B |$ 相加，再減去其交集的基數，而得到其并集的基數。

描述

两个集合的容斥原理

$| A \cup B | = | A | + | B | - | A \cap B |$

三个集合的容斥原理

$| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |$

$n$ 个集合的容斥原理

要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。

最终得到公式：

$\begin{matrix} | ⋃_{i = 1}^{n} A_{i} | = & \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} | - \dots + (- 1)^{n - 1} | A_{1} \cap \dots \cap A_{n} | . \end{matrix}$

又可写成

$| ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} (- 1)^{k + 1} (\sum_{1 \leq i_{1} < \dots < i_{k} \leq n} | A_{i_{1}} \cap \dots \cap A_{i_{k}} |)$

或

$| ⋃_{i = 1}^{n} A_{i} | = \sum_{\emptyset \neq J \subseteq {1, 2, \dots, n}} (- 1)^{| J | - 1} | ⋂_{j \in J} A_{j} | .$

概率论中的容斥原理

在概率论中，对于概率空间 $(Ω, ℱ, ℙ)$ 中的事件A₁，……，A_n，当n = 2时容斥原理的公式为：

ℙ (A_{1} \cup A_{2}) = ℙ (A_{1}) + ℙ (A_{2}) - ℙ (A_{1} \cap A_{2}),

当n = 3时，公式为：

ℙ (A_{1} \cup A_{2} \cup A_{3}) = ℙ (A_{1}) + ℙ (A_{2}) + ℙ (A_{3}) - ℙ (A_{1} \cap A_{2}) - ℙ (A_{1} \cap A_{3}) - ℙ (A_{2} \cap A_{3}) + ℙ (A_{1} \cap A_{2} \cap A_{3})

一般地：

ℙ (⋃_{i = 1}^{n} A_{i}) = \sum_{i = 1}^{n} ℙ (A_{i}) - \sum_{i, j : i < j} ℙ (A_{i} \cap A_{j}) + \sum_{i, j, k : i < j < k} ℙ (A_{i} \cap A_{j} \cap A_{k}) - \dots + (- 1)^{n - 1} ℙ (⋂_{i = 1}^{n} A_{i}),

也可以写成：

ℙ (⋃_{i = 1}^{n} A_{i}) = \sum_{k = 1}^{n} (- 1)^{k - 1} \sum_{\binom{I \subset {1, \dots, n}}{| I | = k}} ℙ (A_{I}),

对于一般的测度空间(S,Σ,μ)和有限测度的可测子集A₁，……，A_n，上面的恒等式也成立，如果把概率测度 $ℙ$ 换为测度μ。

特殊情况

如果在容斥原理的概率形式中，交集A_I的概率只与I中元素的个数有关，也就是说，对于{1, ..., n}中的每一个k，都存在一个a_k，使得：

a_{k} = ℙ (A_{I})

，对于每一个

I \subset {1, \dots, n} (| I | = k),

则以上的公式可以简化为：

ℙ (⋃_{i = 1}^{n} A_{i}) = \sum_{k = 1}^{n} (- 1)^{k - 1} (\binom{n}{k}) a_{k}

这是由于二项式系数 $(\binom{n}{k})$ 的组合解释。

类似地，如果对有限集合A₁，……，A_n的并集的元素个数感兴趣，且对于{1, ..., n}中的每一个k，交集

A_{I} : = ⋂_{i \in I} A_{i}

的元素个数都相同，例如a_k = |A_I|，与{1, ..., n}的k元素子集I无关，则：

| ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} (- 1)^{k - 1} (\binom{n}{k}) a_{k} .

在一般的测度空间(S,Σ,μ)和有限测度的可测子集A₁，……，A_n的情况中，也可以进行类似的简化。

容斥原理的证明

欲证明容斥原理，我们首先要验证以下的关于指示函数的等式：

1_{\cup_{i = 1}^{n} A_{i}} = \sum_{k = 1}^{n} (- 1)^{k - 1} \sum_{\binom{I \subset {1, \dots, n}}{| I | = k}} 1_{A_{I}} (*)

至少有两种方法来证明这个等式：

第一种方法 我们只需证明对于A₁，……，A_n的并集中的每一个x，等式都成立。假设x正好属于m个集合（1 ≤ m ≤ n），不妨设它们为A₁，……，A_m。则x处的等式化为：

1 = \sum_{k = 1}^{m} (- 1)^{k - 1} \sum_{\binom{I \subset {1, \dots, m}}{| I | = k}} 1 .

m元素集合中的k元素子集的个数，是二项式系数 $(\binom{m}{k})$ 的组合解释。由于 $1 = (\binom{m}{0})$ ，我们有：

(\binom{m}{0}) = \sum_{k = 1}^{m} (- 1)^{k - 1} (\binom{m}{k}) .

把所有的项移到等式的左端，我们便得到(1 – 1)^m的二项式展开式，因此可以看出，(*)对x成立。

第二种方法 设A表示集合A₁，……，A_n的并集。于是：

0 = (1_{A} - 1_{A_{1}}) (1_{A} - 1_{A_{2}}) \dots (1_{A} - 1_{A_{n}}),

这是因为对于不在A内的x，两边都等于零，而如果x属于其中一个集合，例如A_m，则对应的第m个因子为零。把右端的乘积展开来，便可得到等式(*)。

归纳法证明

设 $S_{1} = n (A_{1}) + n (A_{2}) + n (A_{3}) + \dots + n (A_{n})$

$S_{2} = n (A_{1} \cap A_{2}) + n (A_{1} \cap A_{3}) + \dots + n (A_{1} \cap A_{n}) + n (A_{2} \cap A_{3}) + \dots + n (A_{n - 1} \cap A_{n})$

$S_{3} = n (A_{1} \cap A_{2} \cap A_{3}) + \dots + n (A_{n - 2} \cap A_{n - 1} \cap A_{n})$

⋮

$S_{n} = n (A_{1} \cap A_{2} \cap A_{3} \cap \dots \cap A_{n})$

求证 $n (A_{1} \cup A_{2} \cup A_{3} \cup \dots \cup A_{n}) = S_{1} - S_{2} + S_{3} - \dots + (- 1)^{n - 1} S_{n} .$

证明：当 $n = 2$ 时， $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 \geq 2)$ 时，有 $n (A_{1} \cup A_{2} \cup \dots \cup A_{k}) = S_{1} - S_{2} + S_{3} - \dots + (- 1)^{k - 1} S_{k} .$

当 $n = k + 1$ 时， $\begin{matrix} n (A_{1} \cup A_{2} \cup \dots \cup A_{k} \cup A_{k + 1}) & = n ((A_{1} \cup A_{2} \cup \dots \cup A_{k}) \cup A_{k + 1}) \\ = n (A_{1} \cup A_{2} \cup \dots \cup A_{k}) + n (A_{k + 1}) \\ - n ((A_{1} \cup A_{2} \cup \dots \cup A_{k}) \cap A_{k + 1}) \\ = n (A_{1} \cup A_{2} \cup \dots \cup A_{k}) + n (A_{k + 1}) \\ - n ((A_{1} \cap A_{k + 1}) \cup (A_{2} \cap A_{k + 1}) \cup \dots \cup (A_{k} \cap A_{k + 1})) . \end{matrix}$

∵ 当 $n=k$ 时，上式成立， ∴ $n (A_{1} \cup A_{2} \cup \dots \cup A_{k + 1}) = S_{1} - S_{2} + S_{3} - \dots + (- 1)^{k} S_{k + 1} .$

综上所述，当 $n \geq 2$ 时， $\begin{matrix} n (A_{1} \cup A_{2} \cup \dots \cup A_{n}) = & n (A_{1}) + n (A_{2}) + \dots + n (A_{n}) \\ - [n (A_{1} \cap A_{2}) + n (A_{1} \cap A_{3}) + \dots + n (A_{n - 1} \cap A_{n})] \\ + [n (A_{1} \cap A_{2} \cap A_{3}) + \dots] \\ - \dots + (- 1)^{n - 1} n (A_{1} \cap A_{2} \cap \dots \cap A_{n}) . \end{matrix}$

其它形式

有时容斥原理用以下的形式来表述：如果

g (A) = \sum_{S : S \subseteq A} f (S)

那么：

f (A) = \sum_{S : S \subseteq A} (- 1)^{| A | - | S |} g (S)

在这种形式中可以看出，它是A的所有子集的偏序集合的指标代数的莫比乌斯反演公式。

应用

在许多情况下，容斥原理都可以给出精确的公式（特别是用埃拉托斯特尼筛法计算素数的个数时），但是用处不大，这是因为它里面含有的项太多。即使每一个单独的项都可以准确地估计，误差累积起来仍然意味着容斥原理不能直接应用。在数论中，这个困难由维戈·布朗解决。开始时进展很慢，但他的想法逐渐被其他数学家所应用，于是便产生了许多各种各样的筛法。这些方法是尝试找出被“筛选”的集合的上界，而不是一个确切的公式。

错排

容斥原理的一个著名的应用，是计算一个有限集合的所有乱序排列的数目。一个集合A的错排，是从A到A的没有不动点的双射。通过容斥原理，我们可以证明，如果A含有n个元素，则乱序排列的数目为[n! / e]，其中[x]表示最接近x的整数。

这也称为n的子阶乘，记为!n。可以推出，如果所有的双射都有相同的概率，则当n增大时，一个随机双射是错排的概率迅速趋近于1/e。

交集的计算

容斥原理与德·摩根定理结合起来，也可以用于计算集合的交集中元素的数目。设 ${\overline{A}}_{k}$ 表示A_k关于全集A的补集，使得对于每一个k，都有 $A_{k} \subseteq A$ 。于是，我们有：

⋂_{i = 1}^{n} A_{i} = \overline{⋃_{i = 1}^{n} {\overline{A}}_{i}}

这样便把计算交集的问题化为计算并集的问题。

参见

拓展阅读

-{R|http://cs.tju.edu.cn/faculty/zhangkl/teaching/comb/lec09.pdf}- Template:Wayback

-{R|http://blog.sina.com.cn/s/blog_6be9596c0100miag.html}- Template:Wayback

-{R|http://e-maxx.ru/algo/inclusion_exclusion_principle}- Template:Wayback Template:Wayback（俄文）中文翻译：-{R|http://www.cppblog.com/vici/archive/2011/09/05/155103.html}- Template:Wayback

参考文献

Template:Reflist

Klaus Dohmen: Improved Bonferroni Inequalities via Abstract Tubes - Inequalities and Identities of Inclusion-Exclusion Type, Springer-Verlag, 2003, ISBN 3-540-20025-8.
Stasys Jukna: Extremal Combinatorics, Springer, 2001, ISBN 3-540-66313-4.
-{R|http://blog.csdn.net/xianglunxi/article/details/9310105}- Template:Wayback

Template:Planetmath

排容原理

目录

描述

两个集合的容斥原理

三个集合的容斥原理

$n$ 个集合的容斥原理

概率论中的容斥原理

特殊情况

容斥原理的证明

归纳法证明

其它形式

应用

错排

交集的计算

参见

拓展阅读

参考文献

导航菜单

排容原理

描述

两个集合的容斥原理

三个集合的容斥原理

n个集合的容斥原理

概率论中的容斥原理

特殊情况

容斥原理的证明

归纳法证明

其它形式

应用

错排

交集的计算

参见

拓展阅读

参考文献

导航菜单

搜索

$n$ 个集合的容斥原理