दोहरी गणना (तकनीक प्रमाण): Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Type of proof technique}} साहचर्य में, डबल काउंटिंग, जिसे दो तरह से काउंटि...")
 
No edit summary
 
(9 intermediate revisions by 5 users not shown)
Line 1: Line 1:
{{Short description|Type of proof technique}}
[[साहचर्य]] में, दोहरी गणना, जिसे दो तरह से गणना भी कहा जाता है, यह दिखाने के लिए एक [[संयोजन प्रमाण]] तकनीक है कि दो भाव समान हैं, यह प्रदर्शित करके कि वे एक [[सेट (गणित)|सम्मुच्चय (गणित)]] के आकार की गिनती के दो तरीके हैं। इस तकनीक में, जिसे वैन लिंट और विल्सन (2001) "कॉम्बिनेटरिक्स में सबसे महत्वपूर्ण उपकरणों में से एक" कहते हैं। {{sfn|van Lint|Wilson|2001}} एक सम्मुच्चय के आकार के लिए दो अलग-अलग अभिव्यक्तियों के लिए अग्रणी दो दृष्टिकोणों से एक [[परिमित सेट|परिमित सम्मुच्चय]] का वर्णन करता है। चूँकि दोनों भाव एक ही सम्मुच्चय के आकार के बराबर हैं, वे एक दूसरे के बराबर हैं।
[[साहचर्य]] में, डबल काउंटिंग, जिसे दो तरह से काउंटिंग भी कहा जाता है, यह दिखाने के लिए एक [[संयोजन प्रमाण]] तकनीक है कि दो भाव समान हैं, यह प्रदर्शित करके कि वे एक [[सेट (गणित)]] के आकार की गिनती के दो तरीके हैं। इस तकनीक में, जो {{harvtxt|van Lint|Wilson|2001}} कॉम्बिनेटरिक्स में सबसे महत्वपूर्ण उपकरणों में से एक को कॉल करें,{{sfn|van Lint|Wilson|2001}} एक सेट के आकार के लिए दो अलग-अलग अभिव्यक्तियों के लिए अग्रणी दो दृष्टिकोणों से एक [[परिमित सेट]] का वर्णन करता है। चूँकि दोनों भाव एक ही सेट के आकार के बराबर हैं, वे एक दूसरे के बराबर हैं।


== उदाहरण ==
== उदाहरण ==


=== गुणन ([[प्राकृतिक संख्या]]ओं का) आवागमन ===
=== गुणन ([[प्राकृतिक संख्या]]ओं का) आवागमन ===
यह दोहरी गिनती का एक सरल उदाहरण है, जिसका उपयोग अक्सर छोटे बच्चों को गुणन पढ़ाते समय किया जाता है। इस संदर्भ में, प्राकृतिक संख्याओं के गुणन को बार-बार जोड़ के रूप में पेश किया जाता है, और फिर एक आयताकार ग्रिड में व्यवस्थित कई वस्तुओं को दो अलग-अलग तरीकों से गिनकर कम्यूटेटिव_प्रॉपर्टी के रूप में दिखाया जाता है। मान लीजिए ग्रिड है <math>n</math> पंक्तियाँ और <math>m</math> कॉलम। हम पहले योग द्वारा वस्तुओं की गणना करते हैं <math>n</math> की पंक्तियों <math>m</math> आइटम प्रत्येक, फिर दूसरी बार संक्षेप में <math>m</math> के कॉलम <math>n</math> आइटम प्रत्येक, इस प्रकार दिखा रहा है कि, इन विशेष मूल्यों के लिए <math>n</math> और <math>m</math>, <math>n \times m = m \times n</math>.
यह दोहरी गिनती का एक सरल उदाहरण है, जिसका उपयोग प्रायः छोटे बच्चों को गुणन पढ़ाते समय किया जाता है। इस संदर्भ में, प्राकृतिक संख्याओं के गुणन को बार-बार जोड़ के रूप में प्रस्तुत किया जाता है, और फिर एक आयताकार संजाल में व्यवस्थित कई वस्तुओं को दो अलग-अलग तरीकों से गिनकर क्रम विनिमय के रूप में दिखाया जाता है। मान लीजिए <math>n</math> पंक्तियाँ और <math>m</math> कॉलम संजाल है। हम पहले प्रत्येक वस्तु की n पंक्तियों को समेटकर वस्तु की गिनती करते हैं, फिर दूसरी बार n वस्तु के m कॉलम को समेटने से, इस प्रकार यह दिखाते हैं कि, इन विशेष मूल्यों के लिए <math>n</math> और <math>m</math>, <math>n \times m = m \times n</math> है।


===समितियों का गठन===
===समितियों का गठन===
डबल काउंटिंग पद्धति का एक उदाहरण उन तरीकों की संख्या को गिनता है जिनसे एक समिति बनाई जा सकती है <math>n</math> लोग, किसी भी संख्या में लोगों को (उनमें से शून्य भी) समिति का हिस्सा बनने की अनुमति देते हैं। अर्थात्, एक उपसमुच्चय की संख्या की गणना करता है जो एक <math>n</math>-तत्व सेट हो सकता है। समिति बनाने का एक तरीका यह है कि प्रत्येक व्यक्ति को यह चुनने के लिए कहा जाए कि वह इसमें शामिल हो या नहीं। प्रत्येक व्यक्ति के पास दो विकल्प होते हैं - हाँ या नहीं - और ये विकल्प अन्य लोगों से स्वतंत्र होते हैं। इसलिए हैं <math>2\times 2\times \cdots 2 = 2^n</math> संभावनाएं। वैकल्पिक रूप से, कोई यह देख सकता है कि समिति का आकार 0 और के बीच कुछ संख्या होनी चाहिए <math>n</math>. प्रत्येक संभव आकार के लिए <math>k</math>, तरीकों की संख्या जिसमें एक समिति <math>k</math> से लोग बन सकते हैं <math>n</math> लोग [[द्विपद गुणांक]] है
दोहरी गणना पद्धति का एक उदाहरण उन तरीकों की संख्या को गिनता है जहाँ <math>n</math> लोग से एक समिति बनाई जा सकती है, किसी भी संख्या में लोगों को (उनमें से शून्य भी) समिति का हिस्सा बनने की अनुमति देते हैं। अर्थात्, एक उपसमुच्चय की संख्या की गणना करता है जो एक <math>n</math>-तत्व सम्मुच्चय हो सकता है। समिति बनाने का एक तरीका यह है कि प्रत्येक व्यक्ति को यह चुनने के लिए कहा जाए कि वह इसमें सम्मिलित हो या नहीं। प्रत्येक व्यक्ति के पास दो विकल्प होते हैं - हाँ या नहीं - और ये विकल्प अन्य लोगों से स्वतंत्र होते हैं। इसलिए वहां <math>2\times 2\times \cdots 2 = 2^n</math> संभावनाएं हैं। वैकल्पिक रूप से, कोई यह देख सकता है कि समिति का आकार 0 और के बीच कुछ संख्या <math>n</math> होनी चाहिए। प्रत्येक संभव आकार <math>k</math> के लिए, तरीकों की संख्या जिसमें एक समिति <math>k</math> से लोग बन सकते हैं <math>n</math> लोग [[द्विपद गुणांक]] है
<math display=block>{n \choose k}.</math>
<math display=block>{n \choose k}.</math>
इसलिए संभावित समितियों की कुल संख्या द्विपद गुणांकों का योग है <math>k=0,1,2,\dots,n</math>. दो व्यंजकों की बराबरी करने से सर्वसमिका (गणित) मिलती है
इसलिए संभावित समितियों की कुल संख्या द्विपद गुणांकों का योग <math>k=0,1,2,\dots,n</math> है। दो व्यंजकों की बराबरी करने से सर्वसमिका (गणित) मिलती है
<math display=block>\sum_{k=0}^n {n \choose k} = 2^n,</math>
<math display=block>\sum_{k=0}^n {n \choose k} = 2^n,</math>
[[द्विपद प्रमेय]] का एक विशेष मामला। अधिक सामान्य पहचान को साबित करने के लिए एक समान दोहरी गणना पद्धति का उपयोग किया जा सकता है<ref>{{harvnb|Garbano|Malerba|Lewinter|2003}}; {{harvnb|Klavžar|2006}}).</ref>
[[द्विपद प्रमेय]] की एक विशेष स्तिथि है। अधिक सामान्य अस्मिता को सिद्ध करने के लिए एक समान दोहरी गणना पद्धति का उपयोग किया जा सकता है<ref>{{harvnb|Garbano|Malerba|Lewinter|2003}}; {{harvnb|Klavžar|2006}}).</ref>
<math display=block>\sum_{k=d}^n {n\choose k}{k\choose d} = 2^{n-d}{n\choose d}</math>
<math display=block>\sum_{k=d}^n {n\choose k}{k\choose d} = 2^{n-d}{n\choose d}</math>




=== हाथ मिलाना लेम्मा ===
=== हैंडशेकिंग सिद्धांत ===
{{main|Handshaking lemma}}
{{main|हैंडशेकिंग सिद्धांत}}
एक अन्य प्रमेय जो आमतौर पर एक डबल काउंटिंग तर्क के साथ सिद्ध होता है, कहता है कि प्रत्येक [[अप्रत्यक्ष ग्राफ]] में विषम [[डिग्री (ग्राफ सिद्धांत)]] के वर्टेक्स (ग्राफ सिद्धांत) की एक समान संख्या होती है। अर्थात्, विषम संख्या वाले घटना [[ग्राफ (असतत गणित)]] वाले शीर्षों की संख्या सम होनी चाहिए। अधिक बोलचाल की भाषा में, लोगों की एक पार्टी में जिनमें से कुछ हाथ मिलाते हैं, एक सम संख्या में लोगों ने विषम संख्या में अन्य लोगों के हाथ मिलाए होंगे; इस कारण से, परिणाम को [[ हाथ मिलाना लेम्मा ]] के रूप में जाना जाता है।


दोहरी गणना करके इसे सिद्ध करने के लिए, मान लीजिए <math>d(v)</math> शीर्ष की डिग्री हो <math>v</math>. ग्राफ़ में वर्टेक्स-एज घटनाओं की संख्या को दो अलग-अलग तरीकों से गिना जा सकता है: वर्टिकल की डिग्री का योग करके, या हर किनारे के लिए दो इंसीडेंस की गिनती करके। इसलिए
एक अन्य प्रमेय जो सामान्यतः एक दोहरी गणना तर्क के साथ सिद्ध होता है, यह कहता है कि प्रत्येक [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष लेखाचित्र]] में विषम [[डिग्री (ग्राफ सिद्धांत)|घात (लेखाचित्र सिद्धांत)]] के कोणबिंदु (लेखाचित्र सिद्धांत) की एक समान संख्या होती है। अर्थात्, विषम संख्या वाले घटना [[ग्राफ (असतत गणित)|लेखाचित्र (असतत गणित)]] वाले शीर्षों की संख्या सम होनी चाहिए। अधिक बोलचाल की भाषा में, लोगों के एक समारोह में जिनमें से कुछ हाथ मिलाते हैं, एक सम संख्या में लोगों ने विषम संख्या में अन्य लोगों के हाथ मिलाए होंगे; इस कारण से, परिणाम को [[ हाथ मिलाना लेम्मा |हैंडशेकिंग सिद्धांत]] के रूप में जाना जाता है।
 
दोहरी गणना करके इसे सिद्ध करने के लिए, मान लीजिए <math>d(v)</math> शीर्ष की घात <math>v</math> है। लेखाचित्ऱ में कोणबिंदु-छोर घटनाओं की संख्या को दो अलग-अलग तरीकों से जैसे अनुलंब की घात का योग करके, या हर किनारे के लिए दो घटनाओं की गिनती करके गिना जा सकता है। इसलिए
<math display=block>\sum_v d(v) = 2e</math>
<math display=block>\sum_v d(v) = 2e</math>
कहाँ <math>e</math> किनारों की संख्या है। इसलिए शीर्षों की घातों का योग एक [[सम संख्या]] है, जो तब नहीं हो सकता जब शीर्षों की विषम संख्या विषम कोटि वाली हो। यह तथ्य, इस प्रमाण के साथ, कोनिग्सबर्ग के सात पुलों पर [[लियोनहार्ड यूलर]] के 1736 के पेपर में दिखाई देता है जिसने सबसे पहले [[ग्राफ सिद्धांत]] का अध्ययन शुरू किया था।
जहाँ <math>e</math> किनारों की संख्या है। इसलिए शीर्षों की घातों का योग एक [[सम संख्या]] है, जो तब नहीं हो सकता जब शीर्षों की विषम संख्या विषम कोटि वाली हो। यह तथ्य, इस प्रमाण के साथ, कोनिग्सबर्ग के सात पुलों पर [[लियोनहार्ड यूलर]] के 1736 के लेख में दिखाई देता है जिसने सबसे पहले [[ग्राफ सिद्धांत|लेखाचित्र सिद्धांत]] का अध्ययन प्रारम्भ किया था।


=== पेड़ों की गिनती ===
=== तरू की गिनती ===
[[File:Cayley's formula 2-4.svg|thumb|240px|केली के सूत्र का तात्पर्य है कि वहाँ है {{nowrap|1 {{=}} 2<sup>2 − 2</sup>}} दो सिरों पर पेड़, {{nowrap|3 {{=}} 3<sup>3 − 2</sup>}} तीन सिरों पर पेड़, और {{nowrap|16 {{=}} 4<sup>4 − 2</sup>}} चार सिरों पर पेड़।]]
[[File:Cayley's formula 2-4.svg|thumb|240px|केली के सूत्र का तात्पर्य है कि वहाँ है {{nowrap|1 {{=}} 2<sup>2 − 2</sup>}} दो सिरों पर ट्री, {{nowrap|3 {{=}} 3<sup>3 − 2</sup>}} तीन सिरों पर ट्री, और {{nowrap|16 {{=}} 4<sup>4 − 2</sup>}} चार सिरों पर ट्री।]]
[[File:Graph.tree. Cayley's formula.png|thumb|जड़ वाले जंगल में एक निर्देशित किनारा जोड़ना]]संख्या क्या है <math>T_n</math> विभिन्न वृक्षों (ग्राफ सिद्धांत) के एक सेट से बनाया जा सकता है <math>n</math> अलग शिखर? केली का सूत्र उत्तर देता है <math>T_n=n^{n-2}</math>. {{harvtxt|Aigner|Ziegler|1998}} इस तथ्य के चार प्रमाणों की सूची बनाएं; वे चौथे के बारे में लिखते हैं, जिम पिटमैन के कारण एक डबल काउंटिंग प्रूफ, कि यह उन सभी में सबसे सुंदर है।{{sfn|Aigner|Ziegler|1998}}
[[File:Graph.tree. Cayley's formula.png|thumb|जड़ वाले फारेस्ट में एक निर्देशित किनारा जोड़ना]]अलग-अलग ट्रीों की संख्या <math>T_n</math> क्या है जो <math>n</math> अलग-अलग शीर्षों के सम्मुच्चय से बनाई जा सकती है? केली का सूत्र <math>T_n=n^{n-2}</math> उत्तर देता है।{{sfn|Aigner|Ziegler|1998}} {{harvtxt|एग्नर|ज़ेग्लर|1998}} इस तथ्य के चार प्रमाणों की सूची बनाएं; वे चौथे के बारे में लिखते हैं, जिम पिटमैन के कारण एक दोहरी गणना प्रमाण, कि यह उन सभी में सबसे सुंदर है। {{sfn|Aigner|Ziegler|1998}}


पिटमैन का प्रमाण दो अलग-अलग तरीकों से निर्देशित किनारों के विभिन्न अनुक्रमों की संख्या की गणना करता है जिन्हें एक [[खाली ग्राफ]] में जोड़ा जा सकता है <math>n</math> इससे एक जड़दार वृक्ष बनता है। निर्देशित किनारे जड़ से दूर इंगित करते हैं। इस तरह का क्रम बनाने का एक तरीका यह है कि इनमें से किसी एक से शुरुआत की जाए <math>T_n</math> संभव है जड़ से उखाड़े गए पेड़, इनमें से किसी एक को चुनें <math>n</math> शीर्षों को रूट के रूप में चुनें, और इनमें से किसी एक को चुनें <math>(n-1)!</math> संभावित अनुक्रम जिसमें इसे जोड़ना है <math>n-1</math> (निर्देशित) किनारों। इसलिए, इस तरह से बनने वाले अनुक्रमों की कुल संख्या है <math>T_n n(n-1)! = T_n n!</math>.{{sfn|Aigner|Ziegler|1998}}
पिटमैन का प्रमाण दो अलग-अलग तरीकों से निर्देशित किनारों के विभिन्न अनुक्रमों की संख्या की गणना करता है जिन्हें एक [[खाली ग्राफ|खाली लेखाचित्र]] <math>n</math> में जोड़ा जा सकता है इससे एक तरू बनता है। निर्देशित किनारे जड़ से दूर इंगित करते हैं। इस तरह का क्रम बनाने का एक तरीका यह है कि इनमें से किसी एक <math>T_n</math>जड़ से उखाड़े गए ट्री से प्रारम्भ की जाए, इनमें से किसी एक <math>n</math> को शीर्षों को वर्गमूल के रूप में चुनें, और इनमें से किसी एक <math>(n-1)!</math> को संभावित अनुक्रम चुनें जिसमें इसे <math>n-1</math> किनारों को जोड़ना है। इसलिए, इस तरह से बनने वाले अनुक्रमों की कुल संख्या <math>T_n n(n-1)! = T_n n!</math> है। {{sfn|Aigner|Ziegler|1998}}


इन किनारे अनुक्रमों को गिनने का एक अन्य तरीका किनारों को एक-एक करके एक खाली ग्राफ़ में जोड़ने पर विचार करना है, और प्रत्येक चरण पर उपलब्ध विकल्पों की संख्या की गणना करना है। अगर किसी ने एक संग्रह जोड़ा है <math>n-k</math> किनारों को पहले से ही, ताकि इन किनारों द्वारा गठित ग्राफ एक जड़ वाला Tree_(graph_theory)#Forest with <math>k</math> पेड़, हैं <math>n(k-1)</math> जोड़ने के लिए अगले किनारे के लिए विकल्प: इसका शुरुआती शीर्ष इनमें से कोई भी हो सकता है <math>n</math> ग्राफ के शीर्ष, और इसका अंतिम शीर्ष इनमें से कोई भी हो सकता है <math>k-1</math> शुरुआती शीर्ष वाले पेड़ की जड़ के अलावा अन्य जड़ें। इसलिए, यदि कोई एक साथ पहले चरण, दूसरे चरण, आदि से विकल्पों की संख्या को गुणा करता है, तो विकल्पों की कुल संख्या है
इन किनारे अनुक्रमों को गिनने का एक अन्य तरीका किनारों को एक-एक करके एक खाली लेखाचित्ऱ में जोड़ने पर विचार करना है, और प्रत्येक चरण पर उपलब्ध विकल्पों की संख्या की गणना करना है। यदि किसी ने पहले से ही एन-के किनारों का एक संग्रह जोड़ा है, ताकि इन किनारों द्वारा गठित लेखाचित्र के ट्री के साथ एक जड़ वाला फारेस्ट हो, तो अगले किनारे को जोड़ने के लिए <math>n-k</math> विकल्प हैं: इसका प्रारंभिक शीर्ष लेखाचित्ऱ के <math>n</math> शीर्षों में से कोई एक हो सकता है, और इसका अंतिम शीर्ष प्रारंभिक शीर्ष वाले ट्री की जड़ के अलावा <math>k-1</math> जड़ों में से कोई भी हो सकता है। इसलिए, यदि कोई एक साथ पहले चरण, दूसरे चरण, आदि से विकल्पों की संख्या को गुणा करता है, तो विकल्पों की कुल संख्या है
<math display=block>\prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!.</math>
<math display=block>\prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!.</math>
किनारों के अनुक्रमों की संख्या के लिए इन दो सूत्रों की तुलना केली के सूत्र में होती है:
किनारों के अनुक्रमों की संख्या के लिए इन दो सूत्रों की तुलना केली के सूत्र में होती है:
Line 36: Line 36:
और
और
<math display=block>\displaystyle T_n=n^{n-2}.</math>
<math display=block>\displaystyle T_n=n^{n-2}.</math>
जैसा कि एग्नर और ज़िगलर वर्णन करते हैं, जड़ वाले जंगलों की संख्या की गणना करने के लिए सूत्र और प्रमाण को सामान्यीकृत किया जा सकता है <math>k</math> पेड़, किसी के लिए {{nowrap|<math>k</math>.{{sfn|Aigner|Ziegler|1998}}}}
किसी भी k के लिए, <math>k</math> वृक्षों वाले जड़ वाले वनों की संख्या की गणना करने के लिए सूत्र और प्रमाण को सामान्यीकृत किया जा सकता है। {{nowrap|{{sfn|Aigner|Ziegler|1998}}}}


== यह भी देखें ==
== यह भी देखें ==


=== अतिरिक्त उदाहरण ===
=== अतिरिक्त उदाहरण ===
* वैंडरमोंड की पहचान, द्विपद गुणांक के योग पर एक और पहचान जो दोहरी गिनती से सिद्ध की जा सकती है।{{sfn|Joshi|2015}}
* वैंडरमोंड की अस्मिता, द्विपद गुणांक के योग पर एक और अस्मिता जो दोहरी गिनती से सिद्ध की जा सकती है। {{sfn|Joshi|2015}}
* [[वर्ग पिरामिड संख्या]]। पहले के योग के बीच समानता <math>n</math> [[वर्ग संख्या]]ओं और एक घन बहुपद को संख्याओं के त्रिगुणों की दोहरी गणना करके दिखाया जा सकता है <math>x</math>, <math>y</math>, और <math>z</math> कहाँ <math>z</math> अन्य दो संख्याओं में से किसी एक से बड़ा है।
* [[वर्ग पिरामिड संख्या]]. पहले के योग के बीच समानता <math>n</math> [[वर्ग संख्या]]ओं और एक घन बहुपद को संख्याओं <math>x</math>, <math>y</math>, और <math>z</math> के त्रिगुणों की दोहरी गणना करके दिखाया जा सकता है जहाँ <math>z</math> अन्य दो संख्याओं में से किसी एक से बड़ा है।
* लुबेल-यामामोटो-मेशलकिन असमानता। लुबेल का सेट परिवारों पर इस परिणाम का प्रमाण क्रम[[परिवर्तन]] पर एक दोहरी गिनती का तर्क है, जिसका उपयोग समानता के बजाय [[असमानता (गणित)]] को साबित करने के लिए किया जाता है।
* लुबेल-यामामोटो-मेशलकिन असमानता. लुबेल का सम्मुच्चय वर्ग पर इस परिणाम का प्रमाण क्रम[[परिवर्तन]] पर एक दोहरी गिनती का तर्क है, जिसका उपयोग समानता के स्थान पर [[असमानता (गणित)]] को सिद्ध करने के लिए किया जाता है।
* एर्डोस-को-राडो प्रमेय, समुच्चयों के प्रतिच्छेदी परिवारों पर एक ऊपरी सीमा, ग्युला ओ. एच. कटोना द्वारा दोहरी गिनती असमानता का उपयोग करके सिद्ध किया गया।{{sfn|Aigner|Ziegler|1998}}
* एर्डोस-को-राडो प्रमेय, समुच्चयों के प्रतिच्छेदी वर्गों पर एक ऊपरी सीमा, ग्युला ओ. एच. कटोना द्वारा दोहरी गिनती असमानता का उपयोग करके सिद्ध किया गया।{{sfn|Aigner|Ziegler|1998}}
* फर्मेट की छोटी प्रमेय के प्रमाण। दोहरी गणना द्वारा विभाज्यता प्रमाण: किसी भी [[अभाज्य संख्या]] के लिए <math>p</math> और प्राकृतिक संख्या <math>A</math>, वहाँ हैं <math>A^p-A</math> लंबाई-<math>p</math> एक से अधिक शब्द <math>A</math>-प्रतीक वर्णमाला जिसमें दो या दो से अधिक भिन्न चिह्न हों। इन्हें के सेट में बांटा जा सकता है <math>p</math> ऐसे शब्द जो वृत्ताकार पारियों द्वारा एक दूसरे में रूपांतरित हो सकते हैं; इन सेटों को नेकलेस (कॉम्बिनेटरिक्स) कहा जाता है। इसलिए, <math>A^p-A=p\cdot{}</math>(हारों की संख्या) और से विभाज्य है <math>p</math>.{{sfn|Joshi|2015}}
* फर्मेट की छोटी प्रमेय के प्रमाण. दोहरी गणना द्वारा विभाज्यता प्रमाण: किसी भी [[अभाज्य संख्या]] के लिए <math>p</math> और प्राकृतिक संख्या <math>A</math>, जहाँ <math>A^p-A</math> लंबाई-<math>p</math> एक से अधिक शब्द <math>A</math>-प्रतीक वर्णमाला जिसमें दो या दो से अधिक भिन्न चिह्न हैं। इन्हें <math>p</math> के सम्मुच्चय में बांटा जा सकता है, ऐसे शब्द जो वृत्ताकार पारियों द्वारा एक दूसरे में रूपांतरित हो सकते हैं; इन सम्मुच्चयों को नेकलेस (साहचर्य) कहा जाता है। इसलिए, <math>A^p-A=p\cdot{}</math>(हारों की संख्या) और <math>p</math> से विभाज्य है। {{sfn|Joshi|2015}}
* [[द्विघात पारस्परिकता के प्रमाण]]। [[गोथोल्ड आइज़ेंस्टीन]] द्वारा एक सबूत एक और महत्वपूर्ण [[संख्या सिद्धांत]] प्राप्त करता है | एक त्रिभुज में जाली बिंदुओं की दोहरी गिनती से संख्या-सैद्धांतिक तथ्य।
* [[द्विघात पारस्परिकता के प्रमाण]]. [[गोथोल्ड आइज़ेंस्टीन]] द्वारा एक प्रमाण एक और महत्वपूर्ण [[संख्या सिद्धांत]] प्राप्त करता है | एक त्रिभुज में जाली बिंदुओं की दोहरी गिनती से संख्या-सैद्धांतिक तथ्य है।


=== संबंधित विषय ===
=== संबंधित विषय ===
* [[विशेषण प्रमाण]]। जहां दोहरी गिनती में एक सेट को दो तरीकों से गिनना शामिल है, विशेषण प्रमाण में दो सेटों को एक तरह से गिनना शामिल है, यह दिखाते हुए कि उनके तत्व एक-से-एक के अनुरूप हैं।
* [[विशेषण प्रमाण]]. जहां दोहरी गिनती में एक सम्मुच्चय को दो तरीकों से गिनना सम्मिलित है, विशेषण प्रमाण में दो सम्मुच्चयों को एक तरह से गिनना सम्मिलित है, यह दिखाते हुए कि उनके तत्व एक-से-एक के अनुरूप हैं।
* समावेश-बहिष्करण सिद्धांत, सेट के [[संघ (सेट सिद्धांत)]] के आकार के लिए एक सूत्र, जो एक ही संघ के लिए एक और सूत्र के साथ मिलकर, दोहरी गिनती तर्क के भाग के रूप में उपयोग किया जा सकता है।
* समावेश-बहिष्करण सिद्धांत, सम्मुच्चय के [[संघ (सेट सिद्धांत)|संघ (सम्मुच्चय सिद्धांत)]] के आकार के लिए एक सूत्र, जो एक ही संघ के लिए एक और सूत्र के साथ मिलकर, दोहरी गिनती तर्क के भाग के रूप में उपयोग किया जा सकता है।


==टिप्पणियाँ==
==टिप्पणियाँ==
Line 70: Line 70:
*{{citation | last = Klavžar| first = Sandi | doi = 10.1016/j.disc.2005.10.036 | issue = 22 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] | pages = 2964–2967 | title = Counting hypercubes in hypercubes | volume = 306 | year = 2006| doi-access = free }}.
*{{citation | last = Klavžar| first = Sandi | doi = 10.1016/j.disc.2005.10.036 | issue = 22 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] | pages = 2964–2967 | title = Counting hypercubes in hypercubes | volume = 306 | year = 2006| doi-access = free }}.
*{{citation | last1 = van Lint| first1 = Jacobus H. | last2 = Wilson| first2 = Richard M. | title = A Course in Combinatorics | page = 4 | publisher = Cambridge University Press | year = 2001 | isbn = 978-0-521-00601-9}}.
*{{citation | last1 = van Lint| first1 = Jacobus H. | last2 = Wilson| first2 = Richard M. | title = A Course in Combinatorics | page = 4 | publisher = Cambridge University Press | year = 2001 | isbn = 978-0-521-00601-9}}.
[[Category: गणनात्मक कॉम्बिनेटरिक्स]] [[Category: प्रमाण युक्त लेख]] [[Category: गणितीय प्रमाण]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Created On 05/05/2023]]
[[Category:Created On 05/05/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:गणनात्मक कॉम्बिनेटरिक्स]]
[[Category:गणितीय प्रमाण]]
[[Category:प्रमाण युक्त लेख]]

Latest revision as of 17:10, 3 November 2023

साहचर्य में, दोहरी गणना, जिसे दो तरह से गणना भी कहा जाता है, यह दिखाने के लिए एक संयोजन प्रमाण तकनीक है कि दो भाव समान हैं, यह प्रदर्शित करके कि वे एक सम्मुच्चय (गणित) के आकार की गिनती के दो तरीके हैं। इस तकनीक में, जिसे वैन लिंट और विल्सन (2001) "कॉम्बिनेटरिक्स में सबसे महत्वपूर्ण उपकरणों में से एक" कहते हैं। [1] एक सम्मुच्चय के आकार के लिए दो अलग-अलग अभिव्यक्तियों के लिए अग्रणी दो दृष्टिकोणों से एक परिमित सम्मुच्चय का वर्णन करता है। चूँकि दोनों भाव एक ही सम्मुच्चय के आकार के बराबर हैं, वे एक दूसरे के बराबर हैं।

उदाहरण

गुणन (प्राकृतिक संख्याओं का) आवागमन

यह दोहरी गिनती का एक सरल उदाहरण है, जिसका उपयोग प्रायः छोटे बच्चों को गुणन पढ़ाते समय किया जाता है। इस संदर्भ में, प्राकृतिक संख्याओं के गुणन को बार-बार जोड़ के रूप में प्रस्तुत किया जाता है, और फिर एक आयताकार संजाल में व्यवस्थित कई वस्तुओं को दो अलग-अलग तरीकों से गिनकर क्रम विनिमय के रूप में दिखाया जाता है। मान लीजिए पंक्तियाँ और कॉलम संजाल है। हम पहले प्रत्येक वस्तु की n पंक्तियों को समेटकर वस्तु की गिनती करते हैं, फिर दूसरी बार n वस्तु के m कॉलम को समेटने से, इस प्रकार यह दिखाते हैं कि, इन विशेष मूल्यों के लिए और , है।

समितियों का गठन

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

इसलिए संभावित समितियों की कुल संख्या द्विपद गुणांकों का योग है। दो व्यंजकों की बराबरी करने से सर्वसमिका (गणित) मिलती है
द्विपद प्रमेय की एक विशेष स्तिथि है। अधिक सामान्य अस्मिता को सिद्ध करने के लिए एक समान दोहरी गणना पद्धति का उपयोग किया जा सकता है[2]


हैंडशेकिंग सिद्धांत

Main article: हैंडशेकिंग सिद्धांत

एक अन्य प्रमेय जो सामान्यतः एक दोहरी गणना तर्क के साथ सिद्ध होता है, यह कहता है कि प्रत्येक अप्रत्यक्ष लेखाचित्र में विषम घात (लेखाचित्र सिद्धांत) के कोणबिंदु (लेखाचित्र सिद्धांत) की एक समान संख्या होती है। अर्थात्, विषम संख्या वाले घटना लेखाचित्र (असतत गणित) वाले शीर्षों की संख्या सम होनी चाहिए। अधिक बोलचाल की भाषा में, लोगों के एक समारोह में जिनमें से कुछ हाथ मिलाते हैं, एक सम संख्या में लोगों ने विषम संख्या में अन्य लोगों के हाथ मिलाए होंगे; इस कारण से, परिणाम को हैंडशेकिंग सिद्धांत के रूप में जाना जाता है।

दोहरी गणना करके इसे सिद्ध करने के लिए, मान लीजिए शीर्ष की घात है। लेखाचित्ऱ में कोणबिंदु-छोर घटनाओं की संख्या को दो अलग-अलग तरीकों से जैसे अनुलंब की घात का योग करके, या हर किनारे के लिए दो घटनाओं की गिनती करके गिना जा सकता है। इसलिए

जहाँ किनारों की संख्या है। इसलिए शीर्षों की घातों का योग एक सम संख्या है, जो तब नहीं हो सकता जब शीर्षों की विषम संख्या विषम कोटि वाली हो। यह तथ्य, इस प्रमाण के साथ, कोनिग्सबर्ग के सात पुलों पर लियोनहार्ड यूलर के 1736 के लेख में दिखाई देता है जिसने सबसे पहले लेखाचित्र सिद्धांत का अध्ययन प्रारम्भ किया था।

तरू की गिनती

केली के सूत्र का तात्पर्य है कि वहाँ है 1 = 22 − 2 दो सिरों पर ट्री, 3 = 33 − 2 तीन सिरों पर ट्री, और 16 = 44 − 2 चार सिरों पर ट्री।
जड़ वाले फारेस्ट में एक निर्देशित किनारा जोड़ना

अलग-अलग ट्रीों की संख्या क्या है जो अलग-अलग शीर्षों के सम्मुच्चय से बनाई जा सकती है? केली का सूत्र उत्तर देता है।[3] एग्नर & ज़ेग्लर (1998) इस तथ्य के चार प्रमाणों की सूची बनाएं; वे चौथे के बारे में लिखते हैं, जिम पिटमैन के कारण एक दोहरी गणना प्रमाण, कि यह उन सभी में सबसे सुंदर है। [3]

पिटमैन का प्रमाण दो अलग-अलग तरीकों से निर्देशित किनारों के विभिन्न अनुक्रमों की संख्या की गणना करता है जिन्हें एक खाली लेखाचित्र में जोड़ा जा सकता है इससे एक तरू बनता है। निर्देशित किनारे जड़ से दूर इंगित करते हैं। इस तरह का क्रम बनाने का एक तरीका यह है कि इनमें से किसी एक जड़ से उखाड़े गए ट्री से प्रारम्भ की जाए, इनमें से किसी एक को शीर्षों को वर्गमूल के रूप में चुनें, और इनमें से किसी एक को संभावित अनुक्रम चुनें जिसमें इसे किनारों को जोड़ना है। इसलिए, इस तरह से बनने वाले अनुक्रमों की कुल संख्या है। [3]

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

किनारों के अनुक्रमों की संख्या के लिए इन दो सूत्रों की तुलना केली के सूत्र में होती है:
और
किसी भी k के लिए, वृक्षों वाले जड़ वाले वनों की संख्या की गणना करने के लिए सूत्र और प्रमाण को सामान्यीकृत किया जा सकता है। [3]

यह भी देखें

अतिरिक्त उदाहरण

  • वैंडरमोंड की अस्मिता, द्विपद गुणांक के योग पर एक और अस्मिता जो दोहरी गिनती से सिद्ध की जा सकती है। [4]
  • वर्ग पिरामिड संख्या. पहले के योग के बीच समानता वर्ग संख्याओं और एक घन बहुपद को संख्याओं , , और के त्रिगुणों की दोहरी गणना करके दिखाया जा सकता है जहाँ अन्य दो संख्याओं में से किसी एक से बड़ा है।
  • लुबेल-यामामोटो-मेशलकिन असमानता. लुबेल का सम्मुच्चय वर्ग पर इस परिणाम का प्रमाण क्रमपरिवर्तन पर एक दोहरी गिनती का तर्क है, जिसका उपयोग समानता के स्थान पर असमानता (गणित) को सिद्ध करने के लिए किया जाता है।
  • एर्डोस-को-राडो प्रमेय, समुच्चयों के प्रतिच्छेदी वर्गों पर एक ऊपरी सीमा, ग्युला ओ. एच. कटोना द्वारा दोहरी गिनती असमानता का उपयोग करके सिद्ध किया गया।[3]
  • फर्मेट की छोटी प्रमेय के प्रमाण. दोहरी गणना द्वारा विभाज्यता प्रमाण: किसी भी अभाज्य संख्या के लिए और प्राकृतिक संख्या , जहाँ लंबाई- एक से अधिक शब्द -प्रतीक वर्णमाला जिसमें दो या दो से अधिक भिन्न चिह्न हैं। इन्हें के सम्मुच्चय में बांटा जा सकता है, ऐसे शब्द जो वृत्ताकार पारियों द्वारा एक दूसरे में रूपांतरित हो सकते हैं; इन सम्मुच्चयों को नेकलेस (साहचर्य) कहा जाता है। इसलिए, (हारों की संख्या) और से विभाज्य है। [4]
  • द्विघात पारस्परिकता के प्रमाण. गोथोल्ड आइज़ेंस्टीन द्वारा एक प्रमाण एक और महत्वपूर्ण संख्या सिद्धांत प्राप्त करता है | एक त्रिभुज में जाली बिंदुओं की दोहरी गिनती से संख्या-सैद्धांतिक तथ्य है।

संबंधित विषय

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

टिप्पणियाँ

  1. ↑ van Lint & Wilson 2001.
  2. ↑ Garbano, Malerba & Lewinter 2003; Klavžar 2006).
  3. ↑ 3.0 3.1 3.2 3.3 3.4 Aigner & Ziegler 1998.
  4. ↑ 4.0 4.1 Joshi 2015.


संदर्भ

  • Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Springer-Verlag. Double counting is described as a general principle on page 126; Pitman's double counting proof of Cayley's formula is on pp. 145–146; Katona's double counting inequality for the Erdős–Ko–Rado theorem is pp. 214–215.
  • Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF), Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128–140. Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press.
  • Garbano, M. L.; Malerba, J. F.; Lewinter, M. (2003), "Hypercubes and Pascal's triangle: a tale of two proofs", Mathematics Magazine, 76 (3): 216–217, doi:10.2307/3219324, JSTOR 3219324.
  • Joshi, Mark (2015), "Double Counting", Proof Patterns, Springer International Publishing, pp. 11–17, doi:10.1007/978-3-319-16250-8_2
  • Klavžar, Sandi (2006), "Counting hypercubes in hypercubes", Discrete Mathematics, 306 (22): 2964–2967, doi:10.1016/j.disc.2005.10.036.
  • van Lint, Jacobus H.; Wilson, Richard M. (2001), A Course in Combinatorics, Cambridge University Press, p. 4, ISBN 978-0-521-00601-9.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=दोहरी_गणना_(तकनीक_प्रमाण)&oldid=272652’