Inclusion–Exclusion & the Binomial Theorem

#Inclusion–exclusion

When sets overlap, adding their sizes counts the overlaps more than once. Correct for it:

|A ∪ B| = |A| + |B| − |A ∩ B|

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

In general: add the single sets, subtract all pairwise intersections, add all triple intersections, and so on with alternating signs.

#Example: divisibility

How many integers from 1 to 1000 are divisible by 2, 3 or 5?

N = 1000
direct = sum(1 for n in range(1, N + 1) if n % 2 == 0 or n % 3 == 0 or n % 5 == 0)
formula = (N//2 + N//3 + N//5) - (N//6 + N//10 + N//15) + N//30
print("count directly:", direct, " inclusion-exclusion:", formula)
print("not divisible by 2, 3 or 5:", N - formula)

count directly: 734  inclusion-exclusion: 734
not divisible by 2, 3 or 5: 266

#Derangements

A derangement is a permutation where no element stays in its original position — n letters put into n envelopes so that every letter is in the wrong one. By inclusion–exclusion:

Dₙ = n! (1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!)

from math import factorial
from itertools import permutations

def derangements(n):
    return round(factorial(n) * sum((-1) ** k / factorial(k) for k in range(n + 1)))

for n in range(1, 8):
    brute = sum(1 for p in permutations(range(n)) if all(p[i] != i for i in range(n)))
    print(f"D{n} = {derangements(n)} (brute force {brute}), fraction {derangements(n) / factorial(n):.4f}")

D1 = 0 (brute force 0), fraction 0.0000
D2 = 1 (brute force 1), fraction 0.5000
D3 = 2 (brute force 2), fraction 0.3333
D4 = 9 (brute force 9), fraction 0.3750
D5 = 44 (brute force 44), fraction 0.3667
D6 = 265 (brute force 265), fraction 0.3681
D7 = 1854 (brute force 1854), fraction 0.3679

The fraction of permutations that are derangements approaches 1/e ≈ 0.3679.

#The binomial theorem

(x + y)ⁿ = Σₖ₌₀ⁿ C(n, k) xⁿ⁻ᵏ yᵏ

The coefficients C(n, k) are the binomial coefficients — the rows of Pascal's triangle, where each entry is the sum of the two above it.

from math import comb

for n in range(7):
    print(" " * (2 * (6 - n)) + "".join(f"{comb(n, k):4}" for k in range(n + 1)))

n = 4
terms = [f"{comb(n, k)}x^{n-k}y^{k}" for k in range(n + 1)]
print("(x + y)^4 =", " + ".join(terms))

               1
             1   1
           1   2   1
         1   3   3   1
       1   4   6   4   1
     1   5  10  10   5   1
   1   6  15  20  15   6   1
(x + y)^4 = 1x^4y^0 + 4x^3y^1 + 6x^2y^2 + 4x^1y^3 + 1x^0y^4

Consequences:

• Setting x = y = 1: Σ C(n, k) = 2ⁿ (the number of subsets).
• Setting x = 1, y = −1: Σ (−1)ᵏ C(n, k) = 0.
• The coefficient of x³y⁵ in (x + y)⁸ is C(8, 5) = 56.
• The coefficient of x⁴ in (2x − 3)⁶ is C(6, 2) · 2⁴ · (−3)² = 15 · 16 · 9 = 2160.