Day 52 — Inclusion-exclusion

Updated

July 30, 2026

Day 52 — Inclusion–exclusion

Stage V · concept day
Goal: Apply inclusion–exclusion for 2–3 sets and the general pattern; count surjections and derangements; enforce upper bounds in stars-and-bars; connect to Stirling numbers of the second kind awareness.

Why this matters

Naive sum overcounts unions. Security policies (“violates rule A or B”), covering residual cases, surjective assignments, and “nobody gets their own hat” need inclusion–exclusion (IE). It is the systematic correction to the sum rule when classes overlap. Master the pattern once; re-specialize forever.

Theory

Two sets

\[ |A\cup B| = |A| + |B| - |A\cap B|. \]

Why: \(|A|+|B|\) counts \(A\cap B\) twice; subtract once so it is counted once.

Complement form: \(|U\setminus(A\cup B)|=|U|-|A|-|B|+|A\cap B|\) (neither property).

Three sets

\[ |A\cup B\cup C| = |A|+|B|+|C| - |A\cap B|-|A\cap C|-|B\cap C| + |A\cap B\cap C|. \]

Venn region check: elements only in \(A\cap B\cap C\) are counted \(3-3+1=1\) time; elements in exactly two sets: \(2-1=1\); elements in exactly one: \(1\).

General formula

For sets \(A_1,\ldots,A_m\subseteq U\),

\[ \Bigl|\bigcup_{i=1}^{m} A_i\Bigr| = \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)^{m+1}|A_1\cap\cdots\cap A_m|. \]

Sign pattern: intersections of \(r\) sets get sign \((-1)^{r+1}\).

Property form (often best for counting)

Let \(U\) be a universe. Property \(P_i\): element has feature \(i\). Let \(A_i=\{x\in U:x\text{ has }P_i\}\). Number of elements with none of the properties:

\[ N_{\text{none}} = |U| - \sum|A_i| + \sum|A_i\cap A_j| - \sum|A_i\cap A_j\cap A_k| + \cdots + (-1)^m |A_1\cap\cdots\cap A_m|. \]

Number with at least one property: \(|U|-N_{\text{none}}\).

Counting surjections (onto functions)

Number of surjective functions \(f:N\to K\) with \(|N|=n\), \(|K|=k\):

Let \(U=\) all functions: \(|U|=k^n\).
Let \(A_i=\) functions that miss element \(i\) in the codomain (\(|A_i|=(k-1)^n\)).
Then \(A_{i_1}\cap\cdots\cap A_{i_r}\) = functions missing \(r\) particular codomain points: \((k-r)^n\).
Number missing none (i.e. surjections):

\[ \sum_{i=0}^{k}(-1)^i\binom{k}{i}(k-i)^n. \]

Stirling numbers of the second kind (awareness)

\(S(n,k)\) = number of ways to partition \(n\) distinct objects into \(k\) nonempty unlabeled subsets. Then

\[ \text{surjections } = k!\, S(n,k), \]

because label the \(k\) blocks by codomain elements. So

\[ S(n,k) = \frac{1}{k!}\sum_{i=0}^{k}(-1)^i\binom{k}{i}(k-i)^n. \]

Derangements as IE special case

Permutations of \([n]\) with no fixed points: \(U=n!\) permutations; \(A_i=\) permutations fixing \(i\); \(|A_{i_1}\cap\cdots\cap A_{i_r}|=(n-r)!\). Thus

\[ !n = \sum_{i=0}^{n}(-1)^i\binom{n}{i}(n-i)! = n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}. \]

(Recover Day 48 formula.)

IE + stars and bars (upper bounds)

Nonnegative solutions to \(x_1+\cdots+x_k=n\) with each \(x_j\le M\):
\(U\) = all nonnegative solutions, \(|U|=\binom{n+k-1}{k-1}\);
\(A_j\): \(x_j\ge M+1\); substitute and apply general IE (Day 51 examples).

Divisibility counting

How many integers in \(\{1,\ldots,N\}\) are divisible by \(a\) or \(b\)?
\(|A\cup B|=\lfloor N/a\rfloor+\lfloor N/b\rfloor-\lfloor N/\mathrm{lcm}(a,b)\rfloor\).

Worked examples

Example 1 — Two sets

In a class of 40: 25 take math, 20 take CS, 10 both. Math or CS: \(25+20-10=35\). Neither: \(40-35=5\).

Example 2 — Three sets

\(|A|=20,|B|=15,|C|=10\), \(|A\cap B|=8\), \(|A\cap C|=6\), \(|B\cap C|=5\), \(|A\cap B\cap C|=3\), \(|U|=50\).
Union: \(20+15+10-8-6-5+3=29\). None: \(50-29=21\).

Example 3 — Bit-strings OR

Length-4 bit-strings starting with 1 or ending with 1:
\(|A|=8\), \(|B|=8\), \(|A\cap B|=4\) → \(8+8-4=12\).
Complement: neither = start 0 and end 0: \(2^2=4\); total \(16-4=12\).

Example 4 — Divisibility

\(\{1,\ldots,100\}\) divisible by 2 or 5: \(\lfloor 100/2\rfloor+\lfloor 100/5\rfloor-\lfloor 100/10\rfloor=50+20-10=60\).

Example 5 — Three primes

\(\{1,\ldots,210\}\) divisible by 2, 3, or 5:
\(\lfloor 210/2\rfloor+\lfloor 210/3\rfloor+\lfloor 210/5\rfloor -\lfloor 210/6\rfloor-\lfloor 210/10\rfloor-\lfloor 210/15\rfloor +\lfloor 210/30\rfloor\)
\(=105+70+42-35-21-14+7=154\).

Example 6 — Surjections \([4]\to[2]\)

\(\sum_{i=0}^{2}(-1)^i\binom{2}{i}(2-i)^4 = \binom{2}{0}2^4-\binom{2}{1}1^4+\binom{2}{2}0^4=16-2+0=14\).
Check: \(2^4-2=14\) (exclude 2 constants). \(S(4,2)=7\), and \(2!\cdot 7=14\).

Example 7 — Surjections \([5]\to[3]\)

\(\binom{3}{0}3^5-\binom{3}{1}2^5+\binom{3}{2}1^5-\binom{3}{3}0^5=243-3\cdot 32+3\cdot 1-0=243-96+3=150\).
\(S(5,3)=25\), \(3!\cdot 25=150\).

Example 8 — Derangement \(!4\)

\(4!(1-1+1/2-1/6+1/24)=24\cdot\frac{9}{24}=9\).
Or: \(24-\binom{4}{1}6+\binom{4}{2}2-\binom{4}{3}1+\binom{4}{4}0=24-24+12-4+1=9\).

Example 9 — Derangement \(!5\)

\(120(1-1+1/2-1/6+1/24-1/120)=120\cdot\frac{44}{120}=44\).

Example 10 — Stars-bars + IE

\(x+y+z=7\), \(0\le x,y,z\le 4\):
Total \(\binom{9}{2}=36\); one variable \(\ge 5\): \(\binom{3+2}{2}=\binom{5}{2}=10\)? Wait \(n'=7-5=2\): \(\binom{2+2}{2}=\binom{4}{2}=6\); \(\times 3=18\); pairwise \(\ge 5\) each: \(7-10<0\): 0. Answer \(36-18=18\).

Example 11 — Passwords at least one digit

Length 4 over 26 letters + 10 digits: \(36^4-26^4\) (complement = no digit). Same as IE with one property “is letter-only” actually pure complement.

Example 12 — Onto maps as assignments

Assign 6 distinct jobs to 3 distinct workers so each worker gets at least one: surjections \(3!\,S(6,3)\).
\(S(6,3)=90\), answer \(6\cdot 90=540\).
IE: \(\binom{3}{0}3^6-\binom{3}{1}2^6+\binom{3}{2}1^6=729-3\cdot 64+3=729-192+3=540\).

Example 13 — Exactly one property

Sometimes you want exactly one of \(A,B\): \(|A|+|B|-2|A\cap B|\).
(Exactly the symmetric difference size.)

Example 14 — Missed intersections

If you compute \(|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|\) and forget \(+|A\cap B\cap C|\), triple-overlap elements are undercounted (0 times instead of 1).

Example 15 — Probability of derangement

\(P(\text{random perm is derangement})\to 1/e\). For \(n=5\): \(44/120\approx 0.3667\).

Exercises

  1. Two-set IE formula; three-set formula—write from memory.
  2. Class: 30 French, 25 German, 10 both, 50 total. Neither language?
  3. Length-5 bit-strings with first bit 1 or last bit 0—compute via IE.
  4. \(\{1,\ldots,120\}\) divisible by 3 or 4.
  5. \(\{1,\ldots,120\}\) divisible by 2, 3, or 5.
  6. Surjections \([3]\to[3]\); \([4]\to[3]\); \([6]\to[4]\).
  7. Compute \(S(4,2)\) and \(S(5,2)\) from the formula.
  8. \(!6\) by formula; compare to \(\mathrm{round}(720/e)\).
  9. Number of permutations of \([7]\) with no fixed points.
  10. \(x+y+z+w=12\), each \(x_i\le 5\)—set up full IE (compute).
  11. Functions \([5]\to[5]\) that are not surjective (use total − surjections).
  12. Exactly 2 of 3 properties: optional formula awareness.
  13. Prove two-set IE from indicator functions: \(1_{A\cup B}=1_A+1_B-1_{A\cap B}\).
  14. Integers \(1..1000\) not divisible by 2, 3, or 5.
  15. Secret Santa: 8 people, no one draws self—count.
  16. Assign 5 distinct TAs to 3 sections, each section ≥1 TA.
  17. Prove \(!n=n\cdot!(n-1)+(-1)^n\) for \(n\ge 1\) (optional induction).
  18. Passwords length 5 from {A..Z,0..9} with at least one letter and at least one digit.
  19. Why \(0^n\) appears in surjection formula for \(i=k\) when \(n>0\)?
  20. CS: hash \(n\) distinct keys into \(k\) buckets, every bucket nonempty—count.
  21. List all derangements of \(\{1,2,3,4\}\) (9 of them)—structure.
  22. Venn: given all region sizes, recover \(|A\cup B\cup C|\).
  23. Challenge: number of integers ≤ 1000 divisible by at least one of 6,10,15.
  24. Multisets vs IE: when do you need both?
  25. Write general IE for \(m=4\) explicitly (all 15 terms grouped).

CS connection

  • Constraint violation counts: logs matching any of several error codes.
  • Coverage: test cases hitting at least one of critical paths.
  • Surjective allocations: every shard/replica gets ≥1 item.
  • Derangements: secure shuffles, mixing networks, hat-check problems.
  • Bloom filters / set sketches culture: IE appears in pure set-size estimation theory.

Common pitfalls

Pitfall What to do instead
Stopping after pairwise subtract for 3 sets Add triple back
Wrong sign pattern \((-1)^{r+1}\) for union form
Surjection: forgetting \(\binom{k}{i}\) Choose which \(i\) points are missed
\(S(n,k)\) vs \(k!S(n,k)\) Unlabeled partitions vs labeled surjections
Applying IE when sets already disjoint Just sum
Floor functions forgotten in divisibility Use \(\lfloor N/a\rfloor\)

Checkpoint

  • 2-set and 3-set formulas cold
  • General sign pattern
  • Surjection formula and one numerical check
  • Derangement as IE; \(!n\approx n!/e\)
  • One stars-bars upper bound via IE
  • Exercises 1–15
  • \(S(n,k)\) relation to surjections in one line

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. Union \(30+25-10=45\) impossible if total 50—wait 45 in language; neither \(5\).
  2. \(|A|=2^4=16\), \(|B|=16\), \(|A\cap B|=2^3=8\) → \(24\); total \(32\), etc.
  3. \(\lfloor 120/3\rfloor+\lfloor 120/4\rfloor-\lfloor 120/12\rfloor=40+30-10=60\).
  4. \(3!=6\); \(\sum(-1)^i\binom{3}{i}(3-i)^4=81-3\cdot 16+3\cdot 1=36\); \([6]\to[4]\) compute similarly.
  5. \(!6=265\); \(720/e\approx 264.87\).
  6. \(5^5-5!S(5,5)=3125-120=3005\) not surj; surjections onto \([5]\) are \(5!=120\).
  7. \(!8=14833\).

Deepening notes

Indicator proof of 2-set IE

For each \(x\), \(1_{A\cup B}(x)=1_A(x)+1_B(x)-1_{A\cap B}(x)\). Sum over \(x\in U\).

General term intuition

An element in exactly \(t\) of the sets \(A_i\) is counted \(\sum_{r=1}^{t}(-1)^{r+1}\binom{t}{r}=1\) times in the union formula (binomial expansion of \((1-1)^t=0\) for \(t>0\) rearranged).

Surjection–Stirling dictionary

Object Symbol / formula
Partitions of \(n\) into \(k\) nonempty unlabeled \(S(n,k)\)
Surjections \([n]\to[k]\) \(k!S(n,k)=\sum_i(-1)^i\binom{k}{i}(k-i)^n\)
All functions \(k^n\)
Injections \(P(k,n)\) if \(n\le k\)

Derangement numerical table

\(n\) \(!n\) \(n!/e\) rounded
0 1 —
1 0 0
2 1 1
3 2 2
4 9 9
5 44 44
6 265 265

Extra drills

D1. Three-set Venn with given region sizes → union.
D2. \(\{1..200\}\) div by 6 or 10 or 15.
D3. Surjections \([6]\to[3]\).
D4. \(S(5,3)\) from formula.
D5. \(!7\).
D6. \(x+y+z=9\), each ≤4 via IE.
D7. Passwords length 5 from 36 with ≥1 digit.
D8. Probability random perm of 8 is derangement (approx).

Flash

\(|A\cup B|=|A|+|B|-|A\cap B|\); surj \(=\sum(-1)^i\binom{k}{i}(k-i)^n\); \(!n=n!\sum(-1)^k/k!\).

Exam drill block

E1. Three-set IE: \(|A|=20,|B|=25,|C|=18,|A\cap B|=8,|A\cap C|=6,|B\cap C|=7,|A\cap B\cap C|=3\); find \(|A\cup B\cup C|\).
E2. How many integers in \(\{1,\ldots,100\}\) divisible by 2, 3, or 5?
E3. Surjections \([5]\to[3]\); compare to \(3^5\).
E4. \(S(5,2)\) via \(2!S(5,2)=\) surjections onto 2 labels.
E5. Compute \(!5\) and \(!6\) from the series formula.
E6. Passwords length 4 from \(\{A..Z,0..9\}\) with at least one digit—complement.
E7. \(x+y+z=8\), each \(\le 4\), via IE.
E8. Probability a random perm of \(n=7\) is a derangement \(\approx 1/e\).
E9. True/false: (i) IE requires properties be independent (ii) surjections \(=k!S(n,k)\) (iii) \(!n=\lfloor n!/e+1/2\rfloor\) often.
E10. CS: hash \(n\) keys into \(k\) buckets, none empty—name the count.

Mini solutions

E1. \(20+25+18-8-6-7+3=45\).
E2. \(\lfloor100/2\rfloor+\lfloor100/3\rfloor+\lfloor100/5\rfloor-\lfloor100/6\rfloor-\lfloor100/10\rfloor-\lfloor100/15\rfloor+\lfloor100/30\rfloor=50+33+20-16-10-6+3=74\).
E3. \(\sum(-1)^i\binom{3}{i}(3-i)^5=243-3\cdot 32+3\cdot 1=150\); \(3^5=243\).
E5. \(44\); \(265\).
E7. Unrestricted \(\binom{10}{2}=45\); one ≥5: \(\binom{5}{2}=10\) ×3=30; two ≥5: sum −2 impossible → \(15\).
E9. F; T; T (for \(n\neq 0\) standard rounding).
E10. Surjections \([n]\to[k]\).

Synthesis

Inclusion–exclusion subtracts overcounts systematically: union of properties, surjections (no empty codomain labels), derangements (no fixed points), and bounded stars-bars. The general pattern is \(\sum (-1)^r\) times intersections of \(r\) properties. Always define the universe \(U\) and the bad properties \(A_i\) first.

S1. Full IE writeup for \(\{1..210\}\) divisible by 2, 3, or 7.
S2. Derive \(!n\) from IE with \(A_i=\) “\(i\) fixed.”
S3. Cold: surjections \([6]\to[4]\); \(!4\).

Tomorrow

Day 53 — Counting in CS: passwords, states, hashes, execution trees, bit constraints, protocol spaces, \(\log_2\) size.