Venn diagrams, derangements, and Euler's totient function
When counting elements in a union of overlapping sets, simply adding the set sizes overcounts elements that belong to multiple sets. The inclusion-exclusion principle corrects this by alternately adding and subtracting intersection sizes: |A ∪ B| = |A| + |B| - |A ∩ B|.
In this lesson, you will manipulate Venn diagrams to see inclusion-exclusion in action, derive the derangement formula step by step, and use sieving to compute Euler's totient function.
Adjust set sizes and intersection sizes to see how inclusion-exclusion computes the union. With two sets, there is one correction term. With three sets, there are four correction terms -- and the formula alternates signs: add singles, subtract pairs, add the triple.
Inclusion-Exclusion: |A∪B| = |A| + |B| - |A∩B|. Each region shows its exclusive count.
Key insight: The alternating signs ensure each element is counted exactly once. An element in all three sets gets added 3 times, subtracted 3 times, then added 1 time = 1 net count.
Let Aᵢ be the set of permutations fixing element i. The derangement count is n! minus the size of A₁ ∪ A₂ ∪ ... ∪ Aₙ. Applying inclusion-exclusion produces the alternating sum formula for !n. Watch the bar chart grow and shrink as each correction is applied.
A derangement is a permutation with no fixed points. Start with 4!, subtract perms fixing 1 position, add back those fixing 2, and so on. The alternating sum gives !4 = 9.
Key insight: At step k, we correct for overcounting by including or excluding permutations that fix exactly k specified positions. There are C(n, k) ways to choose the k positions, each contributing (n-k)! permutations.
φ(n) counts the integers from 1 to n that are coprime to n. To compute it, we sieve out multiples of each prime factor of n using inclusion-exclusion: φ(n) = n × Π(1 - 1/p). This elegant product formula emerges directly from the sieving process.
phi(12) = 12 × (1 - 1/2) × (1 - 1/3) = 12 × 1/2 × 2/3 = 4
Prime factors of 12: 2, 3
Euler's totient phi(12) counts integers from 1 to 12 coprime to 12. Using inclusion-exclusion on prime factor multiples: phi(12) = 12 × (1 - 1/2) × (1 - 1/3) = 4. Orange cells are coprime to 12; red cells are being sieved in the current step.
Key insight: Euler's totient connects number theory to combinatorics through inclusion-exclusion. The formula φ(n) = n × Π(1 - 1/p) is multiplicative: φ(ab) = φ(a)φ(b) when gcd(a,b) = 1.