Worked examples — Inclusion-exclusion principle

4.9.2 · D3 · Maths › Probability Theory & Statistics › Inclusion-exclusion principle

Shuru karne se pehle, sirf ek rule ka reminder, words mein:

---

Scenario matrix

Har inclusion–exclusion problem jo kabhi milegi woh in cells mein se ek hogi. Right column mein us example ka naam hai jo usse clearly explain karta hai.

#	Case class	Kya cheez tricky banati hai	Explained by
C1	2 sets, generic overlap	ek baar subtract karna yaad rakho	Ex 1
C2	2 sets, disjoint ($A\cap B=\varnothing$)	overlap term zero hai	Ex 2
C3	2 sets, ek doosre ke andar ($A\subseteq B$)	union bade set pe collapse ho jaata hai	Ex 2
C4	3 sets, full formula	"+triple" restoration	Ex 3
C5	Complement trick ("inme se koi nahi" / "kam se kam ek")	opposite count karo, total se subtract karo	Ex 4
C6	Probability version (measures, counts nahi)	universe se divide karo / $P$ use karo	Ex 5
C7	Degenerate: sab sets equal	union = unme se koi bhi ek	Ex 6
C8	Limiting behaviour (derangement ratio jab $n\to \infty$)	infinite sign-alternating sum	Ex 7
C9	Exam twist: "exactly $r$" nahi "at least one"	alag coefficients	Ex 8
C10	4 sets, real-world word problem	four-way sign bookkeeping	Ex 9

---

Ex 1 — C1: do sets, generic overlap

Steps.

1. Sets name karo. $A$ = French padhne wale, $|A|=22$; $B$ = German, $|B|=17$; $|A\cap B|=9$. Yeh step kyun? Inclusion–exclusion ko overlap size explicitly naam chahiye — yahi toh poora point hai.
2. Singles add karo: $|A|+|B|=22+17=39$. Yeh step kyun? Isse "dono" wale har student do baar count hote hain, toh yeh zyada hai.
3. Overlap ek baar subtract karo: $39-9=30$. Yeh step kyun? $9$ dono-wale students do baar count hue the; $9$ subtract karne se woh ek baar count hote hain.

$|A\cup B|=22+17-9=30.$

Verify: disjoint pieces mein partition karo — sirf French $=22-9=13$, sirf German $=17-9=8$, dono $=9$. Sum $13+8+9=30$. ✓ Aur $30\le 40$, toh class mein fit hota hai. ✓

---

Ex 2 — C2 & C3: disjoint sets, aur ek set doosre ke andar

Steps for (a) — disjoint case C2.

1. Disjoint matlab $A\cap B=\varnothing$, toh $|A\cap B|=0$. Yeh step kyun? General formula tab bhi apply hoti hai — zero overlap bas ek special value hai.
2. $|A\cup B|=12+7-0=19$.

Verify (a): koi overlap nahi toh kuch double-count nahi hua, seedha addition already sahi hai. $19$. ✓

Steps for (b) — nested case C3.

1. $A\subseteq B$ matlab har chess player already games club mein hai, toh $A\cap B=A$ aur $|A\cap B|=|A|=8$. Yeh step kyun? Overlap wahi chhota set hota hai jab ek set doosre ke andar ho.
2. $|A\cup B|=|A|+|B|-|A\cap B|=8+20-8=20$.

Verify (b): union bas bada set $B$ hai, toh $|B|=20$ hona chahiye. ✓ Formula ne naive $28$ nahi diya — kyunki $8$ chess players naye log nahi hain.

---

Ex 3 — C4: teen sets, full formula (figure ke saath)

Figure dekho: centre region (teeno) har pairwise lens ke andar hai.

Steps.

1. Singles add karo: $60+50+40=150$. Yeh step kyun? Jo do drinks mein hai woh do baar count hua; jo teeno mein hai woh teen baar count hua.
2. Pairs subtract karo: $-(30+20+15)=-65$, deta hai $150-65=85$. Yeh step kyun? Yeh sirf-pair wale logon ki double-counting fix karta hai, lekin all-three group ko over-erase karta hai.
3. All-three group of $10$ track karo: step 1 mein $+3$ baar add hua, step 2 mein $-3$ baar subtract hua → net $0$. Yeh galat hai; hum chahte hain $1$. Yeh step kyun? Isi liye $+$triple exist karta hai — figure mein dark centre dekho.
4. Triple wapas add karo: $85+10=95$.

$|T\cup C\cup J|=60+50+40-30-20-15+10=95.$

Verify: "koi nahi" $=100-95=5$. 7 disjoint Venn regions mein bhi decompose karke sum karo: sirf-T $=60-30-20+10=20$, sirf-C $=50-30-15+10=15$, sirf-J $=40-20-15+10=15$, T∩C-only $=30-10=20$, T∩J-only $=20-10=10$, C∩J-only $=15-10=5$, teeno $=10$. Total $=20+15+15+20+10+5+10=95$. ✓

---

Ex 4 — C5: complement trick ("at least one" via "none")

Yahan naya tool kyun: "$2$ ya $3$ ya $5$ se divisible" directly count karna hai inclusion–exclusion — lekin yeh problem complement idea bhi sikhati hai jo Ex 7 mein use hoti hai. Pehle seedha karte hain.

Steps.

1. Singles — $100$ tak ke multiples count karo. $\lfloor 100/2\rfloor =50$, $\lfloor 100/3\rfloor =33$, $\lfloor 100/5\rfloor =20$. Yeh step kyun? $\lfloor 100/d\rfloor$ = $d$ ke multiples ki count jo $\le 100$ hain (har $d$-va number). $\lfloor x\rfloor$ matlab "==$x$ ko whole number mein round down karo=="
2. Pairs — dono $a$ aur $b$ se divisible matlab $\text{lcm}(a,b)$ se divisible. $\text{lcm}(2,3)=6:\lfloor 100/6\rfloor =16$; $\text{lcm}(2,5)=10:\lfloor 100/10\rfloor =10$; $\text{lcm}(3,5)=15:\lfloor 100/15\rfloor =6$. Yeh step kyun? "2 aur 3 dono se divisible" intersection hai, aur lcm woh sabse chhota number hai jise dono divide karte hain.
3. Triple — $\text{lcm}(2,3,5)=30:\lfloor 100/30\rfloor =3$.
4. Alternating signs ke saath assemble karo: $50+33+20-(16+10+6)+3=103-32+3=74.$

Verify (complement): kisi bhi $2,3,5$ se divisible nahi — yaani coprime-ish survivors $=100-74=26$. Sanity check: kisi se bhi divisible nahi wale $1,7,11,13,\dots$ jaise kuch numbers honge; $26$ plausible hai. Direct union $=74$. ✓

---

Ex 5 — C6: probability version

Probability counts ki jagah kyun: universe size $52$ se har count divide karne se same formula probabilities mein badal jaata hai — additivity bilkul same hai.

Steps.

1. $P(A)=13/52=1/4$ (13 hearts). $P(B)=12/52=3/13$ (12 face cards). Yeh step kyun? Equally-likely event ki probability $=$ favourable $÷$ total.
2. Overlap: face-card hearts hain J♥, Q♥, K♥, toh $|A\cap B|=3$, $P(A\cap B)=3/52$. Yeh step kyun? $A\cap B$ = cards jo dono heart aur face hain.
3. Probability ke liye inclusion–exclusion: $P(A\cup B)=\frac{13}{52}+\frac{12}{52}-\frac{3}{52}=\frac{22}{52}=\frac{11}{26}.$

Verify: union seedha count karo — hearts (13) plus non-heart face cards ($12-3=9$) $=22$ cards, $22/52=11/26\approx 0.423$. Expected se bada (humne face cards add kiye). ✓ Valid probability hai, $0\le 11/26\le 1$. ✓

---

Ex 6 — C7: fully degenerate case (sab sets equal)

Steps.

1. Har set mein $5$ elements hain, aur har intersection (pair ya triple) bhi wohi pura set hai, size $5$. Yeh step kyun? Jab sets coincide karte hain, sab overlaps usi ek set pe collapse ho jaate hain.
2. 3-set formula apply karo: $|A\cup B\cup C|=\underset{15}{\underbrace{(5+5+5)}}-\underset{15}{\underbrace{(5+5+5)}}+\underset{5}{\underbrace{5}}=5.$

Verify: teen identical sets ka union bas wahi set hai, size $5$. Formula deta hai $15-15+5=5$. ✓ Yeh general "element in $m=3$ sets counted exactly once" identity in action hai: $\left(\genfrac{}{}{0ex}{}{3}{1}\right)-\left(\genfrac{}{}{0ex}{}{3}{2}\right)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)=3-3+1=1$, toh $5$ elements mein se har ek ka net $1$ aata hai. ✓

---

Ex 7 — C8: limiting behaviour (derangements jab $n\to \infty$)

Inclusion–exclusion kyun: "kam se kam ek letter sahi" events "letter $i$ sahi" ka union hai; complement hai "koi nahi sahi".

Steps.

1. $A_i$ = permutations jo position $i$ fix karti hain. $|A_i|=(n-1)!$, $k$-fold intersection $k$ chosen spots fix karti hai: $(n-k)!$, $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways se chuna gaya. Yeh step kyun? $k$ letters sahi fix karne se baaki ke $(n-k)!$ arrangements bachte hain.
2. "Kam se kam ek fixed" $={\sum }_{k=1}^n(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{n}{k})(n-k)!$. "None fixed" ke liye $n!$ se subtract karo: $D_n={\sum }_{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}.$ Yeh step kyun? $\left(\genfrac{}{}{0ex}{}{n}{k}\right)(n-k)!=n!/k!$, $n!$ bahar nikalte hain.
3. $n=4$ ke liye: $D_4=24\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)=24\cdot \frac{9}{24}=9$. Probability $=9/24=3/8=0.375$.
4. Limit: ${\sum }_{k=0}^{\infty }\frac{(-1{)}^k}{k!}=e^{-1}$ (exponential series at $-1$). Toh $D_n/n!\to e^{-1}\approx 0.3679$. Yeh step kyun? $e^x=\sum x^k/k!$ ko $x=-1$ pe evaluate karo; sign-alternating I–E terms exactly yahi series hain.

Verify: $D_4=9$ (parent note se match karta hai). $9/24=0.375$, aur $e^{-1}=0.367879\dots$ — $n=4$ pe already bahut close. ✓ "No match" ki chance khatam nahi hoti; $37\%$ ke paas settle hoti hai.

---

Ex 8 — C9: exam twist ("exactly one", "at least one" nahi)

Alag coefficients kyun: "exactly one" ke liye aisa formula chahiye jo multi-membership cancel out kare, union se alag multipliers deta hai.

Steps.

1. Ex 3 ke Verify se disjoint-region decomposition use karo: sirf-T $=20$, sirf-C $=15$, sirf-J $=15$. Yeh step kyun? "Exactly ek drink" = teen single-only regions ka sum.
2. Add karo: $20+15+15=50$.
3. Coefficient formula se cross-check karo: $\text{exactly one}=\sum |A_i|-2\sum |A_i\cap A_j|+3|A\cap B\cap C|.$ $=150-2(65)+3(10)=150-130+30=50.$ Yeh step kyun? Exactly $2$ sets mein wala element net $0$ hona chahiye: $2-2\cdot 1=0$; teeno mein: $3-2\cdot 3+3=0$. Sirf single-membership coefficient $1$ ke saath bachti hai.

Verify: dono methods $50$ dete hain. Saath mein: exactly-two total $=20+10+5=35$, exactly-three $=10$, koi nahi $=5$; $50+35+10+5=100$. ✓

---

Ex 9 — C10: chaar sets, real-world word problem

Steps.

1. Singles add karo ($+$): $30+25+18+12=85$. Yeh step kyun? $k=1$, sign $(-1{)}^2=+$.
2. Sab $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ pairs subtract karo ($-$): $15+10+6+8+5+4=48$, deta hai $85-48=37$. Yeh step kyun? $k=2$, sign $-$; double-counting fix karta hai.
3. Sab $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ triples add karo ($+$): $5+3+2+2=12$, deta hai $37+12=49$. Yeh step kyun? $k=3$, sign $+$; triple-erased logon ko restore karta hai.
4. Single quadruple subtract karo ($-$): $49-1=48$. Yeh step kyun? $k=4$, sign $-$; all-four wala person triples se over-add hua tha.

$|Y\cup J\cup C\cup R|=85-48+12-1=48.$

Verify: answer $48\le 50$ team size, toh $2$ logon ko koi nahi aata — plausible hai. All-four person track karo: add hua $\left(\genfrac{}{}{0ex}{}{4}{1}\right)=4$ (singles) $-\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ (pairs) $+\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ (triples) $-\left(\genfrac{}{}{0ex}{}{4}{4}\right)=1$ (quad) $=4-6+4-1=1$. Exactly ek baar count hua. ✓

---

Recall Kaun sa cell kaunsa tha?

C1 generic 2-set (Ex1) ::: overlap ek baar subtract karo C2 disjoint / C3 nested (Ex2) ::: overlap $0$ hai ya chhota set hai C4 teen sets (Ex3) ::: triple wapas add karo C5 complement (Ex4) ::: "koi nahi" $=$ total $-$ union C6 probability (Ex5) ::: same formula $P$ ke saath C7 sab equal (Ex6) ::: union $=$ koi bhi ek set C8 limit (Ex7) ::: $D_n/n!\to e^{-1}$ C9 exactly-one (Ex8) ::: coefficients $1,-2,+3$ C10 chaar sets (Ex9) ::: signs $+,-,+,-$

---

Connections

• Inclusion-exclusion principle — parent note: woh formula jo yeh examples exercise karte hain
• Set Theory & Venn Diagrams — Ex 3 & 8 mein use ki gayi disjoint-region decomposition
• Counting Principles & Combinatorics — Ex 7 & 9 mein intersections ki $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ counts
• Probability Axioms — Ex 5 ka probability form additivity plus overlap correction hai
• Derangements & Permutations — Ex 7 classic derangement payoff hai
• Binomial Theorem — Ex 7 mein $\sum (-1{)}^k/k!\to e^{-1}$ limit
• Bonferroni Inequalities — in alternating sums ko truncate karne se bounds milte hain