✖

पुनरावृत्ति सहित संचय

पुनरावृत्ति सहित संचय सामान्य संचयों जैसे ही होते हैं, बस इनमें आधार समुच्चय M (जिसमें से वस्तुएँ चुनी जाती हैं) के अवयव दोहराए जा सकते हैं।

परिभाषा और सूत्र

आइए, एक अच्छे उदाहरण से शुरू करें: आप दुकान पर जाते हैं और पिकनिक के लिए जूस की बारह बोतलें ख़रीदना चाहते हैं। रैक में कुल चार प्रकार के जूस हैं। अब बोतलें ख़रीदने के आपके पास कई विकल्प हैं: उदाहरण के लिए, आप आम की 5, संतरे की 2, अमरूद की 1 और लीची की 4 बोतलें ले सकते हैं, या हर प्रकार की तीन-तीन बोतलें। कुल बारह बोतलें ख़रीदने के कितने भिन्न तरीके हैं?

इस प्रकार हमारे पास आधार समुच्चय M = {आम, संतरा, अमरूद, लीची} है और हम पूछते हैं कि k = 12 वाले ऐसे कितने k-टपल हैं, जिनमें समुच्चय M के अवयव हों और जिनमें क्रम का महत्व न हो?

यहाँ सूत्र की व्युत्पत्ति गणना के अन्य प्रश्नों की तुलना में कुछ कठिन है। सबसे पहले हम अपनी ख़रीदारी को शून्यों और इकाइयों (अंक 1) के अनुक्रम के रूप में दर्शाते हैं: इकाइयों की संख्या किसी प्रकार की ख़रीदी गई बोतलों की संख्या बताती है और शून्य अलग-अलग प्रकारों को अलग करता है। इसलिए 111011101111101 बताता है कि हमने आम की तीन बोतलें लीं (पहले तीन 1), फिर संतरे की तीन (0 विभाजक है, फिर तीन 1), फिर अमरूद की पाँच (0 विभाजक और फिर पाँच 1) और अंत में लीची की एक। पूरा सिद्धांत यह आरेख दर्शाता है:

111⏟आम0111⏟संतरा011111⏟अमरूद01⏟लीची

यदि हम आम की 6, संतरे की 4, लीची की 2 और अमरूद की एक भी बोतल न लेना चाहें, तो अनुक्रम ऐसा दिखेगा:

111111⏟आम01111⏟संतरा0011⏟लीची

ध्यान दीजिए कि इस अनुक्रम की लंबाई हमेशा 15 होती है: इसमें 12 इकाइयाँ होनी चाहिए, ताकि कुल 12 बोतलें ख़रीदी जाएँ। और इसमें तीन विभाजक होने चाहिए, ताकि चार अलग-अलग प्रकार अलग किए जा सकें। अब बस यह गिनना बाकी है कि 15 लंबाई वाले ऐसे कुल कितने अनुक्रम हैं, जिनमें ठीक तीन शून्य हों?

केवल शून्यों के स्थान गिनना पर्याप्त है: जैसे ही हम 12 इकाइयों के बीच 3 शून्य रख देते हैं, हमें बोतलों का एक मान्य संचय मिल जाता है। दूसरे शब्दों में: हमारे पास कुल 15 स्थान हैं और उनमें से 3 पर हमें शून्य रखना है। बचे हुए स्थानों पर अपने-आप इकाइयाँ आ जाती हैं।

यह पुनरावृत्ति रहित संचय का एक सरल प्रश्न है। 15 स्थानों को संख्याओं {1, …, 15} से क्रमांकित करते हैं और अब इस समुच्चय से हर बार तीन संख्याएँ चुनते हैं। इस प्रकार तीन सूचकांक मिलते हैं, जहाँ शून्य रखना है। उदाहरण के लिए, संचय {2, 4, 7} से अनुक्रम मिलेगा: 101011011111111। दूसरे, चौथे और सातवें स्थान पर शून्य है, बाकी इकाइयाँ हैं। इस प्रकार 15 स्थानों में शून्य रखने के कुल

(153)=455

भिन्न तरीके हैं। इसलिए जूस के चार प्रकार होने पर 12 बोतलें ख़रीदने के भी 455 भिन्न तरीके हैं।

इस तर्क को व्यापक रूप दिया जा सकता है। यदि हमारे पास n अवयवों वाला समुच्चय M है और हम उससे k-टपल चुनते हैं, जिनमें अवयव दोहराए जा सकते हैं, तो हम n + k − 1 लंबाई का शून्यों और इकाइयों का अनुक्रम बनाते हैं (k इकाइयाँ और n − 1 शून्य) और यह ज्ञात करते हैं कि n − 1 शून्य कितने तरीकों से रखे जा सकते हैं। अतः n प्रकार की वस्तुओं में से k वस्तुओं के पुनरावृत्ति सहित संचयों की संख्या है:

n+k−1Ck=(n+k−1n−1)=(n+k−1k).

अंतिम चरण हम द्विपद गुणांकों के आधारभूत संबंधों के कारण लिख सके।

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

  1. किसी नाटक के पहले शो के 20 मुफ़्त पास मोहल्ले की 10 दादियों में कितने तरीकों से बाँटे जा सकते हैं? यह पुनरावृत्ति सहित संचय का उदाहरण है, क्योंकि एक दादी को एक से अधिक, यहाँ तक कि सभी, मुफ़्त पास मिल सकते हैं। हमें बस ठीक से समझना है कि n क्या है और k क्या। वास्तव में हम 10 दादियों में से 20 अवयवों वाले संचय बनाते हैं। दूसरे शब्दों में, हम शून्यों और इकाइयों का ऐसा अनुक्रम बनाते हैं, जिसकी लंबाई 29 है और जिसमें 20 इकाइयाँ और 9 शून्य हैं। अतः n = 10, k = 20। हमें परिणाम मिलता है:

29C20=(10+20−120)=1,00,15,005.

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