Exercises — Inclusion-exclusion principle

KAUNSA tool: two-set inclusion–exclusion, kyunki hum ek union ke baare mein pooch rahe hain aur hume overlap diya gaya hai. KYUN ghataate hain: woh $5$ dono-wale log $18$ ke andar bhi hain aur $12$ ke andar bhi, toh seedha addition unhe do baar count karti hai. $|D\cup C|=|D|+|C|-|D\cap C|=18+12-5=25.$ Answer: $25$.

$|A\cap C\cap D|$ ek $k=3$ sets ka intersection hai. Sign hai $(-1{)}^{k+1}=(-1{)}^4=+$. KYUN: teen odd hai, aur odd-size intersections add kiye jaate hain. Answer: $+$ (positive).

Maano $A$ = $4$ ke multiples, $B$ = $6$ ke multiples.

• $|A|=\lfloor 100/4\rfloor =25.$
• $|B|=\lfloor 100/6\rfloor =16.$
• $|A\cap B|$ = $\mathrm{lcm}(4,6)=12$ ke multiples: $\lfloor 100/12\rfloor =8.$ KYUN $4\cdot 6$ nahin, lcm: koi number jo dono $4$ aur $6$ se divisible ho, woh unke least common multiple, $12$ se divisible hona chahiye — product $24$ se nahin (warna $12,36,60,\dots$ miss ho jaayenge). $|A\cup B|=25+16-8=33.$ Answer: $33$.

$55+50+40-20-15-12+8.$ Step by step: singles $=145$; pairs ghataao $145-47=98$; triple jodo $98+8=106$. KYUN $+8$: woh $8$ all-three students $3$ baar add kiye gaye (har single mein ek baar) aur $3$ baar ghataaye gaye (har pair mein ek baar), net $0$ hua — toh unhe ek baar wapas restore karna padega. Answer: $106$.

KAUNSA tool: inclusion–exclusion se "kam se kam ek" count karo, phir total se ghataao — "none" ko directly count karne se kahin zyada aasaan hai. Neeche shaded region dekho.

Maano $A,B,C$ kramashah $2,3,5$ ke multiples hain.

• Singles: $\lfloor 1000/2\rfloor =500,\lfloor 1000/3\rfloor =333,\lfloor 1000/5\rfloor =200.$
• Pairs (lcm use karo): $\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.$ Kisi se bhi divisible nahin: $1000-734=266.$ KYUN complement: "kisi se divisible nahin" union ka bahar hai; total minus union ek line mein de deta hai. Answer: $266$.

KYUN ek nayi formula: union "one or more" count karta hai, lekin hum strictly ek chahte hain. Exactly ek set mein jo element ho woh ek baar count ho; exactly do mein ho toh zero baar; exactly teen mein ho toh zero baar. "Exactly one" ki count hai $\sum |A_i|-2{\sum }_{i<j}|A_i\cap A_j|+3|A\cap B\cap C|.$ KYUN coefficients $-2,+3$ hain: exactly do sets mein koi element $\left(\genfrac{}{}{0ex}{}{2}{1}\right)=2$ singles mein aur $\left(\genfrac{}{}{0ex}{}{2}{2}\right)=1$ pair mein aata hai, toh $2-2(1)=0$. Teeno mein wala element $3$ singles, $3$ pairs, $1$ triple mein aata hai: $3-2(3)+3(1)=0$. Sirf "exactly ek mein" wala coefficient $1$ ke saath bachta hai. $=145-2(47)+3(8)=145-94+24=75.$ Answer: $75$.

KAUNSA tool: inclusion–exclusion se "bad" functions count karo jo kam se kam ek box miss karte hain, phir saare $3^5$ functions se ghataao. Maano $A_i$ = woh functions jo box $b_i$ ko avoid karte hain.

• Total functions: $3^5=243.$
• $|A_i|$ = doosre $2$ boxes mein functions $=2^5=32$; inke $\left(\genfrac{}{}{0ex}{}{3}{1}\right)=3$ hain.
• $|A_i\cap A_j|$ = baaki $1$ box mein functions $=1^5=1$; inke $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$ hain.
• $|A_1\cap A_2\cap A_3|$ = $0$ boxes mein functions $=0$; $\left(\genfrac{}{}{0ex}{}{3}{3}\right)=1$. Kam se kam ek box miss karne wale functions: $3(32)-3(1)+0=96-3=93.$ Surjections $=243-93=150.$ KYUN yeh formula se match karta hai: surjections $={\sum }_{k=0}^3(-1{)}^k(\genfrac{}{}{0ex}{}{3}{k})(3-k{)}^5=243-96+3-0=150.$ Answer: $150$.

KAUNSA tool: derangements $D_n$, ek inclusion–exclusion ka payoff (parent example 3 dekho). Maano $A_i$ = woh arrangements jahan letter $i$ apne sahi envelope mein hai, toh $|A_i|=(n-1)!$, aur $k$-fold intersection $k$ letters ko fix karta hai: $(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).$ Bracket compute karo: $0+0.5-0.1\overline{6}+0.041\overline{6}-0.008\overline{3}=0.36\overline{6}$, aur $120\times \frac{44}{120}=44.$ Answer: $D_5=44$.

KAUNSA tool: Bonferroni Inequalities — inclusion–exclusion ko odd number of terms par truncate karne se over-estimate milta hai (upper bound); even number par under-estimate (lower bound).

• $1$ term ke baad (odd → upper): $P(\cup )\le \sum P(A_i)=3(0.4)=\mathrm{1.2.}$ (Trivially $1$ par cap.)
• $2$ terms ke baad (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.}$ Toh $0.9\le P(A\cup B\cup C)\le 1.$ KAB exact $=$ lower bound $0.9$: equality tab hoti hai jab triple intersection empty ho, $P(A\cap B\cap C)=0$, kyunki full formula lower bound mein $+P(A\cap B\cap C)$ add karta hai. Answer: bounds $[0.9,1]$; exact $=0.9$ iff $P(A\cap B\cap C)=0$.

Strategy: ek element $x$ fix karo jo exactly $r$ sets mein hai, aur dikhao ki woh $E_m$ mein $1$ contribute karta hai jab $r=m$ ho aur $0$ otherwise. Phir saare $x$ par sum karne se count mil jaati hai.

$S_k$ mein uska contribution. $x$ ek $k$-fold intersection mein tab aata hai jab chune gaye saare $k$ sets us $r$ mein se hon jo use contain karte hain, toh woh $S_k$ mein $\left(\genfrac{}{}{0ex}{}{r}{k}\right)$ contribute karta hai (aur $0$ agar $k>r$).

$E_m$ mein uska contribution. Substitute karo: ${\sum }_{k=m}^n(-1{)}^{k-m}(\genfrac{}{}{0ex}{}{k}{m}\left)\right(\genfrac{}{}{0ex}{}{r}{k}).$ Subset-of-a-subset identity use karo $\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)$ (KYUN: $r$ mein se $k$ choose karna phir un $k$ mein se $m$ choose karna, barabar hai $r$ mein se directly woh $m$ choose karna phir bache hue $r-m$ mein se $k-m$ choose karna). $\left(\genfrac{}{}{0ex}{}{r}{m}\right)$ factor out karo: $\left(\genfrac{}{}{0ex}{}{r}{m}\right){\sum }_{k=m}^r(-1{)}^{k-m}(\genfrac{}{}{0ex}{}{r-m}{k-m}).$ $j=k-m$ let karo: $\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}.$ KYUN yahan binomial theorem: ${\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{N}{j})=(1-1{)}^N$ alternating sum ko $0^N$ mein collapse kar deta hai.

• Agar $r>m$: $(1-1{)}^{r-m}=0$ → $0$ contribute karta hai. ✓
• Agar $r=m$: $(1-1{)}^0=1$, aur $\left(\genfrac{}{}{0ex}{}{m}{m}\right)=1$ → $1$ contribute karta hai. ✓
• Agar $r<m$: sum empty hai → $0$. ✓ Exactly $m$ sets mein har element $1$ contribute karta hai, baaki sab $0$. Isliye $E_m$ unhe exactly count karta hai. $■$