संयुक्त प्रमाण

गणित में, संयोजनात्मक प्रमाण का प्रयोग प्रायः दो प्रकार के गणितीय प्रमाण में से किसी एक के लिए किया जाता है:

• दोहरी गिनती (प्रमाण तकनीक) द्वारा प्रमाण दिया गया है। जो कि पहचान में अलग-अलग अभिव्यक्ति प्राप्त करने के लिए दो अलग-अलग विधियो से कुछ सावधानीपूर्वक चुने गए समुच्चय के अवयव की संख्या की गणना करके संयुक्त पहचान (गणित) सिद्ध की जाती है। चूँकि वे अभिव्यक्तियाँ समान वस्तुओं को गिनती हैं, इसलिए उन्हें एक-दूसरे के समान होना चाहिए और इस प्रकार पहचान स्थापित होती है।
• वस्तुपरक प्रमाण दिया गया है। जो की दो समुच्चय में उनके मध्य आक्षेप अर्थात एक-से- पत्राचार प्रदर्शित करके सदस्यों की समान संख्या दिखाई जाती है।

इस प्रकार से कॉम्बिनेटरिक्स में किसी भी प्रकार के प्राथमिक प्रमाण को संदर्भित करने के लिए कॉम्बिनेटरियल प्रमाणों शब्द का अधिक व्यापक रूप से उपयोग किया जा सकता है। चूंकि जैसे ग्लास (2003) अपनी समीक्षा में लिखते हैं बेंजामिन & क्विन (2003) (कॉम्बिनेटरी प्रमाणों के बारे में किताब), ये दो सरल तकनीकें कॉम्बिनेटरिक्स और संख्या सिद्धांत में कई प्रमेयों को प्रमाणित करने के लिए पर्याप्त हैं।

उदाहरण

n -अवयव समुच्चय के k-संयोजन (अर्थात, आकार के उपसमुच्चय ) की संख्या ${\tbinom {n}{k}}$ के लिए प्रसिद्ध सूत्र के लिए एक आदर्श दोहरी गिनती प्रमाण है:

${\binom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}}.$

इस प्रकार से प्रत्यक्ष विशेषण प्रमाण संभव नहीं है: क्योंकि पहचान का दाहिना भाग एक भिन्न है, इसलिए स्पष्ट रूप से इसके द्वारा गिना जाने वाला कोई समुच्चय नहीं है (यह देखने के लिए भी कुछ विचार करना पड़ता है कि हर सदैव अंश को समान रूप से विभाजित करता है)। चूंकि इसका अंश आकार n, n - 1, ..., n - k + 1 के k परिमित समुच्चय के कार्टेशियन उत्पाद की गणना करता है, जबकि इसका हर k-अवयव समुच्चय के क्रमपरिवर्तन की गणना करता है (वह समुच्चय जो स्पष्ट रूप से हर द्वारा गिना जाता है) एक अन्य कार्टेशियन उत्पाद k परिमित समुच्चय होगा; यदि वांछित हो तो कोई स्पष्ट आक्षेप द्वारा उस समुच्चय में क्रमपरिवर्तन को मैप कर सकता है)। अब S को बिना दोहराव के हमारे n-अवयव समुच्चय से चुने गए k अवयव के अनुक्रमों का समुच्चय के रूप में है । एक ओर, अंश $n(n-1)\cdots (n-k+1)$, के संगत कार्तीय गुणनफल के साथ S का सरल विक्षेपण होता है और दूसरी ओर, k के जोड़े के समुच्चय C से एक विक्षेपण होता है। इस प्रकार से बढ़ते क्रम में C के अवयव को लेकर k से S का संयोजन और क्रमपरिवर्तन σ , और फिर S का एक अवयव प्राप्त करने के लिए इस अनुक्रम को σ द्वारा क्रमपरिवर्तित किया जाता है। किन्तु गिनती की दो विधि समीकरण देते हैं

$n(n-1)\cdots (n-k+1)={\binom {n}{k}}k!,$

और k से विभाजन के द्वारा! यह ${\tbinom {n}{k}}$ बताए गए सूत्र की ओर ले जाता है. समान्यत: यदि गिनती के सूत्र में विभाजन सम्मिलित होता है, तो समान दोहरी गिनती का तर्क (यदि यह उपस्तिथ है) पहचान का सबसे सीधा संयोजन प्रमाण देता है, किन्तु दोहरी गिनती के तर्क उन स्थितियों तक सीमित नहीं हैं जहां सूत्र इस रूप का है।

यहां उसी पहचान का सरल, अधिक अनौपचारिक संयोजनात्मक प्रमाण दिया गया है:

${\binom {n}{k}}k!(n-k)!=n!$

मान लीजिए कि n लोग किसी संग्रहालय में प्रवेश करना चाहते हैं, किन्तु संग्रहालय में केवल k लोगों के लिए जगह है। पहले चुनें कि n लोगों में से किन k लोगों को अंदर जाने की अनुमति दी जाएगी। और परिभाषा के अनुसार ऐसा करने के लिए ${\tbinom {n}{k}}$ विधि हैं। अब k लोगों को एक एकल-फ़ाइल लाइन में क्रमित करें जिससे वे एक समय में एक का भुगतान कर सकें। जहाँ k हैं! आकार k के इस समुच्चय को क्रमबद्ध करने के विधि है । इसके अतिरिक्त , ${\tbinom {n}{k}}$ लोगों को एक एकल-फ़ाइल लाइन में बाहर रहने का आदेश दें जिससे अतिरिक्त में वे एक समय में एक में प्रवेश कर सकें, क्योंकि अन्य लोग चले जाते हैं। जहाँ ${\tbinom {n}{k}}$ हैं! ऐसा करने के विधि है जो किन्तु अब हमने n लोगों के पूरे समूह को आदेश दिया है, कुछ ऐसा जो n में किया जा सकता है! इन विधियों में है । इसलिए दोनों पक्ष n लोगों को आदेश देने के विधि की संख्या गिनते हैं। विभाजन से ${\tbinom {n}{k}}$ का सुप्रसिद्ध सूत्र प्राप्त होता है

संयुक्त प्रमाण का लाभ

स्टैनली (1997) एक संयोजन गणना समस्या का एक उदाहरण देता है (k उपसमुच्चय S₁, S₂, ... S_k, के अनुक्रमों की संख्या की गणना करते हुए, जिसे n वस्तुओं के एक समुच्चय से बनाया जा सकता है जैसे कि सभी उपसमुच्चय का प्रतिच्छेदन रिक्त है) इसके समाधान के लिए दो अलग-अलग प्रमाणों के साथ पहला प्रमाण, जो संयोजनात्मक नहीं है, गणितीय प्रेरण और जनरेटिंग फलन का उपयोग करके यह पता लगाता है कि इस प्रकार के अनुक्रमों की संख्या (2^k −1)ⁿ है। दूसरा प्रमाण इस अवलोकन पर आधारित है कि समुच्चय {1, 2, ..., k}, के 2^k −1 उचित उपसमुच्चय हैं, और समुच्चय {1, 2, ..., k}, से (2^k −1)ⁿ फलन हैं।, {1, 2, ..., n} के उचित उपसमुच्चय के वर्ग में है । जिससे गिने जाने वाले अनुक्रमों को इन कार्यों के साथ एक-से-एक पत्राचार में रखा जा सकता है, जहां सबसमुच्चय के दिए गए अनुक्रम से बना फलन प्रत्येक अवयव i को समुच्चय {j | i ∈ S_j} है .

इस प्रकार से स्टैनली लिखते हैं, “उपरोक्त संयोजन प्रमाण न केवल हमारे पिछले प्रमाण की तुलना में अधिक छोटा है, किन्तु यह सरल उत्तर के कारण को पूर्ण रूप से पारदर्शी बनाता है। प्रायः ऐसा होता है, की जैसा कि यहां व्यक्त किया गया है कि दिमाग में आने वाला प्रथम प्रमाण श्रमसाध्य और सुरुचिपूर्ण हो जाता है, किन्तु अंतिम उत्तर सरल संयोजन प्रमाण का सुझाव देता है। गैर-संयोजन संबंधी प्रमाणों की तुलना में उनके निरंतर अधिक लालित्य और उनके द्वारा वर्णित संरचनाओं में अधिक अंतर्दृष्टि प्रदान करने के कारण है स्टेनली ने सामान्य सिद्धांत तैयार किया है कि संयोजन प्रमाणों को अन्य प्रमाणों पर प्राथमिकता दी जानी चाहिए, और संयोजन प्रमाण खोजने की कई समस्याओं को अभ्यास के रूप में सूचीबद्ध किया गया है। अन्य माध्यमों से सत्य माने जाने वाले गणितीय तथ्यों के लिए आवश्यक है ।

विशेषण और दोहरी गणना प्रमाण के मध्य अंतर

इस प्रकार से स्टैनली स्पष्ट रूप से विशेषण और दोहरी गणना प्रमाणों के मध्य अंतर नहीं करता है और दोनों प्रकार के उदाहरण देता है, किन्तु दो प्रकार के संयोजन प्रमाण के मध्य का अंतर एग्नेर और ज़िगलर (1998) द्वारा प्रदान किए गए उदाहरण में देखा जा सकता है, जो केली के सूत्र के प्रमाण हैं। जहाँ n^{n − 2} अलग-अलग ट्रीस (ग्राफ़ सिद्धांत) हैं जिन्हें n नोड्स के दिए गए समुच्चय से बनाया जा सकता है। एग्नेर & ज़ेग्लर (1998) ने इस प्रमेय के चार प्रमाण सूचीबद्ध किए हैं, जिनमें से प्रथम विशेषण है और अंतिम दोहरी गिनती वाला तर्क है। किन्तु वे पांचवें विशेषण प्रमाण का भी उल्लेख करते हैं किन्तु विवरण का वर्णन नहीं करते हैं।

इस सूत्र का विशेषण प्रमाण खोजने का सबसे स्वाभाविक विधि n-नोड ट्रीस और वस्तुओं के कुछ संग्रह के मध्य एक आक्षेप खोजना होगा जिसमें n^{n − 2} सदस्य हैं, जैसे 1 से लेकर प्रत्येक की सीमा में n - 2 मानों का क्रम है । इस प्रकार से से n प्रत्येक ट्रीस के प्रुफ़र अनुक्रम का उपयोग करके ऐसी आपत्ति प्राप्त की जा सकती है। किसी भी ट्रीस को विशिष्ट रूप से प्रमाण अनुक्रम में एनकोड किया जा सकता है, और किसी भी प्रमाण अनुक्रम को विशिष्ट रूप से ट्रीस में डिकोड किया जा सकता है; ये दोनों परिणाम मिलकर केली के सूत्र का एक विशेषण प्रमाण प्रदान करते हैं।

इस प्रकार से वैकल्पिक विशेषण प्रमाण, जो एग्नेर और ज़िग्लर द्वारा दिया गया है और जिसका श्रेय आंद्रे जोयल को दिया गया है, इसमें एक ओर दो निर्दिष्ट नोड्स वाले n-नोड ट्रीस (जो एक दूसरे के समान हो सकते हैं) और दूसरी ओर के मध्य एक आपत्ति सम्मिलित है। दूसरी ओर, n -नोड निर्देशित ग्राफ वर्गीकरण यदि T_nn-नोड ट्रीस हैं, तो दो निर्दिष्ट नोड्स वाले n²T_n ट्रीस भी हैं। और वर्गीकरण को उसके प्रत्येक नोड के लिए है उस नोड से बाहर की ओर विस्तारित किनारे के समापन बिंदु को निर्दिष्ट करके निर्धारित किया जा सकता है; एकल किनारे के समापन बिंदु (स्वयं-लूप की अनुमति) के लिए कोई संभावित विकल्प नहीं हैं और इसलिए संभावित वर्गीकरण हैं। दो लेबल वाले नोड्स और छद्म वर्गीकरण वाले ट्रीस के मध्य आक्षेप खोजकर जोयल का प्रमाण T_n = n^{n − 2} दर्शाया जाता है.

चूंकि अंत में, एग्नेर और ज़िग्लर द्वारा प्रस्तुत केली के सूत्र का चौथा प्रमाण जिम पिटमैन के कारण दोहरा गणना प्रमाण है। इस प्रमाण में पिटमैन निर्देशित किनारों के अनुक्रमों पर विचार करता है जिन्हें n-नोड रिक्त ग्राफ में जोड़ा जा सकता है जिससे इससे एकल रूट वाला ट्री बनाया जा सकता है और ऐसे अनुक्रमों की संख्या को दो अलग-अलग विधियों से गिना जा सकता है । एक ट्री , ट्री के लिए एक रूट और ट्री में किनारों के लिए क्रम चुनकर इस प्रकार का अनुक्रम कैसे प्राप्त किया जाए, यह दर्शाता है कि T_nn हैं! इस प्रकार के संभावित अनुक्रम और उन विधियों की संख्या गिनकर, जिनमें एक आंशिक अनुक्रम को एक किनारे से बढ़ाया जा सकता है, वह दर्शाता है कि n^{n − 2}n हैं! संभावित अनुक्रम किनारे अनुक्रमों के एक ही समुच्चय के आकार के लिए इन दो अलग-अलग सूत्रों को समान करना है, और n के सामान्य कारक को निरस्त करना! केली के सूत्र की ओर ले जाता है।

संबंधित अवधारणाएँ

• संयोजक सिद्धांत में उपयोग की जाने वाली दोहरी गणना और आक्षेप के सिद्धांतों को कॉम्बिनेटरियल सिद्धांतों के उच्च वर्ग के उदाहरण के रूप में देखा जा सकता है, जिसमें पिजेनहोल सिद्धांत जैसे अन्य विचार भी सम्मिलित किये गए हैं।
• संयुक्त रूप से किसी पहचान को प्रमाणित करने को संख्याओं को समुच्चय द्वारा प्रतिस्थापित करके पहचान में अधिक संरचना जोड़ने के रूप में देखा जा सकता है; इसी प्रकार से वर्गीकरण श्रेणियों द्वारा समुच्चय का प्रतिस्थापन है।

संदर्भ

• Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Springer-Verlag, pp. 141–146, ISBN 3-540-40460-0.

• Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, Dolciani Mathematical Expositions, vol. 27, Mathematical Association of America, ISBN 978-0-88385-333-7.

• Glass, Darren (2003), Read This: Proofs that Really Count, Mathematical Association of America.

• Stanley, Richard P. (1997), Enumerative Combinatorics, Volume I, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, pp. 11–12, ISBN 0-521-55309-1.