✖

क्रमचय और संचय

क्या आप जानना चाहते हैं कि 52 पत्तों की ताश की गड्डी से पाँच-पाँच पत्तों के कितने भिन्न समूह चुने जा सकते हैं? ठीक इसी प्रकार के प्रश्न क्रमचय और संचय (combinatorics) में हल किए जाते हैं। गणना के दो आधारभूत नियम हैं: योग का नियम और गुणन का नियम। गणना की अन्य सभी विधियाँ इन्हीं दो सिद्धांतों का विस्तार हैं।

योग का नियम

योग का नियम बहुत सरल है। मान लीजिए दो समुच्चय A, B हैं, जिनमें कोई भी अवयव उभयनिष्ठ नहीं है। तब सम्मिलन A ∪ B से एक अवयव चुनने के कुल तरीकों की संख्या |A| + |B| होती है, अर्थात् दोनों समुच्चयों के अवयवों की संख्याओं का योग।

आइए, एक आसान उदाहरण से शुरू करें। हमारे पास 6 लाल गेंदें और 8 नीली गेंदें हैं। ये सभी गेंदें हम एक थैले में डाल देते हैं। यदि हम थैले से बिना देखे एक गेंद निकालें, तो कुल कितने परिणाम संभव हैं? शुरू में हमारे पास लाल गेंदों का समुच्चय था, इसे समुच्चय A कहते हैं, और नीली गेंदों का समुच्चय, इसे B कहते हैं। ये समुच्चय असंयुक्त हैं, अर्थात् इनमें कोई भी गेंद उभयनिष्ठ नहीं है। हमें एक गेंद निकालनी है, इसलिए कुल |A| + |B| = 6 + 8 = 14 परिणाम संभव हैं। बस इतना ही।

गुणन का नियम

फिर से दो समुच्चय Z और M लेते हैं। समुच्चय Z में तीन महिलाएँ हैं और समुच्चय M में चार पुरुष। अब प्रश्न है कि इन समुच्चयों से पुरुष–महिला के कितने भिन्न जोड़े बनाए जा सकते हैं? हम क्या करना चाहते हैं? हर बार एक महिला लेकर उसके साथ कोई एक पुरुष जोड़ते हैं। सभी जोड़ों की संख्या इस प्रकार गिनते हैं: एक महिला, प्रिया, को लेते हैं और बारी-बारी से उसके साथ सभी पुरुषों को जोड़ते हैं। इस तरह 4 भिन्न जोड़े बनते हैं, क्योंकि प्रिया के साथ कुल 4 भिन्न पुरुष जोड़े जा सकते हैं। बची हुई दो महिलाओं के लिए भी यही करते हैं। उनमें से प्रत्येक से भी 4-4 जोड़े और बनते हैं। बस, कुल 4 + 4 + 4 = 12 जोड़े हो गए।

वास्तव में हमने क्या किया? हमने दोनों समुच्चयों के अवयवों की संख्याओं को गुणा किया। हमारे पास 3 महिलाएँ और 4 पुरुष थे, इसलिए जोड़ों की कुल संख्या 3 · 4 = 12 है। इसीलिए इसे गुणन का नियम (गणना का आधारभूत सिद्धांत) कहते हैं। यदि दो समुच्चयों से हम जोड़े बनाते हैं, तो बस एक समुच्चय के अवयवों की संख्या को दूसरे समुच्चय के अवयवों की संख्या से गुणा कर देते हैं।

नीचे आप स्वयं देख सकते हैं कि यह वास्तव में सत्य है। ये वे सभी जोड़े हैं, जो 3 महिलाओं और 4 पुरुषों से बनाए जा सकते हैं। प्रत्येक पंक्ति एक महिला के जोड़े दर्शाती है और प्रत्येक स्तंभ एक पुरुष के। इस प्रकार तीन पंक्तियाँ और चार स्तंभ हैं, अर्थात् कुल पंक्तियाँ · स्तंभ जोड़े।

(Z1,M1),(Z1,M2),(Z1,M3),(Z1,M4),(Z2,M1),(Z2,M2),(Z2,M3),(Z2,M4),(Z3,M1),(Z3,M2),(Z3,M3),(Z3,M4)

हल सहित उदाहरण

  1. दो अंकों की कितनी भिन्न संख्याएँ होती हैं? दो अंकों की संख्या कैसी दिखती है? पहले स्थान पर अंकों 1, …, 9 में से कोई एक होता है, जबकि दूसरे स्थान पर शून्य भी आ सकता है: 0, …, 9। इस प्रकार पहले समुच्चय में 9 अंक हैं और दूसरे में 10। गुणन का नियम लगाने पर अंतिम परिणाम मिलता है: 9 · 10 = 90।
  • तीन अंकों की ऐसी कितनी भिन्न संख्याएँ होती हैं, जिनमें कोई भी अंक दो बार न आए? पहले स्थान पर फिर से नौ अंक हो सकते हैं, क्योंकि संख्या शून्य से शुरू नहीं हो सकती। दूसरे स्थान पर शून्य सहित सभी अंक आ सकते हैं, पर वह अंक नहीं, जो पहले स्थान पर है। इसलिए दस संभव अंकों में से एक घटाते हैं। (उदाहरण के लिए, यदि हमारी तीन अंकों की संख्या 4 से शुरू होती है, तो स्पष्ट है कि दूसरे स्थान पर 4 नहीं आ सकता, वरना पूरी संख्या में 4 दो बार होगा।) तीसरे स्थान पर भी सभी अंक आ सकते हैं, पर वे दो अंक नहीं, जो पहले या दूसरे स्थान पर हैं। कारण वही है। यदि पहले स्थान पर 4 और दूसरे स्थान पर 7 है, तो तीसरे स्थान पर हम समुच्चय {0, …, 9} ∖ {4, 7} का कोई एक अंक रख सकते हैं। कुल दस अंकों में से हमें दो घटाने होंगे। अब बस गुणा करना है: 9 · 9 · 8 = 648। अतः ऐसी कुल 648 संख्याएँ हैं।
  • एक सामान्य पासे को लगातार दो बार फेंकते हैं। कितने भिन्न परिणाम मिल सकते हैं? पहली फेंक में पासे पर 6 भिन्न परिणाम आ सकते हैं। दूसरी फेंक में भी, इसलिए परिणामों की कुल संख्या 6 · 6 = 36 है।
  • पासे को लगातार दो बार फेंकते हैं। यदि पहली फेंक में सम संख्या आई हो, तो कितने भिन्न परिणाम मिल सकते हैं? पहली फेंक में सम संख्या आई, अर्थात् संख्याओं 2, 4, 6 में से कोई एक। ये कुल 3 विकल्प हैं। दूसरी फेंक में कोई भी संख्या आ सकती है, इसलिए कुल 3 · 6 = 18 परिणाम संभव हैं।

विषय-सूची: क्रमचय और संचय, n में से k वस्तुओं के क्रमचय, सभी वस्तुओं के क्रमचय, संचय, पुनरावृत्ति सहित क्रमचय, पुनरावृत्ति सहित संचय, कितने भिन्न PIN संभव हैं?