容斥原理

數學敘述

對每個非空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。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 集合運算 — union與intersections。
• 基本計數原理 — cardinalities。
• 集合基數比較 — 有限大小。
• 數學歸納法 — 一般有限家族定理。

驗證界線

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

not_formalized

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

下一個義務

加入generating functions與Catalan counting。

同源結構化資料

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