दोहराने वाले सेट से सभी संभावित अद्वितीय सबसेट की कुल संख्या की गणना कैसे करें?

Question

एक सेट ** एस को डुप्लिकेट तत्व युक्त, एस को एस के सभी संभावित सबसेट्स को कैसे निर्धारित किया जा सकता है, जहां प्रत्येक सबसेट अद्वितीय है।

उदाहरण के लिए, एस = {ए, बी, बी} कहें और के सभी को सभी सबसेट्स का सेट दें, फिर के = {{}, {ए}, {बी}, {ए, बी}, {बी , बी}, {ए, बी, बी}} और इसलिए | के | = 6.

एक और उदाहरण होगा यदि एस = {ए, ए, बी, बी}, फिर के = {{}, {ए}, {बी}, {ए, बी}, {ए, ए} , {बी, बी}, {ए, बी, बी}, {ए, ए, बी}, {ए, ए, बी, बी}} और इसके लिए | के | = 9

यह देखना आसान है कि अगर एस वास्तविक सेट है, तो केवल अद्वितीय तत्व हैं, तो | के | = 2^| एस |

इस मूल्य की गणना करने के लिए सूत्र क्या है | के | सभी सबसेट उत्पन्न किए बिना "सेट" एस (डुप्लिकेट के साथ) दिया गया है?

** तकनीकी रूप से एक सेट नहीं है।

Answer 1

सभी (आवृत्तियों + 1) का उत्पाद लें।

उदाहरण के लिए, में {ए, बी, बी}, जवाब (1 + 1) [बी एस की संख्या] = 6.

में है [के रूप में की संख्या] * (2 + 1) दूसरा उदाहरण, गिनती (ए) = 2 और गिनती (बी) = 2. इस प्रकार उत्तर (2 + 1) * (2 + 1) = 9

कारण यह है कि आप किसी भी को परिभाषित कर सकते हैं गणना के वेक्टर के रूप में सबसेट - {ए, बी, बी} के लिए, सबसेट को {ए = 0, बी = 0}, {ए = 0, बी = 1}, {0,2}, {1 के रूप में वर्णित किया जा सकता है , 0}, {1,1}, {1,2}।

गणना में प्रत्येक संख्या के लिए [] वहां (ऑब्जेक्ट + 1 की आवृत्तियों) संभावित मान हैं। (0..फ्रीक्वेंसी)

इसलिए, possiblities की कुल संख्या सभी (आवृत्तियों + 1) का उत्पाद है।

"सभी अद्वितीय" मामले को भी इस तरह समझाया जा सकता है - प्रत्येक ऑब्जेक्ट का एक अवसर होता है, इसलिए उत्तर (1 + 1)^| एस | = 2^| एस |

Answer 2

मैं तर्क दूंगा कि उचित समस्या में देखा जाने पर यह समस्या हल करने के लिए आसान है। आप तत्वों के क्रम के बारे में परवाह नहीं करते हैं, केवल तभी वे एक उप-समूह में दिखाई देते हैं।

सेट में प्रत्येक तत्व की संख्या की गणना करें। एक तत्व सेट {ए} के लिए, कितने सबसेट हैं? स्पष्ट रूप से केवल दो सेट हैं। अब मान लें कि हमने एक और तत्व जोड़ा है, बी, जो कि ए से अलग है, सेट {ए, बी} बनाने के लिए है। हम सभी सेटों की सूची को आसानी से बना सकते हैं। उन सभी सेटों को लें जिन्हें हमने केवल ए का उपयोग करके बनाया है, और शून्य या एक प्रतिलिपि में जोड़ें। असल में, हम सेट की संख्या को दोगुना करते हैं। स्पष्ट रूप से हम यह दिखाने के लिए प्रेरण का उपयोग कर सकते हैं कि एन विशिष्ट तत्वों के लिए, सेट की कुल संख्या केवल 2^एन है।

मान लीजिए कि कुछ तत्व कई बार प्रकट होते हैं? ए की इस तरह की प्रतियों पर विचार करें। इस प्रकार {ए, ए, ए}। आप कितने सबसेट बना सकते हैं? फिर, यह आसान है। हमारे पास 0, 1, 2, या 3 की प्रतियां हो सकती हैं, इसलिए ऑब्जेक्ट की कोई फर्क नहीं पड़ता है क्योंकि सबसेट की कुल संख्या 4 है।

सामान्य रूप से, तत्व ए की एन प्रतियों के लिए, हम एन + 1 संभावित सबसेट के साथ समाप्त हो जाएंगे। अब, बी की प्रतियों की कुछ संख्या, एम में जोड़कर इसका विस्तार करें। इसलिए हमारे पास बी की ए और एम प्रतियों की एन प्रतियां हैं। कितने कुल सबसेट हैं? हाँ, यह भी स्पष्ट लगता है। इसमें केवल ए के साथ हर संभव सबसेट के लिए (उनमें से एन + 1 थे) हम बी की 0 और एम प्रतियों के बीच जोड़ सकते हैं।

तो जब हमारे पास बी की ए और एम प्रतियां की प्रतियां होती हैं तो सबसेट की कुल संख्या सरल होती है। यह होना चाहिए (एन + 1) * (एम + 1)। दोबारा, हम यह दिखाने के लिए एक अपरिवर्तनीय तर्क का उपयोग कर सकते हैं कि सबसेट की कुल संख्या ऐसी शर्तों का उत्पाद है। प्रत्येक विशिष्ट तत्व के लिए प्रतिलिपि की कुल संख्या को केवल गिनें, 1 जोड़ें, और उत्पाद लें।

सेट {ए, बी, बी} के साथ क्या होता है देखें। हम सेट के लिए 2 * 3 = 6.

प्राप्त {ए, ए, बी, बी} पर हम पाते हैं 3 * 3 = 9.