Question bank — Inclusion-exclusion principle

aur reason Agar $A\cap B=\varnothing$ ho to do-set formula galat hai aur use nahi karna chahiye ::: False — ye phir bhi correct hai: $|A\cap B|=0$, isliye $|A\cup B|=|A|+|B|-0=|A|+|B|$, jo exactly disjoint-addition rule hai. Probability Axioms additivity ko is special case ke roop mein dekho. General formula mein, ek term ka sign is baat par depend karta hai ki woh intersection kitne sets join karta hai ::: True — ek $k$-fold intersection ka sign $(-1{)}^{k+1}$ hota hai: odd $k$ ko $+$ milta hai, even $k$ ko $-$, chahe koi bhi sets involved hon. $|A|+|B|+|C|$ add karne par teeno sets mein maujood ek element theek teen baar count hota hai ::: True — woh $|A|$, $|B|$, $|C|$ mein se har ek ke andar ek baar pakda jaata hai, isliye teen additions; baad ke $-$pairs aur $+$triple corrections usse wapas net karke ek tak le aate hain. Union $A\cup B\cup C$ mein ek aisa student jo exactly ek drink pasand karta hai aur ek aisa student jo teeno pasand karta hai, dono ek hi tarah count hote hain ::: True — union ka matlab hai "ek ya zyada sets mein," isliye dono exactly ek baar count hote hain; "exactly one" ek alag quantity hai jiske alag coefficients hain. Inclusion–exclusion agar kaafi sets hon to negative answer de sakta hai ::: False — final count ek cardinality (ya probability) hai, hamesha $\ge 0$; individual terms ka sign alternate hota hai lekin total provably union ka sahi size hota hai. "Subtract all the pairwise intersections" ke baad rokne par true union size ka lower bound milta hai ::: True — yeh ek Bonferroni bound hai: I–E ko subtraction ke baad truncate karne par under-count hota hai, addition ke baad over-count, isliye partial sums answer ko bracket karte hain. Identity ${\sum }_{k=0}^m(-1{)}^k(\genfrac{}{}{0ex}{}{m}{k})=0$ woh reason hai ki har element ek baar count hota hai ::: True — yeh Binomial Theorem se $(1-1{)}^m=0$ hai; $k=0$ term alag karne par baki alternating sum $1$ ke barabar hone ke liye majboor hota hai. Derangement application mein, $|A_i|=(n-1)!$ isliye hai kyunki ek position fix karne par baaki free hain ::: True — $A_i$ = wo permutations jo position $i$ fix karti hain; baaki $n-1$ symbols freely permute hote hain, jo $(n-1)!$ arrangements deta hai. Derangements & Permutations dekho.

"Kyunki maine already $|A\cap B|$, $|A\cap C|$, aur $|B\cap C|$ subtract kar liye hain, teen-set union $\sum |A_i|$ minus woh teen hai." ::: Galat — teeno mein maujood ek element ab $3-3=0$ par hai, isliye woh bilkul miss ho jaata hai; tumhe add back $+|A\cap B\cap C|$ ek baar karna hi hoga. "Survey kehta hai $60+50+40=150$ students out of 100 ko ek drink pasand hai, isliye data impossible hai." ::: Galat reading — $150$ woh sum hai double/triple counting ke saath; I–E overlaps ko hataa kar $95\le 100$ tak le aata hai, jo consistent hai. "30 se neeche 3 ya 5 ke multiples count karne ke liye, main $3\times 5=15$ ke multiples subtract karta hoon." ::: Yahan sirf isliye correct hai kyunki $\gcd (3,5)=1$; overlap $\mathrm{lcm}(3,5)$ ke multiples hain, aur $\mathrm{lcm}=15$ product ke barabar sirf coprime numbers ke liye hota hai. "Mujhe bataya gaya hai $|A\cup B|=40$, $|A|=30$, $|B|=20$, isliye $|A\cup B|=30+20-|A\cap B|=50-|A\cap B|$ aur main union paane ke liye formula dobara apply karta hoon." ::: Circular — union diya hua hai; formula ko ulta use karo taaki $|A\cap B|=30+20-40=10$ mile, jo pehle se pata hai use dobara derive mat karo. "'Exactly one of $A,B,C$' ke liye main bas $|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$ leta hoon." ::: Galat — yeh union hai (at least one). "Exactly one" mein alag coefficients hote hain: $\sum |A_i|-2\sum |A_i\cap A_j|+3|A\cap B\cap C|$. "Alternating-sign proof mein, $k=0$ term irrelevant hai kyunki humara sum $k=1$ se shuru hota hai." ::: Galat — $k=0$ term $\left(\genfrac{}{}{0ex}{}{m}{0}\right)=1$ exactly wahi hai jo hum $(1-1{)}^m=0$ se alag karte hain taaki prove kar sakein ki $k\ge 1$ sum $1$ ke barabar hai; yeh argument ka anchor hai.

Signs alternate kyun karte hain rather than, say, pehle ke baad sab minus? ::: Kyunki $m$ sets mein maujood ek element level $k$ par $\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ baar appear karta hai, aur sirf alternating pattern $(-1{)}^{k+1}$ hi ${\sum }_{k=1}^m(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{m}{k})=1$ ko har $m$ ke liye ek saath hold karata hai. Do-set case woh "atom" kyun hai jisse sab kuch bana hai? ::: Har over-count fundamentally ek pairwise double-count hai; higher terms sirf un elements ke liye recursive fix-ups hain jo do se zyada sets share karte hain, har ek pichli layer ko correct karta hai. Har term ko $|S|$ se divide karne par counting formula probability formula mein kyun convert ho jaata hai? ::: Cardinalities relative frequencies $|A|/|S|=P(A)$ ban jaati hain equally-likely outcomes ke under; additive structure preserve hoti hai, isliye I–E probabilities ke liye bhi identically hold karta hai. Derangement count mein I–E "at least one fixed point" par kyun use hota hai rather than no-fixed-point directly count karne ke? ::: "No fixed point" ek mushkil negative condition hai; I–E naturally "fixes position $i$" events ke unions count karta hai, aur $D_n=n!-(\text{at least one fixed point})$ easily convert ho jaata hai. Hum union ko simply intersections list karke bina proof mein $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ combinatorics ke kyun count nahi kar sakte? ::: $m$ sets mein maujood ek element $\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ alag $k$-fold intersections se belong karta hai, isliye kitne terms use hit karte hain ka combinatorial count exactly wahi hai jo proof ko track karna hai. Jab sab sets pairwise disjoint hain to I–E plain additivity mein kyun reduce ho jaata hai? ::: Saare intersections empty hain, isliye har correction term $0$ hai aur sirf $\sum |A_i|$ bachta hai — disjoint sum recover ho jaata hai. Set Theory & Venn Diagrams dekho.

Jab $n=1$ ho (ek single set) to I–E kya deta hai? ::: Bas $|A_1|$ — sum mein ek term hai, sign $(-1{)}^{1+1}=+1$, aur koi intersection exist nahi karta; formula gracefully degenerate ho jaata hai. Agar ek set empty ho, $A_j=\varnothing$? ::: $A_j$ contain karne wale har term ki size $0$ hoti hai, isliye woh silently drop ho jaata hai; answer baaki sets ke union ke barabar hota hai — koi special handling nahi chahiye. Agar do sets identical hon, $A=B$? ::: Tab $|A\cap B|=|A|=|B|$, isliye $|A\cup B|=|A|+|A|-|A|=|A|$, correctly ek set ki worth report karta hai — formula redundancy ko self-correct karta hai. $m=0$ sets mein maujood ek element (union ke bahar) ke liye alternating-sum proof mein kya hota hai? ::: Proof sirf $m\ge 1$ ke liye correctness claim karta hai; kisi set mein na hone wala element $0$ terms contribute karta hai aur $0$ baar count hota hai, jo exactly sahi hai kyunki woh union mein nahi hai. Kya I–E tab bhi kaam karta hai jab universe infinite ho lekin har $A_i$ finite ho? ::: Haan — formula sirf finite cardinalities $|A_{i_1}\cap \cdots \cap A_{i_k}|$ use karta hai; surrounding universe ka size counting version mein kabhi appear nahi karta. Agar sab $n$ sets mutually equal hon, to kitne distinct nonzero intersection values appear karte hain? ::: Sirf ek — har $k$-fold intersection common set ke barabar hai, isliye total ${\sum }_{k=1}^n(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{n}{k})=1$ ke through telescope karke ek single set ki size par aa jaata hai.