✖

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

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

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

आइए, एक विशिष्ट उदाहरण से शुरू करें: अंग्रेज़ी वर्णमाला के अक्षरों (abc … xyz, कुल 26) से 6 लंबाई वाले कितने भिन्न शब्द बनाए जा सकते हैं? छह अक्षर ज़्यादा नहीं हैं, फिर भी ऐसे शब्द काफ़ी अधिक होंगे। हमें शब्दों के अर्थ से मतलब नहीं है, इसलिए “weqrww” को भी हम छह लंबाई वाला मान्य शब्द मानते हैं।

परिकलन के लिए हमें केवल गुणन का नियम जानना है। उपयोग के लिए कुल 26 भिन्न अक्षर हैं। इसलिए पहले स्थान पर हम 26 अक्षरों में से कोई एक रख सकते हैं। दूसरे स्थान पर भी हम 26 अक्षरों में से कोई एक रख सकते हैं, क्योंकि हमने यह शर्त नहीं रखी कि अक्षर दोहराए नहीं जा सकते। इस प्रकार प्रत्येक स्थान पर हम 26 अक्षरों में से चुनते हैं और गुणन के नियम से क्रमचयों की कुल संख्या 266 = 30,89,15,776 है। केवल 26 अक्षरों के हिसाब से यह काफ़ी बड़ी संख्या है।

n अवयवों वाले समुच्चय M से k अवयवों का पुनरावृत्ति सहित क्रमचय, प्रत्येक ऐसा क्रमित k-टपल है, जिसके अवयव समुच्चय M से हैं और प्रत्येक अवयव k-टपल में k बार तक आ सकता है। इसलिए यदि समुच्चय M = {1, 2, 3} है, तो ये सभी 4 अवयवों वाले मान्य पुनरावृत्ति सहित क्रमचय हैं: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3)। ऐसे पुनरावृत्ति सहित क्रमचयों की संख्या है:

nk.

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

  1. यदि अंक दोहराए जा सकते हैं, तो अंकों {2, 4, 6, 8} से छह अंकों की कितनी संख्याएँ बनाई जा सकती हैं? बस सूत्र में मान रखते हैं: समुच्चय में 4 अवयव हैं और हम छह-छह अवयव चुनते हैं:

    46=4,096.

  2. कंप्यूटरों में सामान्यतः द्विआधारी संख्या पद्धति प्रयोग होती है, अर्थात् ऐसी पद्धति, जिसमें केवल अंक 0 और 1 होते हैं। इसमें नए मात्रक प्रयोग होते हैं। उदाहरण के लिए, एक बिट एक प्रकार का खाना है, जिसमें या तो शून्य रखा जाता है या एक। इससे बड़ा मात्रक बाइट (byte) है, जिसमें 8 बिट होते हैं। इसलिए 1 एक बिट है, जबकि 01110001 एक बाइट है। एक बाइट को 8 बिटों से भरने के कितने भिन्न तरीके हैं?

    हम समुच्चय {0, 1} से, अर्थात् दो अवयवों में से, चुनते हैं। हम k = 8 आकार का k-टपल चुनते हैं, इसलिए सभी तरीकों की संख्या है:

    28=256.

  3. पिछले उदाहरण से हम जानते हैं कि एक बाइट 256 तक भिन्न मानों में अंतर कर सकता है। 4 बाइट भरने के कितने तरीके हैं?

    चार बाइट में 4 · 8 = 32 बिट होते हैं और हम अब भी 2 अवयवों वाले समुच्चय से चुनते हैं। अतः परिणाम है:

    232=4,29,49,67,296.

    हम देखते हैं कि केवल चार बाइट 429 करोड़ से अधिक मानों में अंतर कर सकते हैं। अंदाज़ा लगाने के लिए: आज के कंप्यूटरों में सैकड़ों गीगाबाइट या सीधे टेराबाइट वाली डिस्क होती हैं। एक टेराबाइट में 10,00,00,00,00,000 बाइट होते हैं, अर्थात् 80,00,00,00,00,000 बिट। इस प्रकार एक टेराबाइट की डिस्क पर 280,00,00,00,00,000 तक भिन्न मान रखे जा सकते हैं।

    टिप्पणी: आजकल किलोबाइट (मेगाबाइट आदि) के अर्थ को लेकर थोड़ा भ्रम है। तकनीकी कारणों से एक किलोबाइट में 1,000 बाइट नहीं होते थे, जैसा अन्य मात्रकों में होता है (एक किलोग्राम एक हज़ार ग्राम के बराबर होता है)। एक किलोबाइट 210 बाइट, अर्थात् 1,024 बाइट के बराबर था। एक मेगाबाइट 220 बाइट था, या 210 किलोबाइट।

    इसलिए आजकल हम दो प्रकार के संकेतन में अंतर करते हैं: 1 kB (किलोबाइट पढ़ते हैं) 1,000 बाइट है और 1 KiB (किबिबाइट पढ़ते हैं) 210 = 1,024 बाइट है।

  4. एक और उदाहरण पासवर्ड की सुरक्षा पर अलग लेख में है।

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