Inclusion-Exclusion & Pigeonhole

Counting Unions and Avoiding Overlaps

Inclusion-Exclusion Principle

When events overlap, naive addition double-counts intersections. The inclusion-exclusion principle corrects this:

$|A \cup B| = |A| + |B| - |A \cap B|$

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Derangements

A derangement is a permutation with no fixed points (no element stays in its original position). The count $D(n)$ satisfies: $D(n) = (n-1)(D(n-1) + D(n-2)), \quad D(0)=1,\ D(1)=0$

This follows from inclusion-exclusion applied to the $n!$ permutations.

Pigeonhole Principle

If $n+1$ objects are placed in $n$ bins, at least one bin contains 2 or more objects.

Generalized: If $kn + 1$ objects go into $n$ bins, some bin has at least $k+1$ objects.

def derangements(n):
    if n == 0: return 1
    if n == 1: return 0
    d = [0] * (n + 1)
    d[0], d[1] = 1, 0
    for i in range(2, n + 1):
        d[i] = (i - 1) * (d[i-1] + d[i-2])
    return d[n]

print(derangements(4))  # 9

Your Task

Implement inclusion_exclusion_3, derangements, and min_pigeons_for_guarantee.