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

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

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

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

उदाहरण

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

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

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

$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 के इस समुच्चय को क्रमबद्ध करने के तरीके। इसके बाद, उन n -k लोगों को आदेश दें जिन्हें बाहर ही फ़ाइल लाइन में रहना चाहिए ताकि बाद में वे समय में में प्रवेश कर सकें, जब बाकी लोग चले जाएँ। वहाँ (एन - के) हैं! ऐसा करने के तरीके. किन्तु अब हमने n लोगों के पूरे समूह को आदेश दिया है, कुछ ऐसा जो n में किया जा सकता है! तौर विधि । इसलिए दोनों पक्ष n लोगों को आदेश देने के विधि की संख्या गिनते हैं। विभाजन से सुप्रसिद्ध सूत्र प्राप्त होता है ${\tbinom {n}{k}}$.

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

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

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

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

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

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

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

अंत में, एग्नर और ज़िग्लर द्वारा प्रस्तुत केली के सूत्र का चौथा प्रमाण डबल काउंटिंग (प्रमाण तकनीक)#पेड़ों की गिनती है। इस प्रमाण में, पिटमैन निर्देशित किनारों के अनुक्रमों पर विचार करता है जिन्हें एन-नोड खाली ग्राफ़ में जोड़ा जा सकता है ताकि इससे एकल जड़ वाला पेड़ बनाया जा सके, और ऐसे अनुक्रमों की संख्या को दो अलग-अलग विधि से गिना जा सके। पेड़, पेड़ के लिए जड़ और पेड़ में किनारों के लिए क्रम चुनकर इस प्रकार का अनुक्रम कैसे प्राप्त किया जाए, यह दिखाकर, वह दिखाता है कि टी हैं_nएन! इस प्रकार के संभावित अनुक्रम. और उन विधि की संख्या गिनकर, जिनमें आंशिक अनुक्रम को किनारे से बढ़ाया जा सकता है, वह दर्शाता है कि 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.