Inclusion-exclusion principle — Hinglish notes

4.9.2 · Maths › Probability Theory & Statistics

YEH principle exist kyun karta hai?

Naive addition mein KYA galat hota hai: ek element jo $k$ sets mein hai, woh $k$ baar add hota hai jabki hum chahte hain ki woh sirf $1$ baar add ho. Humein ek aisa correction chahiye jo har $k \geq 1$ ke liye net $1$ de.

Do-set case ko scratch se derive karna

YEH kyon shuru karte hain: har general case isi se banta hai.

Union $A \cup B$ ko teen disjoint pieces mein partition karo:

sirf $A$ (not $B$ ): size $a$
sirf $B$ (not $A$ ): size $b$
dono $A$ aur $B$ : size $c = ∣ A \cap B ∣$

Phir disjoint addition se: $∣ A \cup B ∣ = a + b + c .$ Lekin $∣ A ∣ = a + c$ aur $∣ B ∣ = b + c$ . Toh: $∣ A ∣ + ∣ B ∣ = (a + c) + (b + c) = a + b + 2 c .$ Yeh step kyun? Overlap $c$ dono $∣ A ∣$ aur $∣ B ∣$ mein aata hai, isliye do baar. $c = ∣ A \cap B ∣$ ki ek copy subtract karo: $∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣ = a + b + c = ∣ A \cup B ∣. ✓$

Teen sets — derive karo, memorise mat karo

Pehle singles add karo, phir hum pairwise overlaps ko over-subtract kar dete hain aur triple ko wapas add karna padta hai.

$∣ A ∣ + ∣ B ∣ + ∣ C ∣ ek triple-element ko 3 baar count karta hai.$ Teen pairwise intersections subtract karo: $- (∣ A \cap B ∣ + ∣ A \cap C ∣ + ∣ B \cap C ∣) .$ Yeh step kyun? Har pairwise term exactly do sets mein rehne wale elements ka double-counting remove karti hai — theek hai. Lekin ek element jo teeno sets mein hai, woh teeno pairwise intersections mein tha, toh ushe $3$ baar add hone ke baad $3$ baar subtract kar diya gaya → net $0$ . Yeh galat hai; hum chahte hain ki woh ek baar count ho.

Toh triple intersection ek baar wapas add karo: $+ ∣ A \cap B \cap C ∣.$

General formula (aur signs alternate kyun karte hain)

Alternating signs kyun forced hain — first-principles proof. Koi bhi element $x$ lo jo exactly $m$ sets mein hai ( $m \geq 1$ ). Hume dikhana hai ki right-hand side ise exactly ek baar count karta hai.

$x$ , $(1 m)$ single terms mein, $(2 m)$ pair terms mein, …, $(k m)$ , $k$ -fold intersections mein aata hai.
Iska net contribution hai: $S = \sum_{k = 1}^{m} (- 1)^{k + 1} (k m) .$ Binomial theorem use karo $x = - 1$ ke saath: $\sum_{k = 0}^{m} (- 1)^{k} (k m) = (1 - 1)^{m} = 0.$ Yeh step kyun? Yeh ek identity hamare saare terms contain karti hai, including $k = 0$ term $(0 m) = 1$ . $k = 0$ alag karo: $0 = (0 m) + \sum_{k = 1}^{m} (- 1)^{k} (k m) = 1 - \sum_{k = 1}^{m} (- 1)^{k + 1} (k m) = 1 - S .$ Sign flip kyun? $k \geq 1$ ke liye, $(- 1)^{k} = - (- 1)^{k + 1}$ , toh $\sum_{k = 1}^{m} (- 1)^{k} (k m) = - S$ . Isliye $0 = 1 - S$ , jo deta hai $S = 1.$ Har element exactly ek baar count hota hai — QED.

Probability version

Worked examples

Common mistakes

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho tumne class mein poocha "kaun football khelta hai, aur kaun cricket?" aur dono haath-counts add kar liye. Kuch bacchon ne haath do baar uthaya kyunki woh dono khelte hain! Toh tum unhe over-count kar loge. Fix karne ke liye, tum dono-wale players ko ek baar count karo aur subtract karo, taaki har koi sirf ek baar count ho. Teen sports ke saath thoda aur tricky hai: jab tum overlapping pairs subtract karte ho toh "teeno khelne wale" bacche accidentally poori tarah erase ho jaate hain, toh tumhe unhe wapas add karna padta hai. Yeh add–subtract–add dance hi inclusion–exclusion hai.

Active recall

Two-set inclusion–exclusion formula

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

Do-set case mein intersection subtract kyun karte hain

Dono sets mein rehne wale elements

∣ A ∣ + ∣ B ∣

mein do baar count hote hain;

∣ A \cap B ∣

subtract karne se ek extra count remove ho jaata hai.

Three-set inclusion–exclusion formula

∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣

General I–E mein sign pattern

Odd-size intersections ko

+

milta hai, even-size ko

-

k

sets wale term ka sign

(- 1)^{k + 1}

hota hai.

Exactly

m

sets mein rehne wale element ka net count

Exactly

1

, kyunki

\sum_{k = 1}^{m} (- 1)^{k + 1} (k m) = 1

Do events ke liye probability form

P (A \cup B) = P (A) + P (B) - P (A \cap B)

I–E se derangement formula

D_{n} = n! \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}

\leq 29

integers mein 3 ya 5 se divisible kitne hain

9 + 5 - 1 = 13

Triple intersection wapas kyun add karte hain

Teeno-mein-rehne-wala element 3 baar add (singles) aur 3 baar subtract (pairs) hota hai, net 0 hota hai; ek baar add karne se correct count 1 restore hota hai.

Connections

Set Theory & Venn Diagrams — woh union/intersection structure jo is principle ka aadhar hai
Counting Principles & Combinatorics — general proof mein $(k n)$ use hota hai
Probability Axioms — additivity axiom disjoint special case hai
Derangements & Permutations — ek classic application
Binomial Theorem — woh $(1 - 1)^{m} = 0$ identity provide karta hai jo alternating signs prove karta hai
Bonferroni Inequalities — I–E ko truncate karne se upper/lower bounds milte hain