Kekkei - Advancing Financial Science For Everyone

Introduction

How many integers from 1 to 100 are divisible by 2 or 3? Simple counting fails because some numbers are divisible by both. The Inclusion-Exclusion Principle systematically handles overlapping sets to avoid double-counting.

Learning Objectives:

Master the Inclusion-Exclusion Principle for unions of sets
Apply it to counting problems with constraints
Calculate derangements (permutations with no fixed points)
Solve real-world problems involving overlapping conditions

The Inclusion-Exclusion Principle

For finite sets $A_1, A_2, \ldots, A_n$ :

Two sets: $|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|$

Three sets: $|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|$

General form: $\left|\bigcup_{i=1}^n A_i\right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}|A_1 \cap \cdots \cap A_n|$

Pattern: Alternate adding singletons, subtracting pairs, adding triples, etc.

Example 1: Divisibility by 2 or 3

How many integers from 1 to 100 are divisible by 2 or 3?

Solution:

Let $A$ = numbers divisible by 2 → $|A| = \lfloor 100/2 \rfloor = 50$
Let $B$ = numbers divisible by 3 → $|B| = \lfloor 100/3 \rfloor = 33$
$A \cap B$ = numbers divisible by both 2 and 3 (i.e., by 6) → $|A \cap B| = \lfloor 100/6 \rfloor = 16$

By Inclusion-Exclusion: $|A \cup B| = |A| + |B| - |A \cap B| = 50 + 33 - 16 = 67$

python

def count_divisible(n, divisors):
    """Count integers from 1 to n divisible by at least one divisor using inclusion-exclusion"""
    from itertools import combinations
    import math

    count = 0

    # Iterate over all non-empty subsets of divisors
    for r in range(1, len(divisors) + 1):
        for combo in combinations(divisors, r):
            # LCM of divisors in this combination
            lcm = combo[0]
            for d in combo[1:]:
                lcm = lcm * d // math.gcd(lcm, d)

            # Count numbers divisible by LCM
            divisible_count = n // lcm

            # Inclusion-Exclusion: alternate add/subtract
            if r % 2 == 1:
                count += divisible_count
            else:
                count -= divisible_count

    return count

# Divisible by 2 or 3
n = 100
divisors = [2, 3]

result = count_divisible(n, divisors)

print(f"Integers from 1 to {n} divisible by 2 or 3:")
print(f"\nBreakdown:")
print(f"  Divisible by 2: {n // 2}")
print(f"  Divisible by 3: {n // 3}")
print(f"  Divisible by both (6): {n // 6}")
print(f"\nInclusion-Exclusion: {n // 2} + {n // 3} - {n // 6} = {result}")

# Verify by enumeration
actual = sum(1 for i in range(1, n+1) if i % 2 == 0 or i % 3 == 0)
print(f"\nVerification by enumeration: {actual}")
print(f"Match: {result == actual}")

Key Insight: Without subtraction, we'd count numbers divisible by 6 twice (once in "divisible by 2" and once in "divisible by 3"). Inclusion-Exclusion corrects this overlap.

Three-Set Example

Example 2: Divisibility by 2, 3, or 5

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

Solution:

$|A| = \lfloor 200/2 \rfloor = 100$
$|B| = \lfloor 200/3 \rfloor = 66$
$|C| = \lfloor 200/5 \rfloor = 40$
$|A \cap B| = \lfloor 200/6 \rfloor = 33$
$|A \cap C| = \lfloor 200/10 \rfloor = 20$
$|B \cap C| = \lfloor 200/15 \rfloor = 13$
$|A \cap B \cap C| = \lfloor 200/30 \rfloor = 6$

$|A \cup B \cup C| = 100 + 66 + 40 - 33 - 20 - 13 + 6 = 146$

python

# Divisible by 2, 3, or 5
n = 200
divisors = [2, 3, 5]

result = count_divisible(n, divisors)

print(f"Integers from 1 to {n} divisible by 2, 3, or 5:")
print(f"\nSingletons (add):")
print(f"  Divisible by 2: {n // 2}")
print(f"  Divisible by 3: {n // 3}")
print(f"  Divisible by 5: {n // 5}")
print(f"  Sum: {n // 2 + n // 3 + n // 5}")

print(f"\nPairs (subtract):")
print(f"  Divisible by 6 (LCM of 2,3): {n // 6}")
print(f"  Divisible by 10 (LCM of 2,5): {n // 10}")
print(f"  Divisible by 15 (LCM of 3,5): {n // 15}")
print(f"  Sum: {n // 6 + n // 10 + n // 15}")

print(f"\nTriple (add):")
print(f"  Divisible by 30 (LCM of 2,3,5): {n // 30}")

print(f"\nInclusion-Exclusion: {n // 2} + {n // 3} + {n // 5} - {n // 6} - {n // 10} - {n // 15} + {n // 30} = {result}")

# Verify
actual = sum(1 for i in range(1, n+1) if i % 2 == 0 or i % 3 == 0 or i % 5 == 0)
print(f"\nVerification: {actual}")
print(f"Match: {result == actual}")

Derangements

A derangement is a permutation where no element appears in its original position. The number of derangements of $n$ objects is denoted $D_n$ or $!n$ .

Formula using Inclusion-Exclusion: $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$

Approximation: $D_n \approx \frac{n!}{e}$ (for large $n$ )

Interpretation: About $1/e \approx 36.8\%$ of all permutations are derangements.

Example 3: Secret Santa

5 people do Secret Santa. Each draws a name. What's the probability no one draws their own name?

Solution: We need derangements of 5 people:

$D_5 = 5! \left(\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!}\right)$

$= 120 \left(1 - 1 + 0.5 - 0.1667 + 0.0417 - 0.0083\right)$

$= 120 \times 0.3667 = 44$

Probability: $\frac{D_5}{5!} = \frac{44}{120} \approx 0.367 \approx \frac{1}{e}$

python

import math

def derangements(n):
    """Calculate number of derangements of n objects"""
    # D_n = n! * sum_{k=0}^n (-1)^k / k!
    factorial_n = math.factorial(n)
    sum_term = sum((-1)**k / math.factorial(k) for k in range(n + 1))
    return int(round(factorial_n * sum_term))

# Secret Santa with 5 people
n = 5
D_n = derangements(n)
total_perms = math.factorial(n)

print(f"Secret Santa with {n} people:")
print(f"\nTotal permutations: {n}! = {total_perms}")
print(f"Derangements: D_{n} = {D_n}")
print(f"Probability no one gets their own name: {D_n}/{total_perms} = {D_n/total_perms:.4f}")
print(f"Approximation 1/e = {1/math.e:.4f}")

# Show derangements for n = 1 to 10
print(f"\nDerangements table:")
print(f"{'n':>3} {'n!':>10} {'D_n':>10} {'D_n/n!':>10}")
print("-" * 38)
for k in range(1, 11):
    D_k = derangements(k)
    fact_k = math.factorial(k)
    ratio = D_k / fact_k
    print(f"{k:>3} {fact_k:>10,} {D_k:>10,} {ratio:>10.4f}")

Counterintuitive Result: The probability of a derangement converges to $1/e \approx 36.8\%$ regardless of $n$ ! Whether you have 5 people or 1000, about 37% of random permutations have no fixed points.

Complementary Counting

Sometimes it's easier to count what you don't want and subtract.

Example 4: At Least One Condition

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

Solution: Use complement: $\text{Not divisible} = \text{Total} - \text{Divisible by at least one}$

From Example 2 logic (scaled to 100):

Divisible by 2, 3, or 5: Use Inclusion-Exclusion

$100 - (50 + 33 + 20 - 16 - 10 - 6 + 3) = 100 - 74 = 26$

python

# Not divisible by 2, 3, or 5
n = 100
divisors = [2, 3, 5]

divisible = count_divisible(n, divisors)
not_divisible = n - divisible

print(f"Integers from 1 to {n}:")
print(f"  Divisible by 2, 3, or 5: {divisible}")
print(f"  NOT divisible by 2, 3, or 5: {not_divisible}")

# Verify
actual_not = sum(1 for i in range(1, n+1) if i % 2 != 0 and i % 3 != 0 and i % 5 != 0)
print(f"\nVerification: {actual_not}")

# Show first few
examples = [i for i in range(1, n+1) if i % 2 != 0 and i % 3 != 0 and i % 5 != 0][:10]
print(f"\nFirst 10 such numbers: {examples}")

Key Takeaways

Inclusion-Exclusion: $|A \cup B| = |A| + |B| - |A \cap B|$ (extend for $n$ sets)
Pattern: Alternate adding/subtracting intersections of increasing size
Derangements: $D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$ , approaches $\frac{n!}{e}$
Complementary counting: Sometimes easier to count what you don't want
Overlap correction: Always account for elements counted multiple times

Next Lesson: The Pigeonhole Principle for existence proofs and surprising results!

Formula	Description	Example
$	A \cup B	=	A	+	B	-	A \cap B	$	Two sets	Divisible by 2 or 3
$	A \cup B \cup C	= \sum	A_i	- \sum	A_i \cap A_j	+	A \cap B \cap C	$	Three sets	Divisible by 2, 3, or 5
$D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$	Derangements	Secret Santa
$D_n / n! \approx 1/e$	Derangement probability	$\approx 0.368$ for any $n$

IntroductionFocusStart Focus Mode

The Inclusion-Exclusion PrincipleFocusStart Focus Mode

Example 1: Divisibility by 2 or 3

Three-Set ExampleFocusStart Focus Mode

Example 2: Divisibility by 2, 3, or 5

DerangementsFocusStart Focus Mode

Example 3: Secret Santa

Complementary CountingFocusStart Focus Mode

Example 4: At Least One Condition

Key TakeawaysFocusStart Focus Mode

Introduction

The Inclusion-Exclusion Principle

Three-Set Example

Derangements

Complementary Counting

Key Takeaways