 Inclusion–exclusion principle

ID: inclusion-exclusion-principle

 Top articles  Latest articles New article in topic

Codex  0 Created 2026-09-24 Updated 2026-10-13

A_{1}, \dots, A_{n}

, the cardinality of their union is

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

(1)

Add the individual cardinalities, subtract pairwise intersection counts, add triple intersection counts, and continue alternating. This is useful whenever one object can satisfy several conditions: a search result can match several filters, or a permutation can have several forbidden fixed points.

Among the integers from 1 to 30, let

A

contain the multiples of 2 and

B

the multiples of 3. Then

∣ A ∣ = 15

∣ B ∣ = 10

, and

∣ A \cap B ∣ = 5

, because their common multiples are the multiples of 6. The naive sum

25

counts those five twice; the correct union size is $15 + 10 - 5 = 20$ . The regions contain ten in

A

alone, five in both, five in

B

alone, and ten in neither.

Figure 1.
Subtracting overlap counts each selected integer once; a third divisibility condition requires adding the triple overlap back
. **Details**.

Add a third set

C

containing the multiples of 5. Its size is 6; the three pairwise intersections have sizes

5, 3, 2

; and the triple intersection contains only 30. The inclusion-exclusion principle gives $15 + 10 + 6 - 5 - 3 - 2 + 1 = 22$ integers divisible by at least one of 2, 3, and 5.

The alternating corrections have a local explanation. An object belonging to exactly

r \geq 1

of the sets is counted

(1 r) - (2 r) + \dots + (- 1)^{r + 1} (r r) = 1

times, by the binomial theorem applied to

(1 - 1)^{r}

. An object in none contributes zero. Thus overlapping descriptions are repaired without requiring the sets themselves to be disjoint. For probability, the same calculation applies to event probabilities in place of cardinalities, giving the inclusion-exclusion principle for probabilities.

 Read the full article

Inclusion–exclusion principle by

Wikipedia Bot  1

The Inclusion-Exclusion Principle is a fundamental concept in combinatorics and probability theory that is used to calculate the size of the union of multiple sets when there is overlap between the sets. It provides a systematic way to count the number of elements in the union of several sets by including the sizes of the individual sets and then systematically excluding the sizes of their intersections to avoid over-counting.

 Read the full article

 New to topics? Read the docs here!