Venn diagrams, derangements, and Euler's totient function
Adding the sizes of overlapping sets counts some elements twice. Inclusion-exclusion fixes that with alternating signs.
Switch between two and three sets and slide the set and overlap sizes. Watch the formula add singles, subtract pairs, and add the triple.
Inclusion-Exclusion: |A∪B| = |A| + |B| - |A∩B|. Each region shows its exclusive count.
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|.
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.
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.
Watch the bar chart grow and shrink as each inclusion-exclusion correction is applied, homing in on the derangement count.
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.
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.
Key insight: At step k, we correct for overcounting by including or excluding permutations that fix at least the k specified positions. There are C(n, k) ways to choose the k positions, each contributing (n-k)! permutations.
Pick n and step through its prime factors, crossing out multiples of each one. What survives are the numbers coprime to n.
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.
φ(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.
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.
Spot a mistake or have an idea?