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

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

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

कॉम्बिनेटरिक्स में किसी भी प्रकार के प्राथमिक प्रमाण को संदर्भित करने के लिए कॉम्बिनेटरियल प्रूफ़ शब्द का अधिक व्यापक रूप से उपयोग किया जा सकता है। हालाँकि, जैसे Glass (2003) अपनी समीक्षा में लिखते हैं Benjamin & Quinn (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}.

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

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

स्टैनली स्पष्ट रूप से विशेषण और दोहरी गणना प्रमाणों के बीच अंतर नहीं करता है, और दोनों प्रकार के उदाहरण देता है, लेकिन दो प्रकार के संयोजन प्रमाण के बीच का अंतर इसके द्वारा प्रदान किए गए उदाहरण में देखा जा सकता है। Aigner & Ziegler (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.