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

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

उदाहरण

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

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

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

डबल काउंटिंग पद्धति का एक उदाहरण उन तरीकों की संख्या को गिनता है जिनसे एक समिति बनाई जा सकती है $n$ लोग, किसी भी संख्या में लोगों को (उनमें से शून्य भी) समिति का हिस्सा बनने की अनुमति देते हैं। अर्थात्, एक उपसमुच्चय की संख्या की गणना करता है जो एक $n$-तत्व सेट हो सकता है। समिति बनाने का एक तरीका यह है कि प्रत्येक व्यक्ति को यह चुनने के लिए कहा जाए कि वह इसमें शामिल हो या नहीं। प्रत्येक व्यक्ति के पास दो विकल्प होते हैं - हाँ या नहीं - और ये विकल्प अन्य लोगों से स्वतंत्र होते हैं। इसलिए हैं $2\times 2\times \cdots 2=2^{n}$ संभावनाएं। वैकल्पिक रूप से, कोई यह देख सकता है कि समिति का आकार 0 और के बीच कुछ संख्या होनी चाहिए $n$. प्रत्येक संभव आकार के लिए $k$, तरीकों की संख्या जिसमें एक समिति $k$ से लोग बन सकते हैं $n$ लोग द्विपद गुणांक है

$${n \choose k}.$$

इसलिए संभावित समितियों की कुल संख्या द्विपद गुणांकों का योग है $k=0,1,2,\dots ,n$. दो व्यंजकों की बराबरी करने से सर्वसमिका (गणित) मिलती है

$$\sum _{k=0}^{n}{n \choose k}=2^{n},$$

द्विपद प्रमेय का एक विशेष मामला। अधिक सामान्य पहचान को साबित करने के लिए एक समान दोहरी गणना पद्धति का उपयोग किया जा सकता है

$$\sum _{k=d}^{n}{n \choose k}{k \choose d}=2^{n-d}{n \choose d}$$

हाथ मिलाना लेम्मा

Main article: Handshaking lemma

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

दोहरी गणना करके इसे सिद्ध करने के लिए, मान लीजिए $d(v)$ शीर्ष की डिग्री हो $v$. ग्राफ़ में वर्टेक्स-एज घटनाओं की संख्या को दो अलग-अलग तरीकों से गिना जा सकता है: वर्टिकल की डिग्री का योग करके, या हर किनारे के लिए दो इंसीडेंस की गिनती करके। इसलिए

$$\sum _{v}d(v)=2e$$

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

पेड़ों की गिनती

केली के सूत्र का तात्पर्य है कि वहाँ है 1 = 2^{2 − 2} दो सिरों पर पेड़, 3 = 3^{3 − 2} तीन सिरों पर पेड़, और 16 = 4^{4 − 2} चार सिरों पर पेड़।

जड़ वाले जंगल में एक निर्देशित किनारा जोड़ना

संख्या क्या है $T_{n}$ विभिन्न वृक्षों (ग्राफ सिद्धांत) के एक सेट से बनाया जा सकता है $n$ अलग शिखर? केली का सूत्र उत्तर देता है $T_{n}=n^{n-2}$. Aigner & Ziegler (1998) इस तथ्य के चार प्रमाणों की सूची बनाएं; वे चौथे के बारे में लिखते हैं, जिम पिटमैन के कारण एक डबल काउंटिंग प्रूफ, कि यह उन सभी में सबसे सुंदर है।

पिटमैन का प्रमाण दो अलग-अलग तरीकों से निर्देशित किनारों के विभिन्न अनुक्रमों की संख्या की गणना करता है जिन्हें एक खाली ग्राफ में जोड़ा जा सकता है $n$ इससे एक जड़दार वृक्ष बनता है। निर्देशित किनारे जड़ से दूर इंगित करते हैं। इस तरह का क्रम बनाने का एक तरीका यह है कि इनमें से किसी एक से शुरुआत की जाए $T_{n}$ संभव है जड़ से उखाड़े गए पेड़, इनमें से किसी एक को चुनें $n$ शीर्षों को रूट के रूप में चुनें, और इनमें से किसी एक को चुनें $(n-1)!$ संभावित अनुक्रम जिसमें इसे जोड़ना है $n-1$ (निर्देशित) किनारों। इसलिए, इस तरह से बनने वाले अनुक्रमों की कुल संख्या है $T_{n}n(n-1)!=T_{n}n!$.

इन किनारे अनुक्रमों को गिनने का एक अन्य तरीका किनारों को एक-एक करके एक खाली ग्राफ़ में जोड़ने पर विचार करना है, और प्रत्येक चरण पर उपलब्ध विकल्पों की संख्या की गणना करना है। अगर किसी ने एक संग्रह जोड़ा है $n-k$ किनारों को पहले से ही, ताकि इन किनारों द्वारा गठित ग्राफ एक जड़ वाला Tree_(graph_theory)#Forest with $k$ पेड़, हैं $n(k-1)$ जोड़ने के लिए अगले किनारे के लिए विकल्प: इसका शुरुआती शीर्ष इनमें से कोई भी हो सकता है $n$ ग्राफ के शीर्ष, और इसका अंतिम शीर्ष इनमें से कोई भी हो सकता है $k-1$ शुरुआती शीर्ष वाले पेड़ की जड़ के अलावा अन्य जड़ें। इसलिए, यदि कोई एक साथ पहले चरण, दूसरे चरण, आदि से विकल्पों की संख्या को गुणा करता है, तो विकल्पों की कुल संख्या है

$$\prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.$$

किनारों के अनुक्रमों की संख्या के लिए इन दो सूत्रों की तुलना केली के सूत्र में होती है:

$$\displaystyle T_{n}n!=n^{n-2}n!$$

और

$$\displaystyle T_{n}=n^{n-2}.$$

जैसा कि एग्नर और ज़िगलर वर्णन करते हैं, जड़ वाले जंगलों की संख्या की गणना करने के लिए सूत्र और प्रमाण को सामान्यीकृत किया जा सकता है $k$ पेड़, किसी के लिए $k$.

यह भी देखें

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

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

संबंधित विषय

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

संदर्भ

• 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.