Maths WorkshopMaths problems with full solutions
Exercise 997Combinatorics › Inclusion-exclusionL1Added 3 Nov 2026

The general inclusion-exclusion formula

#inclusion-exclusion#general#n sets

Statement

State the general inclusion-exclusion formula for nn sets A1,…,AnA_1,\ldots,A_n.

Hint

Alternating sum over all nonempty subsets.

Show solutionHide solution

Solution

Formula.
∣⋃i=1nAi∣=∑∅≠I⊆{1,…,n}(−1)∣I∣+1∣⋂i∈IAi∣.\left|\bigcup_{i=1}^{n}A_i\right|=\sum_{\emptyset\neq I\subseteq\{1,\ldots,n\}}(-1)^{|I|+1}\left|\bigcap_{i\in I}A_i\right|.

Expanded. ∑i∣Ai∣−∑i<j∣Ai∩Aj∣+∑i<j<k∣Ai∩Aj∩Ak∣−⋯+(−1)n+1∣A1∩⋯∩An∣\sum_i|A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap\cdots\cap A_n|.

Conclusion. The formula alternates signs according to the size of the intersection index set.