Exercises — Inclusion-exclusion principle

WHAT tool: two-set inclusion–exclusion, because we are asked for a union and we were handed the overlap. WHY subtract: the $5$ both-owners are inside the $18$ and inside the $12$, so simple addition counts them twice. $|D\cup C|=|D|+|C|-|D\cap C|=18+12-5=25.$ Answer: $25$.

$|A\cap C\cap D|$ is an intersection of $k=3$ sets. The sign is $(-1{)}^{k+1}=(-1{)}^4=+$. WHY: three is odd, and odd-size intersections are added. Answer: $+$ (positive).

Let $A$ = multiples of $4$, $B$ = multiples of $6$.

• $|A|=\lfloor 100/4\rfloor =25.$
• $|B|=\lfloor 100/6\rfloor =16.$
• $|A\cap B|$ = multiples of $\mathrm{lcm}(4,6)=12$: $\lfloor 100/12\rfloor =8.$ WHY lcm not $4\cdot 6$: a number divisible by both $4$ and $6$ must be divisible by their least common multiple, $12$ — not the product $24$ (else you'd miss $12,36,60,\dots$). $|A\cup B|=25+16-8=33.$ Answer: $33$.

$55+50+40-20-15-12+8.$ Step by step: singles $=145$; subtract pairs $145-47=98$; add the triple $98+8=106$. WHY $+8$: the $8$ all-three students were added $3$ times (once per single) and subtracted $3$ times (once per pair), netting $0$ — so they must be restored once. Answer: $106$.

WHAT tool: count "at least one" by inclusion–exclusion, then subtract from the total — it is far easier than counting "none" directly. See the shaded region below.

Let $A,B,C$ be multiples of $2,3,5$.

• Singles: $\lfloor 1000/2\rfloor =500,\lfloor 1000/3\rfloor =333,\lfloor 1000/5\rfloor =200.$
• Pairs (use lcm): $\lfloor 1000/6\rfloor =166,\lfloor 1000/10\rfloor =100,\lfloor 1000/15\rfloor =66.$
• Triple: $\lfloor 1000/30\rfloor =33.$ $|A\cup B\cup C|=500+333+200-166-100-66+33=734.$ Divisible by none: $1000-734=266.$ WHY the complement: "divisible by none" is the outside of the union; total minus union gives it in one line. Answer: $266$.

WHY a new formula: the union counts "one or more," but we want strictly one. An element in exactly one set should count once; in exactly two, zero times; in exactly three, zero times. The count of "exactly one" is $\sum |A_i|-2{\sum }_{i<j}|A_i\cap A_j|+3|A\cap B\cap C|.$ WHY the coefficients $-2,+3$: an element in exactly two sets appears in $\left(\genfrac{}{}{0ex}{}{2}{1}\right)=2$ singles and $\left(\genfrac{}{}{0ex}{}{2}{2}\right)=1$ pair, so $2-2(1)=0$. An element in all three appears in $3$ singles, $3$ pairs, $1$ triple: $3-2(3)+3(1)=0$. Only "in exactly one" survives with coefficient $1$. $=145-2(47)+3(8)=145-94+24=75.$ Answer: $75$.

WHAT tool: count the "bad" functions that miss at least one box by inclusion–exclusion, then subtract from all $3^5$ functions. Let $A_i$ = functions that avoid box $b_i$.

• Total functions: $3^5=243.$
• $|A_i|$ = functions into the other $2$ boxes $=2^5=32$; there are $\left(\genfrac{}{}{0ex}{}{3}{1}\right)=3$ of them.
• $|A_i\cap A_j|$ = functions into the remaining $1$ box $=1^5=1$; there are $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$.
• $|A_1\cap A_2\cap A_3|$ = functions into $0$ boxes $=0$; $\left(\genfrac{}{}{0ex}{}{3}{3}\right)=1$. Functions missing at least one box: $3(32)-3(1)+0=96-3=93.$ Surjections $=243-93=150.$ WHY this matches the formula: surjections $={\sum }_{k=0}^3(-1{)}^k(\genfrac{}{}{0ex}{}{3}{k})(3-k{)}^5=243-96+3-0=150.$ Answer: $150$.

WHAT tool: derangements $D_n$, an inclusion–exclusion payoff (see parent example 3). Let $A_i$ = arrangements where letter $i$ is in its correct envelope, so $|A_i|=(n-1)!$, and a $k$-fold intersection fixes $k$ letters: $(n-k)!$ with $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ choices. $D_5=5!{\sum }_{k=0}^5\frac{(-1{)}^k}{k!}=120\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120}\right).$ Compute the bracket: $0+0.5-0.1\overline{6}+0.041\overline{6}-0.008\overline{3}=0.36\overline{6}$, and $120\times \frac{44}{120}=44.$ Answer: $D_5=44$.

WHAT tool: Bonferroni Inequalities — truncating inclusion–exclusion after an odd number of terms over-estimates (upper bound); after an even number under-estimates (lower bound).

• After $1$ term (odd → upper): $P(\cup )\le \sum P(A_i)=3(0.4)=\mathrm{1.2.}$ (Trivially capped at $1$.)
• After $2$ terms (even → lower): $P(\cup )\ge \sum P(A_i)-{\sum }_{i<j}P(A_i\cap A_j)=1.2-3(0.1)=\mathrm{0.9.}$ So $0.9\le P(A\cup B\cup C)\le 1.$ WHEN exact $=$ lower bound $0.9$: equality holds precisely when the triple intersection is empty, $P(A\cap B\cap C)=0$, since the full formula adds $+P(A\cap B\cap C)$ to the lower bound. Answer: bounds $[0.9,1]$; exact $=0.9$ iff $P(A\cap B\cap C)=0$.

Strategy: fix one element $x$ that lies in exactly $r$ of the sets, and show it contributes $1$ to $E_m$ when $r=m$ and $0$ otherwise. Summing over all $x$ then gives the count.

Its contribution to $S_k$. $x$ appears in a $k$-fold intersection exactly when all $k$ chosen sets are among the $r$ containing it, so it contributes $\left(\genfrac{}{}{0ex}{}{r}{k}\right)$ to $S_k$ (and $0$ if $k>r$).

Its contribution to $E_m$. Substitute: ${\sum }_{k=m}^n(-1{)}^{k-m}(\genfrac{}{}{0ex}{}{k}{m}\left)\right(\genfrac{}{}{0ex}{}{r}{k}).$ Use the subset-of-a-subset identity $\left(\genfrac{}{}{0ex}{}{k}{m}\right)\left(\genfrac{}{}{0ex}{}{r}{k}\right)=\left(\genfrac{}{}{0ex}{}{r}{m}\right)\left(\genfrac{}{}{0ex}{}{r-m}{k-m}\right)$ (WHY: choosing $k$ from $r$ then $m$ from those $k$ equals choosing the final $m$ from $r$ then the remaining $k-m$ from the leftover $r-m$). Factor out $\left(\genfrac{}{}{0ex}{}{r}{m}\right)$: $\left(\genfrac{}{}{0ex}{}{r}{m}\right){\sum }_{k=m}^r(-1{)}^{k-m}(\genfrac{}{}{0ex}{}{r-m}{k-m}).$ Let $j=k-m$: $\left(\genfrac{}{}{0ex}{}{r}{m}\right){\sum }_{j=0}^{r-m}(-1{)}^j(\genfrac{}{}{0ex}{}{r-m}{j})=(\genfrac{}{}{0ex}{}{r}{m})(1-1{)}^{r-m}.$ WHY the binomial theorem here: ${\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{N}{j})=(1-1{)}^N$ collapses the alternating sum to $0^N$.

• If $r>m$: $(1-1{)}^{r-m}=0$ → contributes $0$. ✓
• If $r=m$: $(1-1{)}^0=1$, and $\left(\genfrac{}{}{0ex}{}{m}{m}\right)=1$ → contributes $1$. ✓
• If $r<m$: the sum is empty → $0$. ✓ Every element in exactly $m$ sets contributes $1$, all others $0$. Hence $E_m$ counts them exactly. $■$