Pattern Guide
Inclusion-Exclusion Principle
"|A∪B| = |A| + |B| - |A∩B|. Generalize to n sets. Count with constraints."
Inclusion-exclusion (PIE) counts elements in the union of overlapping sets: |A₁∪...∪Aₙ| = Σ|Aᵢ| - Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| - ... Crucial for counting with "at least one" constraints (complement counting), derangements, Euler's totient function, and bitmask DP on subsets. The alternating sign pattern comes from the binomial theorem.
Problems you can solve with this pattern
4 problems · click any to start solving
// Count integers in [1..n] divisible by at least one of primes[]
// PIE over all subsets of primes
function countDivisible(n, primes) {
const k = primes.length;
let count = 0;
for (let mask = 1; mask < (1 << k); mask++) {
let lcm = 1, bits = 0;
for (let i = 0; i < k; i++) {
if (!((mask >> i) & 1)) continue;
lcm = lcm / gcd(lcm, primes[i]) * primes[i];
bits++;
}
count += (bits % 2 === 1 ? 1 : -1) * Math.floor(n / lcm);
}
return count;
}
// Derangements: permutations with no fixed points
// D(n) = n! * Σ_{k=0}^{n} (-1)^k / k!
// Or recursively: D(n) = (n-1)(D(n-1) + D(n-2))
function derangements(n) {
if (n <= 1) return 1 - n;
let [a, b] = [1, 0]; // D(0)=1, D(1)=0
for (let i = 2; i <= n; i++) [a, b] = [b, (i - 1) * (a + b)];
return b;
}
// Euler's totient: count integers 1..n coprime to n
// φ(n) = n * Π_{p|n} (1 - 1/p) = PIE over prime factors
function eulerTotient(n) {
let phi = n;
for (let p = 2; p * p <= n; p++) {
if (n % p === 0) {
while (n % p === 0) n /= p;
phi -= phi / p;
}
}
if (n > 1) phi -= phi / n;
return phi;
}Inclusion-exclusion works on "bad" properties: let Aᵢ = set of items with property i (a "bad" property). |complement of A₁∪...| = total - |A₁∪...| = total - (Σ|Aᵢ| - Σ|Aᵢ∩Aⱼ| + ...). Often the intersections have closed-form size (e.g., |Aᵢ∩Aⱼ| = items divisible by both i and j = items divisible by lcm(i,j)). Bitmask over all n "bad" properties, enumerate all 2ⁿ subsets.
// Count integers in [1..n] divisible by at least one of primes[]
// PIE over all subsets of primes
function countDivisible(n, primes) {
const k = primes.length;
let count = 0;
for (let mask = 1; mask < (1 << k); mask++) {
let lcm = 1, bits = 0;
for (let i = 0; i < k; i++) {
if (!((mask >> i) & 1)) continue;
lcm = lcm / gcd(lcm, primes[i]) * primes[i];
bits++;
}
count += (bits % 2 === 1 ? 1 : -1) * Math.floor(n / lcm);
}
return count;
}
// Derangements: permutations with no fixed points
// D(n) = n! * Σ_{k=0}^{n} (-1)^k / k!
// Or recursively: D(n) = (n-1)(D(n-1) + D(n-2))
function derangements(n) {
if (n <= 1) return 1 - n;
let [a, b] = [1, 0]; // D(0)=1, D(1)=0
for (let i = 2; i <= n; i++) [a, b] = [b, (i - 1) * (a + b)];
return b;
}
// Euler's totient: count integers 1..n coprime to n
// φ(n) = n * Π_{p|n} (1 - 1/p) = PIE over prime factors
function eulerTotient(n) {
let phi = n;
for (let p = 2; p * p <= n; p++) {
if (n % p === 0) {
while (n % p === 0) n /= p;
phi -= phi / p;
}
}
if (n > 1) phi -= phi / n;
return phi;
}|A₁∪A₂∪...∪Aₙ| = Σ|Aᵢ| - Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| - ...
Bitmask PIE: For n "bad" properties, enumerate all 2ⁿ subsets. Odd-size subsets add, even-size subtract.
Common applications:
- Count integers with at least one bad divisor: PIE over prime factors
- Derangements: D(n) = Σ (-1)^k × C(n,k) × (n-k)! = (n-1)(D(n-1)+D(n-2))
- Surjections: |surjections from n to k| = Σ (-1)^i × C(k,i) × (k-i)^n
- At-least-one constraint: complement = none, PIE gives exactly-one