# 容斥原理

有限indexed set family的union cardinality是全部非空index subsets交集大小的交替和。

mko-inclusion-exclusion-principle · theorem · v0.10.0



## 數學敘述

對每個非空I⊆[n]使用(-1)^(|I|+1)|intersection_i in I A_i|；odd-order正、even-order負。重複sets仍按indices處理，empty intersections可為0，n=0約定union與sum皆0。只用singles/pairs對n>=3不是exact inclusion-exclusion，截斷只能另稱Bonferroni bound。





## 代表公式（精確 TeX）

I(A)





## 成立條件


- 完整有限indexed family，每個set是明示有限整數set。
- general family枚舉全部2^n-1個nonempty index subsets。





## 符號作用域


- I — 容斥交替和
- A — 有限集合族





## 直觀、定義與常見誤解

全部nonempty index subsets缺一不可。

交替符號由intersection order決定。

pairwise truncation不是一般exact formula。

三集合以上仍只減pairwise intersections而遺漏higher intersections。





## 已採用的推導導讀

[三集合全部七個交集項](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-inclusion-exclusion-principle-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [集合運算](https://ocme.evemisslab.com/zh-Hant/mko/mko-set-operations/) — union與intersections。
- [基本計數原理](https://ocme.evemisslab.com/zh-Hant/mko/mko-counting-principle/) — cardinalities。
- [集合基數比較](https://ocme.evemisslab.com/zh-Hant/mko/mko-cardinality-comparison/) — 有限大小。
- [數學歸納法](https://ocme.evemisslab.com/zh-Hant/mko/mko-mathematical-induction/) — 一般有限家族定理。





## 驗證界線

只處理有限families；Bonferroni bounds須另行標示。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。





## 下一個義務

加入generating functions與Catalan counting。





## 同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/inclusion-exclusion-principle.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-inclusion-exclusion-principle/index.md)