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

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

उदाहरण

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

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

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

दोहरी गणना करके इसे सिद्ध करने के लिए, मान लीजिए $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}$ उत्तर देता है। एग्नर & ज़ेग्लर (1998) इस तथ्य के चार प्रमाणों की सूची बनाएं; वे चौथे के बारे में लिखते हैं, जिम पिटमैन के कारण एक दोहरी गणना प्रमाण, कि यह उन सभी में सबसे सुंदर है।

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

इन किनारे अनुक्रमों को गिनने का एक अन्य तरीका किनारों को एक-एक करके एक खाली लेखाचित्ऱ में जोड़ने पर विचार करना है, और प्रत्येक चरण पर उपलब्ध विकल्पों की संख्या की गणना करना है। यदि किसी ने पहले से ही एन-के किनारों का एक संग्रह जोड़ा है, ताकि इन किनारों द्वारा गठित लेखाचित्र के ट्री के साथ एक जड़ वाला फारेस्ट हो, तो अगले किनारे को जोड़ने के लिए $n-k$ विकल्प हैं: इसका प्रारंभिक शीर्ष लेखाचित्ऱ के $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.