排容原理

维库，知识与思想的自由文库

(重定向自容斥原理)

跳转到: 导航, 搜索

3个分类: 扩充中的条目 | 缺少来源的条目 | 离散数学

这个条目（或其中的一段）被请求扩充。
完成扩充后请移除这个提示。详情請參閱讨论页和WikiLib:扩充请求。

本節或条目没有引用其参考或来源。
請加上適當的資料來源或引用來改善這篇條目。

三個集的情況

排容原理又称容斥原理，在組合數學里，其說明若 $A 1$ , ..., $A n$ 為有限集，則

$\left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right| -\sum_{i,j\,:\,i\neq j}\left|A_i\cap A_j\right|$ $+\sum_{i,j,k\,:\,i\neq j\neq k\neq i}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\cdots\ \pm \left|A_1\cap\cdots\cap A_n\right|$

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

排容原理亦可用於機率的計算上：

$P\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n P\left(A_i\right) -\sum_{i,j\,:\,i\neq j}P\left(A_i\cap A_j\right)$ $+\sum_{i,j,k\,:\,i\neq j\neq k\neq i}P\left(A_i\cap A_j\cap A_k\right)-\ \cdots\cdots\ \pm P\left(\bigcap_{i=1}^n A_i\right)$