Method of distinguished element
गणनात्मक संयोजन के गणितीय क्षेत्र में, पहचान कभी-कभी उन तर्कों द्वारा स्थापित की जाती हैं जो एक समूह के एक "विशिष्ट तत्व" को अलग करने पर निर्भर करते हैं। परिभाषा मान लीजिए कि सेट के सबसेट का एक परिवार है और सेट का एक विशिष्ट तत्व है। फिर मान लीजिए कि एक विधेय है जो एक उपसमुच्चय से संबंधित है। उपसमुच्चय के समूह के रूप में दर्शाएँ जिसमें से सही है और उपसमुच्चय का समूह है जिसमें से गलत है, फिर और असंबद्ध सेट हैं, इसलिए योग की विधि से, कार्डिनलिटीज योगात्मक हैं इस प्रकार विशिष्ट तत्व एक विधेय के अनुसार अपघटन की अनुमति देता है जो एक विभाजन और विजय एल्गोरिथ्म का एक सरल रूप है। संयोजन विज्ञान में, यह पुनरावृत्ति संबंधों के निर्माण की अनुमति देता है। उदाहरण अगले खंड में हैं। उदाहरण द्विपद गुणांक एक आकार-एन समुच्चय के आकार-के उपसमुच्चय की संख्या है। एक बुनियादी पहचान-जिसका एक परिणाम यह है कि द्विपद गुणांक ठीक वही संख्याएँ हैं जो पास्कल के त्रिभुज में दिखाई देती हैं-बताती है किः प्रमाणः एक आकार-(n + 1) समूह में, एक विशिष्ट तत्व चुनें। सभी आकार-के उपसमुच्चय के समूह में शामिल हैंः (1) सभी आकार-के उपसमुच्चय जिनमें विशिष्ट तत्व होता है, और (2) सभी आकार-के उपसमुच्चय जिनमें विशिष्ट तत्व नहीं होता है। यदि किसी आकार-(एन + 1) समुच्चय के आकार-के उपसमुच्चय में विशिष्ट तत्व होता है, तो इसके अन्य के-1 तत्वों को हमारे आकार-(एन + 1) समुच्चय के अन्य एन तत्वों में से चुना जाता है। इसलिए उन्हें चुनने के तरीकों की संख्या है। यदि एक आकार-के उपसमुच्चय में विशिष्ट तत्व नहीं होता है, तो इसके सभी के सदस्यों को अन्य एन "गैर-विशिष्ट" तत्वों में से चुना जाता है। इसलिए उन्हें चुनने के तरीकों की संख्या है। किसी भी आकार-एन समूह के उपसमुच्चय की संख्या 2n है। प्रमाणः हम गणितीय प्रेरण का उपयोग करते हैं। प्रेरण का आधार n = 0 के मामले में इस प्रस्ताव का सत्य है। खाली समूह में 0 सदस्य और 1 उपसमुच्चय होता है, और 20 = 1 होता है। इंडक्शन हाइपोथिसिस n मामले में प्रस्ताव है; हम इसका उपयोग n + 1 मामले को साबित करने के लिए करते हैं। साइज-(एन + 1) सेट में, एक विशिष्ट तत्व चुनें। प्रत्येक उपसमुच्चय में या तो विशिष्ट तत्व होता है या नहीं होता है। यदि किसी उपसमुच्चय में विशिष्ट तत्व होता है, तो उसके शेष तत्वों को अन्य एन तत्वों में से चुना जाता है। प्रेरण परिकल्पना के अनुसार, ऐसा करने के तरीकों की संख्या 2n है। यदि किसी उपसमुच्चय में विशिष्ट तत्व नहीं है, तो यह सभी गैर-विशिष्ट तत्वों के समूह का एक उपसमुच्चय है। प्रेरण परिकल्पना के अनुसार, ऐसे उपसमुच्चय की संख्या 2n है। अंत में, हमारे आकार-(n + 1) समूह के उपसमुच्चय की पूरी सूची में 2n + 2n = 2n + 1 तत्व होते हैं। मान लीजिए कि Bn n वीं घंटी संख्या है, यानी, n सदस्यों के एक समूह के विभाजन की संख्या। मान लीजिए कि Cn उस समूह के सभी विभाजनों के बीच "भागों" (या "खंडों", जैसा कि संयोजनवादी अक्सर उन्हें कहते हैं) की कुल संख्या है। उदाहरण के लिए, आकार-3 समुच्चय {a, b, c} के विभाजन इस प्रकार लिखे जा सकते हैंः हम 5 विभाजन देखते हैं, जिसमें 10 खंड होते हैं, इसलिए B3 = 5 और C3 = 10। एक पहचान बताती हैः प्रमाणः एक आकार-(एन + 1) सेट में, एक विशिष्ट तत्व चुनें। हमारे आकार-(एन + 1) समुच्चय के प्रत्येक विभाजन में, या तो विशिष्ट तत्व एक "सिंगलटन" है, अर्थात, केवल विशिष्ट तत्व वाला समुच्चय खंडों में से एक है, या विशिष्ट तत्व एक बड़े खंड से संबंधित है। यदि विशिष्ट तत्व एक सिंगलटन है, तो विशिष्ट तत्व को हटाने से सेट का एक विभाजन हो जाता है जिसमें n गैर-विशिष्ट तत्व होते हैं। ऐसा करने के बीएन तरीके हैं। यदि विशिष्ट तत्व एक बड़े ब्लॉक से संबंधित है, तो इसका विलोपन सेट के एक विभाजन में एक ब्लॉक छोड़ देता है जिसमें n गैर-विशिष्ट तत्व होते हैं। ऐसे सी. एन. ब्लॉक हैं। कॉम्बिनेटरियल सिद्धांत कॉम्बिनेटरियल प्रूफ संदर्भ कॉम्बिनेटरिक गणितीय सिद्धांत भी देखें।