Maths WorkshopMaths problems with full solutions
Exercise 485Combinatorics › Inclusion-exclusionHigh schoolAdded 3 Nov 2026

Summary of inclusion-exclusion

#summary#IE#formulas

Statement

Summarize the key inclusion-exclusion formulas.

Hint

Review the main identities.

Show solutionHide solution

Solution

Two sets. ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|.

Three sets. ∣A∪B∪C∣=∑∣Ai∣−∑∣Ai∩Aj∣+∣A∩B∩C∣|A\cup B\cup C|=\sum|A_i|-\sum|A_i\cap A_j|+|A\cap B\cap C|.

General.
∣⋃iAi∣=∑∅≠I(−1)∣I∣+1∣⋂i∈IAi∣.\left|\bigcup_i A_i\right|=\sum_{\emptyset\neq I}(-1)^{|I|+1}\left|\bigcap_{i\in I}A_i\right|.

Derangements. Dn=n!∑k=0n(−1)k/k!D_n=n!\sum_{k=0}^n(-1)^k/k!.

Surjections. Surj(m,n)=∑k=0n(−1)k(nk)(n−k)m\text{Surj}(m,n)=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^m.

Exactly kk properties. Ek=∑j=kn(−1)j−k(jk)NjE_k=\sum_{j=k}^n(-1)^{j-k}\binom{j}{k}N_j.

Conclusion. IE is one of the most versatile counting tools, applicable to unions, complements, derangements, surjections, and beyond.