inclusion–exclusion principle

容斥原理

Combinatorics · Undergraduate · Mathematics Resources editorial compilation (AI-assisted)

Other names / variants: PIE · principle of inclusion and exclusion

Translation evidence: Literature usage

Meaning in context

For finite sets A_1,…,A_m, the size of their union is the sum over nonempty index sets S of (−1)^(|S|+1) times the size of the intersection indexed by S.

对有限集合 A_1,…,A_m，并集大小等于各非空指标子集对应的交集大小按交集阶数交替加减所得的和。

Example

If $|A|=7$, $|B|=6$, and $|A\cap B|=2$, then $|A\cup B|=11$.

Usage and distinctions

In a complement formula the empty intersection is the specified universe; its sign is positive.

Read the encyclopedia explanation

Recommended reading in this subject · Preparation & skip guidance

Definition sources

1. Keller and Trotter — Applied Combinatorics (2016)Section 7.2, Theorem 7.7 and equation (7.2.1) · Checked 2026-10-14

Translation sources

1. 上海交通大学 — CS0901 组合数学（2026）§3.1，定理3.1「容斥原理」 · Checked 2026-10-14

Original encyclopedia and terminology content: CC BY-SA 4.0. Contribute or report a correction.