Inclusion–exclusion, onto functions और derangements
उद्देश्य और पूर्वज्ञान
Bad-event sets बनाना, intersections गिनना, सही multiplicities के साथ inclusion–exclusion लगाना और onto functions, missing symbols तथा permutations के fixed points हल करना सीखें। पूर्वज्ञान: finite sets, functions के terms, combinations और permutations। यह पहले two-/three-set rule को गहरा करता है; असंबंधित formulas की नई सूची नहीं।
हर event एक निश्चित finite universe का subset है। Counts अपने आप probabilities नहीं। Probability पूछी हो तो universe size से तभी divide करें जब दिए random experiment में outcomes equally likely हों।
1. Alternating intersection counts क्यों सही हैं
A₁,…,A_k का union count: सभी single-set sizes जोड़ें, सभी pairwise intersections घटाएँ, triple intersections जोड़ें, और आगे इसी तरह। j अलग events के intersection का sign (−1)^{j+1} है। Union के बाहर का count universe size से शुरू होकर signs (−1)^j लेता है, जिसमें events का empty selection शामिल है।
कारण: ठीक t≥1 events में आने वाला object singles में C(t,1), pairs में C(t,2), आदि बार गिना जाता है। Union में उसका कुल योगदान C(t,1)−C(t,2)+⋯+(−1)^{t+1}C(t,t)=1, क्योंकि Σ(j=0 से t)(−1)^j C(t,j)=(1−1)^t=0। किसी event में न आने वाले object का योगदान zero। इस तरह हर union object ठीक एक बार गिना जाता है।
यह proof दो गलतियाँ दिखाता है। Intersections वापस जोड़े बिना सभी bad sets घटाने पर object कई बार हट सकता है। दूसरी ओर pairwise intersections में सामान्यतः triple intersection वाले objects भी होते हैं; उन्हें चुपचाप “ठीक इन दो” के counts न मानें।
2. Arithmetic universe का worked example
U={1,2,…,120} लें। A में 2 के multiples, B में 3 के और C में 5 के। Sizes 60,40,24 हैं। Intersection का अर्थ एक साथ divisibility है, इसलिए least common multiple लें: |A∩B|=floor(120/6)=20, |A∩C|=12, |B∩C|=8 और |A∩B∩C|=4।
Union count 60+40+24−20−12−8+4=88। इसलिए 2,3,5 में से किसी से divisible न होने वाले ठीक 120−88=32 integers। यहाँ divisors pairwise coprime हैं, लेकिन general rule lcm है, हमेशा product नहीं। 4 और 6 से divisibility के intersection में divisor 12 है, 24 नहीं।
Union में “या” inclusive है: दो या तीनों properties वाले numbers भी शामिल। “ठीक एक” अलग लक्ष्य है और अलग coefficients चाहिए।
3. ठीक एक, ठीक दो, कम-से-कम दो
तीन events में S₁=|A|+|B|+|C|, S₂=|A∩B|+|A∩C|+|B∩C| और S₃=|A∩B∩C| लिखें। तब:
- ठीक तीन: S₃।
- ठीक दो: S₂−3S₃।
- कम-से-कम दो: S₂−2S₃।
- ठीक एक: S₁−2S₂+3S₃।
Guess करने के बजाय derive करें। ठीक दो events का object S₁ में दो बार और S₂ में एक बार। तीनों का object S₁ में तीन बार और S₂ में भी तीन बार। Formula में योगदान रखकर देखें कि माँगी category के अनुसार 0 या 1 मिलता है।
Divisibility example में S₁=124,S₂=40,S₃=4। ठीक दो: 40−12=28; कम-से-कम दो: 40−8=32; ठीक एक: 124−80+12=56। Disjoint categories ठीक एक, ठीक दो और ठीक तीन का sum 56+28+4=88, जिससे union check होता है। बाहर का count भी 32 है, लेकिन यह इन data का संयोग है, theorem नहीं।
4. Onto functions: missing targets को हटाएँ
Domain में n labeled और codomain में k labeled elements हों, n,k≥1। कुल functions kⁿ हैं। हर codomain element i के लिए A_i वे functions हैं जो target i इस्तेमाल नहीं करते। Function onto तभी और केवल तभी है जब किसी A_i में न हो।
j targets का कोई निश्चित set missing हो तो हर domain element के k−j choices हैं, इसलिए intersection count (k−j)ⁿ। Missing set चुनने के C(k,j) तरीके। Inclusion–exclusion से onto count
Σ(j=0 से k)(−1)^j C(k,j)(k−j)ⁿ।
n=4,k=3 में 3⁴−3·2⁴+3·1⁴−0⁴=81−48+3=36। यह injections नहीं गिनता: चार domain elements को तीन targets में inject नहीं कर सकते, लेकिन कई onto functions हैं। k>n में onto function नहीं, क्योंकि हर target hit करने के लिए domain elements कम हैं; sum तब zero होता है।
n=k में count k! है, क्योंकि बराबर आकार के finite sets के बीच onto और one-to-one equivalent हैं। Positive n और k=1 में ठीक एक onto function। Empty domain/codomain cases सीधे definition से लें; conventions बताए बिना इस positive-parameter formula में न डालें।
5. ठीक दी हुई संख्या में symbols इस्तेमाल करना
k-symbol alphabet का length-n word, n labeled positions से symbols तक function है। n,k≥1 तथा 1≤r≤min(n,k) में ठीक r distinct symbols के लिए पहले used set C(k,r) तरीकों से चुनें, फिर n positions से उन r symbols तक onto functions गिनें। अलग chosen sets की word collections disjoint हैं, इसलिए multiplication सही।
{A,B,C,D} पर length-4 words में ठीक दो symbols इस्तेमाल हों तो C(4,2)(2⁴−2)=6·14=84। दो symbols चुनने के बाद दो constant words घटाएँ। ABAB और BABA अलग हैं, क्योंकि positions labeled हैं। केवल दो symbols चुनकर 2⁴ से multiply करने पर एक ही symbol वाले words भी गलत शामिल होंगे।
Onto labeled boxes का संबंध unlabeled nonempty groups की partitions से है। चार distinct objects को तीन nonempty unlabeled groups में बाँटें। हर partition के groups को 3! तरीकों से labels मिल सकते हैं, इसलिए count 36/6=6। स्वतंत्र check: एक group में दो elements और बाकी singleton होंगे; pair C(4,2)=6 तरीकों से चुनें। Division इसलिए सही कि तीनों groups nonempty हैं और labels ठीक 3! तरीकों से मिलते हैं।
6. Derangements: कोई fixed point नहीं
{1,…,n} का permutation π एक bijection है। Fixed point वह i है जहाँ π(i)=i। Derangement में कोई fixed point नहीं। D_n उनका count हो। A_i में i को fix करने वाले permutations रखें। j-element का निश्चित set fixed हो तो बचे n−j elements को (n−j)! तरीकों से permute कर सकते हैं। बाकी में भी fixed points allowed हैं, क्योंकि intersection inclusive है।
Inclusion–exclusion देता है
D_n=Σ(j=0 से n)(−1)^j C(n,j)(n−j)!=n! Σ(j=0 से n)(−1)^j/j!।
चार objects में D₄=24−4·6+6·2−4·1+1=9। 24 से केवल चार single fixed-point sets घटाकर intersections न लौटाएँ तो गलत zero मिलता है। पाँच में D₅=120−120+60−20+5−1=44। इसलिए कम-से-कम एक fixed point वाले permutations 120−44=76।
D₀=1 लें: empty permutation बिना fixed point का अकेला permutation है। D₁=0, क्योंकि अकेला one-element permutation अपना element fix करता है। इन conventions से आगे exact-fixed-point formulas endpoints पर सही रहते हैं।
7. ठीक r fixed points
n labels में ठीक r fixed points चाहिए तो उनका set C(n,r) तरीकों से चुनें और बाकी n−r labels को derange करें। Count C(n,r)D_{n−r} है। बाकी permutation उन labels के सापेक्ष derangement होना चाहिए; (n−r)! लेने पर extra fixed points allowed हो जाएँगे और “कम-से-कम ये r” गिनेंगे।
n=5 और ठीक दो fixed points में C(5,2)D₃=10·2=20। Three-label set के दो derangements उसकी दो 3-cycles हैं। पाँच में ठीक चार fixed points असंभव: बचा अकेला label भी अपने स्थान पर forced है; C(5,4)D₁=0 यही बताता है। ठीक पाँच fixed points में C(5,5)D₀=1।
Consistency check: Σ(r=0 से n)C(n,r)D_{n−r}=n!, क्योंकि हर permutation का fixed-point count और set तय है। Disjoint cases जोड़ सकते हैं; overlapping fixed-point events में inclusion–exclusion चाहिए।
समस्या हल करने की जाँच-सूची
एक universe तय करें और हर bad event स्पष्ट परिभाषित करें। पहले events के एक निश्चित selected set का intersection गिनें, फिर ऐसे selections की संख्या से multiply करें। “कोई नहीं”, “कम-से-कम एक”, “ठीक एक”, “ठीक r” अलग रखें। Onto functions, injections और permutations अलग हैं। उत्तर negative, universe से बड़ा या छोटे hand-enumerated case से असंगत हो तो event model दोबारा देखें, केवल arithmetic को बदलकर ठीक न दिखाएँ।
मौलिक अभ्यास: छह single-correct MCQ
मौलिक प्रश्न हैं, पिछले वर्षों के नहीं। हर प्रश्न में ठीक एक विकल्प चुनें और labels, symmetry, domain तथा positivity की दी शर्तें रखें।
C01. 1 से 120 तक कितने integers 2,3,5 में से किसी से divisible नहीं?
A. 88 B. 36 C. 32 D. 28
उत्तर: C
A: 88 union है, यानी कम-से-कम एक से divisible integers।
B: इसमें pair और triple intersections का सही हिसाब नहीं।
C: Union 60+40+24−20−12−8+4=88; complement 120−88=32।
D: 28 ठीक दो से divisible integers गिनता है, किसी से नहीं वाले नहीं।
C02. उसी 1,…,120 universe में कितने integers 2,3,5 से divisibility की ठीक एक property पूरी करते हैं?
A. 56 B. 88 C. 84 D. 64
उत्तर: A
A: S₁=124,S₂=40,S₃=4 से ठीक एक: S₁−2S₂+3S₃=56।
B: यह inclusive union है और double/triple members भी गिनता है।
C: S₁−S₂=84 में triple contribution zero, लेकिन double members एक बार बचे हैं; ठीक एक नहीं।
D: Multiplicity correction सही नहीं; ठीक एक वाले का योगदान एक और double/triple का zero चाहिए।
C03. चार-element labeled domain से तीन-element labeled codomain तक कितने onto functions हैं?
A. 81 B. 24 C. 0 D. 36
उत्तर: D
A: 81=3⁴ सभी functions हैं, missing targets वाले भी।
B: 4! चार labels के permutations गिनता है, अलग function model।
C: यहाँ zero injection count है, onto count नहीं।
D: Missing targets हटाएँ: 3⁴−3·2⁴+3·1⁴=36। Overlapping missing-target events में positive correction जरूरी।
C04. {A,B,C,D} पर length-4 के कितने words ठीक दो distinct symbols लेते हैं?
A. 96 B. 84 C. 14 D. 144
उत्तर: B
A: C(4,2)·2⁴ में केवल एक chosen symbol वाले constant words भी आ जाते हैं।
B: दो symbols 6 तरीकों से और दोनों का उपयोग 2⁴−2=14 तरीकों से; total 84।
C: 14 केवल एक fixed symbol-pair का count, pair चुनना बाकी।
D: Used pairs 6 और हर pair के valid words 14 हैं, 24 नहीं; 144 बताई class नहीं गिनता।
C05. चार labeled elements पर कितने derangements हैं?
A. 24 B. 0 C. 9 D. 6
उत्तर: C
A: 24 सभी permutations हैं, fixed points वाले भी।
B: चार single fixed-point events घटाकर intersections वापस न जोड़ने से यह गलत परिणाम आता है।
C: Inclusion–exclusion से D₄=24−4·6+6·2−4+1=9।
D: 6 केवल 4-cycles हैं; दो disjoint swaps वाले तीन permutations भी derangements हैं।
C06. पाँच labeled elements के कितने permutations में ठीक दो fixed points हैं?
A. 20 B. 60 C. 10 D. 44
उत्तर: A
A: दो fixed labels C(5,2)=10 तरीकों से चुनें, बचे तीन के D₃=2 derangements; total 20।
B: 10·3! में बाकी labels के extra fixed points allowed हो जाते हैं और माँगी class overcount होती है।
C: 10 केवल fixed set चुनता है; बाकी labels के दो derangements छूटते हैं।
D: 44, D₅ है: कोई fixed point नहीं वाला count, ठीक दो वाला नहीं।
स्रोत और दायरा
यह मौलिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 में Discrete Mathematics के combinatorial counting भाग को गहरा करता है। आधिकारिक syllabus व्यापक विषय बताता है; MIT chapter counting methods का संस्थागत further-study स्रोत है। यहाँ examples, व्याख्या और अभ्यास मौलिक हैं। एक पाठ से पूरे subject में mastery का दावा नहीं।
स्रोत खोले और जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन