गणना के नियम, क्रमचय और संचय

उद्देश्य और मान्यताएँ

हर परिणाम अलग लिखे बिना सीमित परिणामों की संख्या गिनना सीखें। तय करें कि विकल्प अलग-अलग मामलों में बँटते हैं या लगातार चरणों में; क्रम वाले विन्यास और बिना क्रम वाले चयन में अंतर करें; दोहराव, पाबंदियों और साझा परिणामों को संभालें; और pigeonhole principle से मिलने वाली गारंटी समझें। पूर्वज्ञान: सीमित समुच्चय, गुणा, factorial और सामान्य तर्क। जिन वस्तुओं को अलग बताया गया है, वे वास्तव में पहचानी जा सकती हैं। अन्यथा न कहा हो तो घुमाए गए क्रम अलग हैं, स्थानों की पहचान निश्चित है और चयन बिना पुनरावृत्ति के है। Recurrences, generating functions, उन्नत inclusion–exclusion और probability के लिए आगे के पाठ चाहिए।

पहले स्पष्ट करें कि एक परिणाम क्या है। समिति {A,B} और {B,A} एक ही समिति हैं। अध्यक्ष–सचिव का आवंटन (A,B), आवंटन (B,A) से अलग है। दोनों में दो व्यक्ति चुने जाते हैं, लेकिन परिणाम अलग प्रकार के हैं। यह निर्णय कोई सूत्र आपकी जगह नहीं कर सकता।

1. जोड़ और गुणा के नियम

यदि काम दो परस्पर अलग तरीकों में से ठीक एक से होता है और पहले तरीके के a तथा दूसरे के b परिणाम हैं, तो कुल a+b परिणाम होंगे। उदाहरण: चार गणित electives या तीन computing electives में से एक course चुनना है; दोनों सूचियों में कोई course साझा नहीं है। कुल सात विकल्प हैं। किसी course का दोनों सूचियों में होना सीधे जोड़ने पर दोहरी गिनती देगा।

यदि काम लगातार चरणों में होता है, पहले चरण के a विकल्प हैं और उसके हर विकल्प के बाद दूसरे चरण के ठीक b विकल्प हैं, तो कुल ab परिणाम हैं। तीन shirts और दो trousers से छह outfits बनते हैं। दूसरे चरण की उपलब्ध वस्तुएँ पहले चयन के साथ बदल सकती हैं; उनकी संख्या b रहनी चाहिए। पाँच विद्यार्थियों से दो अलग विद्यार्थियों का ordered pair चुनने में 5×4=20 विकल्प हैं। पहले विद्यार्थी के अनुसार दूसरा बदलता है, फिर भी चार विकल्प बचते हैं।

शाखाओं में विकल्पों की संख्या अलग हो तो हर शाखा गिनकर जोड़ें। पहला symbol A या B हो। A के बाद 0,1,2 की अनुमति हो और B के बाद केवल 0,1 की। कुल 3+2=5 strings हैं, 2×3 नहीं। विकल्पों का tree बनाना ऐसी असमान शाखाएँ पहचानने में मदद करता है।

2. क्रम वाले विन्यास

n अलग वस्तुओं को पूरा क्रम देने के n!=n(n−1)…1 तरीके हैं। 0!=1 परिभाषित करते हैं: खाली विन्यास का एक तरीका है। n अलग वस्तुओं में से r चुनकर क्रम देने के P(n,r)=n!/(n−r)! तरीके हैं, जहाँ 0≤r≤n पूर्णांक हैं और कोई वस्तु दोबारा नहीं ली जाती। पहले स्थान के n, दूसरे के n−1 और अंतिम के n−r+1 विकल्प हैं।

हल किया उदाहरण: सात प्रतिभागियों में अलग-अलग व्यक्तियों को gold, silver और bronze देना है। पुरस्कारों की पहचान अलग है और किसी व्यक्ति को दो पुरस्कार नहीं मिलते। इसलिए P(7,3)=7×6×5=210। इसे 3! से भाग देने पर यह जानकारी मिट जाएगी कि किसे कौन-सा पुरस्कार मिला; वह अलग सवाल होगा।

यदि r निश्चित स्थानों पर पुनरावृत्ति स्वीकार्य है और हर स्थान पर सभी n symbols आ सकते हैं, तो n^r परिणाम हैं। {A,B,C} से चार-symbol strings की संख्या 3^4=81 है। String आवश्यक रूप से decimal integer नहीं है: code में शुरुआती zero स्वीकार्य है, जब तक नियम उसे मना न करे।

हल किया उदाहरण: बिना दोहराए digit वाली तीन-अंकीय decimal संख्या बनाएँ। सैकड़े के स्थान पर नौ विकल्प (1–9) हैं। दहाई पर फिर नौ विकल्प हैं: zero और बचे आठ nonzero digits। इकाई पर आठ बचते हैं। कुल 9×9×8=648। 10×9×8 में शुरुआती zero गलत ढंग से स्वीकार होगा; 9×8×7 हर स्थान पर zero को गलत ढंग से मना करेगा।

3. बिना क्रम वाले चयन

n अलग वस्तुओं में से r को बिना पुनरावृत्ति चुनने के C(n,r)=n!/[r!(n−r)!] तरीके हैं। हर unordered r-element subset, ordered selections में r! बार आता है। इसलिए r! से भाग देना सही है: हर चयन के ठीक इतने क्रम हैं। सात में से तीन समिति सदस्य चुनने के 210/6=35 तरीके हैं।

C(n,0)=C(n,n)=1। किसी को न चुनने का एक खाली चयन है; शून्य चयन नहीं। C(n,r)=C(n,n−r) भी सही है: चुनी गई वस्तुएँ तय करने पर बाहर की वस्तुएँ भी तय हो जाती हैं। ये अच्छे cross-check हैं। r यदि 0…n के बाहर हो तो ऐसा subset नहीं है। कुछ परंपराओं में वहाँ C(n,r)=0 लेते हैं, लेकिन ऊपर के factorial सूत्र में negative factorial नहीं लगाना चाहिए।

समान symbols दोहरें तो बिना सोचे r! से भाग देना गलत हो सकता है। AABC के विन्यास में दोनों A को अस्थायी रूप से अलग label दें। तब 4! विन्यास हैं। केवल A के labels बदलने पर दिखाई देने वाली string नहीं बदलती। इसलिए अलग दिखाई देने वाले विन्यास 4!/2!=12 हैं। यह समान प्रतियों का तर्क है, replacement के साथ चयन का नहीं। यहाँ combinations with repetition का पूरा सूत्र नहीं पढ़ते।

4. पाबंदियों के लिए अलग-अलग मामले

चार researchers और तीन designers में से तीन की समिति चुनें, जिसमें कम-से-कम एक designer हो। Complement से गिनें: सभी समितियाँ C(7,3)=35, बिना designer की समितियाँ C(4,3)=4। उत्तर 31 है। “कम-से-कम एक” में एक, दो और तीन designers शामिल हैं; इसका अर्थ “ठीक एक” नहीं है।

अलग मामलों से जाँचें। ठीक एक designer: C(3,1)C(4,2)=18। ठीक दो: C(3,2)C(4,1)=12। ठीक तीन: C(3,3)C(4,0)=1। कुल 18+12+1=31। हर वैध समिति ठीक एक मामले में आती है। दोनों तरीकों का मिलना उपयोगी जाँच है और overlapping cases पकड़ सकता है।

Complement counting में पूरा universe स्पष्ट होना चाहिए: वैध = सभी − अवैध। पाँच-bit strings में कम-से-कम एक 1 चाहिए तो कुल 2^5=32 strings में केवल 00000 अवैध है; 31 बचती हैं। ठीक दो 1 चाहिए तो उनके स्थान चुनें: C(5,2)=10। इसे 2^3 से गुणा नहीं करेंगे, क्योंकि बचे स्थानों पर केवल 0 आ सकता है।

5. साझा परिणाम और inclusion–exclusion

सीमित sets A और B के लिए |A∪B|=|A|+|B|−|A∩B|। साझा वस्तु की दोहरी गिनती घटाने पर हर वस्तु एक बार बचती है। यदि 18 विद्यार्थी logic, 15 algebra और 7 दोनों पढ़ते हैं, तो कम-से-कम एक विषय पढ़ने वाले 26 हैं। कुल 40 विद्यार्थी हों तो 40−26=14 कोई भी विषय नहीं पढ़ते। Union 33 नहीं है। “दोनों में से कोई नहीं” और “दोनों साथ नहीं” अलग शर्तें हैं।

तीन sets में पहले तीनों की संख्या जोड़ें, तीनों pair intersections घटाएँ और triple intersection एक बार वापस जोड़ें। तीनों sets में मौजूद वस्तु 3−3+1=1 बार गिनी जाती है। Pair intersection में triple intersection की वस्तुएँ भी आती हैं, जब तक प्रश्न “केवल इन्हीं दो में” न कहे। दोनों अर्थों को अलग रखें।

6. Pigeonhole principle

N वस्तुएँ k उपलब्ध डिब्बों में रखी जाएँ और k≥1 हो, तो किसी डिब्बे में कम-से-कम ceil(N/k) वस्तुएँ होंगी। कोई डिब्बा खाली भी रह सकता है; k उपलब्ध श्रेणियों की संख्या है। यदि हर डिब्बे में अधिकतम ceil(N/k)−1 वस्तुएँ हों, तो कुल क्षमता N से कम होगी, जो असंभव है।

उदाहरण: 13 वस्तुओं और 4 डिब्बों में किसी एक में कम-से-कम 4 वस्तुएँ होंगी। यह गारंटी सबसे मजबूत है: 4,3,3,3 का वितरण दिखाता है कि 5 की गारंटी नहीं दे सकते। सामान्यतः k(m−1)+1 वस्तुएँ रखने पर किसी डिब्बे में कम-से-कम m होंगी। यह किसी एक डिब्बे के अस्तित्व का निष्कर्ष है; यह नहीं बताता कि कौन-सा डिब्बा होगा या हर डिब्बे में m होंगी।

सवाल हल करने की जाँच-सूची

एक परिणाम का अर्थ लिखें। तय करें कि क्रम महत्वपूर्ण है या नहीं, दोहराव स्वीकार्य है या नहीं और स्थानों पर अलग पाबंदियाँ हैं या नहीं। समान संख्या वाली लगातार शाखाओं में गुणा, अलग मामलों में जोड़ और साझा परिणामों में inclusion–exclusion लगाएँ। पाबंदी के लिए सीधे गिनने की तुलना complement से करें। अंत में छोटा उदाहरण सूची बनाकर जाँचें। उत्तर गैर-ऋणात्मक पूर्णांक होना चाहिए और बिना पाबंदी की गिनती से अधिक नहीं होना चाहिए।

7. तीन sets के inclusion–exclusion का हल किया उदाहरण

40 विद्यार्थियों में A, B और C तीन विषय पढ़ने वालों के sets हों। मानें |A|=20, |B|=18, |C|=12, |A∩B|=8, |A∩C|=5, |B∩C|=4 और |A∩B∩C|=2। Pair-intersection की गिनतियों में तीनों विषय पढ़ने वाले भी शामिल हैं।

तब |A∪B∪C|=20+18+12−8−5−4+2=35, इसलिए 5 कोई विषय नहीं पढ़ते। “केवल A और B” में 8−2=6 विद्यार्थी हैं, 8 नहीं। ठीक दो विषयों में (8−2)+(5−2)+(4−2)=11 विद्यार्थी हैं। अलग क्षेत्रों से जाँचें: केवल A=20−8−5+2=9, केवल B=8 और केवल C=5। इसलिए ठीक एक विषय=22, ठीक दो=11 और तीनों=2; कुल 35।

यह उदाहरण बताता है कि शब्दों का अर्थ क्यों महत्वपूर्ण है। “A और B दोनों” में सामान्यतः तीनों विषय पढ़ने वाले भी आते हैं। “A और B, लेकिन C नहीं” में triple intersection नहीं आता। प्रश्न जाँचे बिना इन दोनों अर्थों के लिए एक ही संख्या न लें।

मौलिक अभ्यास: छह single-correct MCQ

ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।

C01. Code में तीन निश्चित स्थान हैं। हर स्थान पर A,B,C,D में से कोई symbol आ सकता है और दोहराव स्वीकार्य है। कितने codes हैं?

A. 12 B. 24 C. 64 D. 81

उत्तर: C

A: 4+4+4 लगातार चरणों को जोड़ता है; यहाँ गुणा चाहिए।

B: 4×3×2 गलत ढंग से दोहराव रोकता है।

C: तीनों स्थानों पर चार-चार विकल्प हैं; 4^3=64।

D: 3^4 में symbols और स्थानों की संख्या उलट गई।

C02. बिना दोहराए digit वाली तीन-अंकीय decimal संख्याएँ कितनी हैं?

A. 720 B. 648 C. 504 D. 900

उत्तर: B

A: 10×9×8 पहले स्थान पर zero स्वीकारता है, जिससे तीन-अंकीय संख्या नहीं बनेगी।

B: पहले नौ nonzero digits, फिर zero सहित नौ बचे digits, फिर आठ: कुल 648।

C: 9×8×7 हर स्थान से zero गलत ढंग से हटाता है।

D: 9×10×10=900 में digit दोहरा सकते हैं।

C03. सात अलग व्यक्तियों में से बिना क्रम की तीन-सदस्यीय समितियाँ कितनी चुनी जा सकती हैं?

A. 21 B. 210 C. 343 D. 35

उत्तर: D

A: C(7,2)=21 दो व्यक्ति चुनता है, तीन नहीं।

B: P(7,3)=210 हर समिति के 3!=6 क्रम अलग गिनता है।

C: 7^3 पुनरावृत्ति और स्थानों का अंतर मानता है; दोनों यहाँ लागू नहीं।

D: C(7,3)=7×6×5/(3×2×1)=35; समिति में क्रम महत्वपूर्ण नहीं।

C04. चार researchers और तीन designers से बनी तीन-सदस्यीय समितियों में कम-से-कम एक designer वाली कितनी हैं?

A. 31 B. 18 C. 34 D. 35

उत्तर: A

A: कुल 35 में से केवल researchers वाली चार समितियाँ घटाएँ: 35−4=31।

B: 18 में ठीक एक designer है; दो और तीन वाले मामले छूटते हैं।

C: 34 सभी designers वाली समिति हटाता है, जबकि वह वैध है।

D: 35 में बिना designer वाली चार समितियाँ भी शामिल हैं।

C05. 40 के समूह में 18 logic, 15 algebra और 7 दोनों पढ़ते हैं। कोई भी विषय न पढ़ने वाले कितने हैं?

A. 7 B. 26 C. 14 D. 33

उत्तर: C

A: 40−18−15=7 साझा सात विद्यार्थियों को दो बार घटाता है।

B: 26 union की संख्या है, यानी कम-से-कम एक विषय; कोई भी नहीं की संख्या नहीं।

C: कम-से-कम एक: 18+15−7=26; कोई भी नहीं: 40−26=14।

D: 33 overlap सुधारे बिना दोनों गिनतियाँ जोड़ता है; यह neither नहीं है।

C06. हर संभव वितरण में चार डिब्बों में से किसी एक में कम-से-कम पाँच वस्तुओं की गारंटी के लिए न्यूनतम कुल कितनी वस्तुएँ चाहिए?

A. 16 B. 17 C. 20 D. 5

उत्तर: B

A: सोलह का वितरण 4,4,4,4 हो सकता है; किसी में पाँच नहीं।

B: हर डिब्बे में पाँच से कम रखते हुए अधिकतम 16 रह सकती हैं; सत्रहवीं किसी में पाँच कर देती है।

C: बीस पर्याप्त हैं, न्यूनतम नहीं; 17 से ही गारंटी है।

D: पाँच का वितरण 2,1,1,1 हो सकता है; किसी में पाँच आवश्यक नहीं।

स्रोत और दायरा

यह आधारभूत पाठ आधिकारिक GATE 2027 CS पाठ्यक्रम के Section 1 में Discrete Mathematics से जुड़ा है। यह पूरे विषय या पूरे पाठ्यक्रम की समाप्ति नहीं है। स्रोत विषय की प्रासंगिकता बताता है; उदाहरण और अभ्यास प्रश्न मौलिक हैं।

Official GATE 2027 CS syllabus (verified 2026-10-14).