The Principle of Inclusion-Exclusion: Formulation and Proof

Welcome back! In the previous module, we delved into the Pigeonhole Principle, a powerful tool for proving the existence of certain properties in combinatorial structures. We culminated our study by proving the elegant Erdős-Szekeres theorem, which guarantees order within seemingly random sequences.

Today, we pivot from existence proofs to the art of precise counting. We will introduce another fundamental pillar of combinatorics: the Principle of Inclusion-Exclusion (PIE). While the sum rule allows us to count disjoint sets, PIE gives us a systematic method for counting the elements in a union of overlapping sets by cleverly adding and subtracting the parts that have been overcounted. This principle is indispensable for tackling a vast range of complex counting problems you'll encounter in higher-level combinatorics.

Our learning outcome for this lesson is to formulate and prove the general Principle of Inclusion-Exclusion.

The Intuition: Correcting for Overlaps

Before diving into a general formula, let's build our intuition. You're already familiar with the simplest case of PIE for two sets, A and B. When we want to find the size of their union, $∣ A \cup B ∣$ , a naive first attempt would be to simply add their sizes: $∣ A ∣ + ∣ B ∣$ . However, any elements in the intersection $A \cap B$ have been counted twice. To correct this, we subtract the size of the intersection once.

This gives us the familiar formula:

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

Now, let's extend this to three sets: A, B, and C.

Principle of Inclusion-Exclusion - AoPS Wiki - Art of Problem Solving

This article from the Art of Problem Solving Wiki provides a clear, step-by-step development of the intuition behind PIE.

Start by reading the Two Set Example for a quick refresher. Then, carefully read the Three Set Example, which breaks down the process of overcounting and correction for three sets. Pay close attention to how the elements in the triple intersection are first added three times, then subtracted three times, and finally need to be added back in.

The logic you just read for three sets leads to the formula:

∣ A \cup B \cup C ∣ = (∣ A ∣ + ∣ B ∣ + ∣ C ∣) - (∣ A \cap B ∣ + ∣ A \cap C ∣ + ∣ B \cap C ∣) + ∣ A \cap B \cap C ∣

This process is visualized perfectly in the following diagram, which shows how many times each region is counted at each stage of the formula.

The Venn diagrams illustrate the counting process for PIE with three sets. (Left) Naively summing the sets overcounts the intersections. (Center) Subtracting pairwise intersections undercounts the central region. (Right) Adding the triple intersection back results in each region being counted exactly once.

Notice the pattern: we add the sizes of single sets, subtract the sizes of pairwise intersections, and then add back the size of the triple intersection. This alternating sum is the core idea of the principle.

The General Formula

We can now generalize this pattern to any number of finite sets, $A_{1}, A_{2}, \dots, A_{n}$ . This gives us the formal statement of the Principle of Inclusion-Exclusion.

The Principle of Inclusion-Exclusion (PIE): For finite sets $A_{1}, A_{2}, \dots, A_{n}$ , the size of their union is given by:

i = 1 ⋃ n A_{i} = i \sum ∣ A_{i} ∣ - i < j \sum ∣ A_{i} \cap A_{j} ∣ + i < j < k \sum ∣ A_{i} \cap A_{j} \cap A_{k} ∣ - \dots + (- 1)^{n - 1} ∣ A_{1} \cap \dots \cap A_{n} ∣

Using more compact summation notation, this is:

i = 1 ⋃ n A_{i} = \emptyset \neq = I \subseteq {1, \dots, n} \sum (- 1)^{∣ I ∣ - 1} i \in I ⋂ A_{i}

This formula states that to find the size of the union, we sum the sizes of all non-empty intersections, with the sign determined by whether the number of sets in the intersection is odd or even.

Proof of the Principle

Stating the formula is one thing; proving its universal correctness is another. We'll explore two distinct proofs that offer different insights into why PIE works. This aligns with your goal of gaining a deep and versatile understanding of combinatorics.

Proof 1: The Combinatorial Argument

The most intuitive proof involves showing that every element in the union is counted exactly once on the right-hand side of the equation.

Let's consider an arbitrary element $x$ that belongs to the union $⋃_{i = 1}^{n} A_{i}$ . Suppose that $x$ is a member of exactly $k$ of these sets, where $k \geq 1$ . We need to show that this element $x$ contributes a net count of exactly 1 to the right-hand side of the PIE formula.

The first term, $\sum ∣ A_{i} ∣$ , counts $x$ exactly $(1 k)$ times.
The second term, $\sum ∣ A_{i} \cap A_{j} ∣$ , subtracts the count of $x$ exactly $(2 k)$ times, since $x$ is in $(2 k)$ of the pairwise intersections.
The third term adds the count of $x$ back $(3 k)$ times.
...and so on.

The total number of times $x$ is counted is:

Count (x) = (1 k) - (2 k) + (3 k) - \dots + (- 1)^{k - 1} (k k)

Recall the binomial theorem identity: $(1 + x)^{k} = \sum_{i = 0}^{k} (i k) x^{i}$ . If we set $x = - 1$ , we get:

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

Rearranging this gives us:

(0 k) = (1 k) - (2 k) + (3 k) - \dots + (- 1)^{k - 1} (k k)

Since $(0 k) = 1$ , the total count for our element $x$ is exactly 1. This holds for any element in the union, so the formula is correct.

This video provides a great walkthrough of this argument, framing it in terms of "conditions" an element might satisfy.

INCLUSION-EXCLUSION PRINCIPLE - DISCRETE MATHEMATICS

This video from TrevTutor presents the general formula for PIE and gives a formal proof using the combinatorial argument we just discussed.

Watch the segment from this timestamp where the presenter proves why an element lying in the intersection of r sets is counted exactly once by the formula. The video uses r where we used k, but the logic is identical.

Proof 2: An Algebraic Approach with Characteristic Functions

For a different and highly elegant perspective, we can use an algebraic tool called characteristic functions. This method transforms the problem from counting elements in sets to manipulating simple functions.

2 The Principle of Inclusion-Exclusion

This document provides a formal proof of PIE using characteristic functions. It's a powerful technique common in advanced combinatorics.

First, read the introductory section to understand the definition and properties of characteristic functions. Pay special attention to the identities listed in Proposition 2.0.2. Next, read the main proof in the section titled "The Main Result: PIE". Focus on how the proof reduces the problem of counting elements to proving an identity for these functions for a single element x.

Let's summarize the key steps of this algebraic proof:

Define the Characteristic Function: For a subset $A$ of a universal set $S$ , the characteristic function $1_{A} (s)$ is 1 if $s \in A$ and 0 otherwise. A key property is that $∣ A ∣ = \sum_{s \in S} 1_{A} (s)$ .
Relate Set Operations to Algebra:
- Intersection: $1_{A \cap B} = 1_{A} \cdot 1_{B}$
- Complement: $1_{A^{c}} = 1 - 1_{A}$
Express the Union: Using De Morgan's laws, the union $U = A_{1} \cup \dots \cup A_{n}$ can be written as the complement of an intersection: $U = (A_{1}^{c} \cap \dots \cap A_{n}^{c})^{c}$ .
Translate to Characteristic Functions: $1_{U} = 1 - 1_{A_{1}^{c} \cap \dots \cap A_{n}^{c}} = 1 - (1_{A_{1}^{c}} \cdot \dots \cdot 1_{A_{n}^{c}})$ Substituting $1_{A_{i}^{c}} = 1 - 1_{A_{i}}$ , we get: $1_{U} = 1 - (1 - 1_{A_{1}}) (1 - 1_{A_{2}}) \dots (1 - 1_{A_{n}})$
Expand and Simplify: When we expand the product on the right, the '1' cancels out, and we are left with: $1_{U} = i \sum 1_{A_{i}} - i < j \sum 1_{A_{i}} 1_{A_{j}} + \dots = i \sum 1_{A_{i}} - i < j \sum 1_{A_{i} \cap A_{j}} + \dots$
Sum Over All Elements: Summing this identity over all $s \in S$ gives us the PIE formula: $∣ U ∣ = i \sum ∣ A_{i} ∣ - i < j \sum ∣ A_{i} \cap A_{j} ∣ + \dots$

This proof is exceptionally clean and shows the deep connection between logic, set theory, and algebra.

Conclusion

In this lesson, we have formally introduced the Principle of Inclusion-Exclusion, one of the most versatile tools in enumerative combinatorics.

Key Takeaways:

PIE provides a general formula to count the elements in a union of overlapping sets.
The core idea is to systematically correct for overcounting and undercounting by creating an alternating sum of intersection sizes.
The general formula for the union of $n$ sets is: $∣ ⋃_{i = 1}^{n} A_{i} ∣ = \sum_{\emptyset \neq = I \subseteq {1, \dots, n}} (- 1)^{∣ I ∣ - 1} ⋂_{i \in I} A_{i}$ .
We proved this formula using two different methods: a combinatorial argument that tracks how individual elements are counted, and an algebraic proof using characteristic functions. Both are essential perspectives for deep mastery.

You have now formally derived and proven PIE. In the upcoming lessons, we will put this powerful tool to work. Our next topic will be applying PIE to solve complex distribution problems, such as using the stars and bars method with upper-bound constraints, a common scenario in Olympiad problems.

Recommended resources