Course contentsShow
← Mathematics
Lesson 2619 of 3,12152. CombinatoricsFree lesson

The General Inclusion-Exclusion Principle

Stating the formula for n sets with alternating sums over all intersections.

The General Inclusion-Exclusion Principle

What you'll learn: How to count elements in any union of n sets using a single alternating-sum formula.

The Big Picture

You've seen inclusion-exclusion for two and three sets. Now we extend this to any finite number of sets with one elegant formula. The pattern you observed—add individual sets, subtract pairs, add triples, subtract quadruples—continues indefinitely.

The General Formula

For sets (A_1, A_2, \ldots, A_n), the number of elements in their union is:

[ |A_1 \cup A_2 \cup \cdots \cup A_n| = \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 A_2 \cap \cdots \cap A_n| ]

In plain English:

  1. Add the sizes of all individual sets
  2. Subtract the sizes of all 2-way intersections
  3. Add back the sizes of all 3-way intersections
  4. Subtract all 4-way intersections
  5. Continue alternating signs...
  6. The last term involves all n sets together

Why the Pattern?

Think of it as correcting overcounting layer by layer. An element in exactly k sets gets counted (\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots) times, which equals exactly 1 (a beautiful binomial identity!). Elements in none of the sets contribute 0, as desired.

The Compact Notation

Using set notation: [ \left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \neq S \subseteq {1,\ldots,n}} (-1)^{|S|+1} \left|\bigcap_{i \in S} A_i\right| ]

This sums over all non-empty subsets S, alternating signs based on subset size.

Key Takeaway: The general inclusion-exclusion principle counts the union of n sets by alternating between adding and subtracting the sizes of all possible intersections, correcting for multiple overlaps systematically.