बायजेक्टिव प्रमाण

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

मूल उदाहरण

द्विपद गुणांकों की सममिति को सिद्ध करना

द्विपद गुणांक की समरूपता बताती है कि

${n \choose k}={n \choose n-k}.$

इसका मतलब है कि बिल्कुल उतने ही संयोजन हैं k आकार के एक सेट में चीजें n के संयोजन हैं n − k आकार के एक सेट में चीजेंn.

एक विशेषण प्रमाण

प्रमाण के मुख्य विचार को एक साधारण उदाहरण से समझा जा सकता है: चयन करना k के समूह में से बच्चों को आइसक्रीम कोन से पुरस्कृत किया जाएगा n बच्चों पर ठीक वैसा ही प्रभाव पड़ता है जैसा इसके बजाय चुनने पर होता है n − k बच्चों को आइसक्रीम कोन देने से मना किया जाए।

अधिक संक्षेप में और आम तौर पर, बराबर होने का दावा करने वाली दो मात्राएँ आकार के सबसेट की गणना करती हैं k और n − k, क्रमशः, किसी का n-तत्व सेट S. होने देना A सभी का समुच्चय हो k-तत्व का सबसेट S, सेट A का आकार है ${\tbinom {n}{k}}.$ होने देना B सभी का समुच्चय हो n−k के सबसेट S, समुच्चय B का आकार है ${\tbinom {n}{n-k}}$. दो सेटों के बीच एक साधारण आपत्ति है A और B: यह प्रत्येक को जोड़ता है k-तत्व सबसेट (अर्थात, का एक सदस्य A) इसके पूरक (सेट सिद्धांत) के साथ, जिसमें ठीक शेष शामिल है n − k घटक S, और इसलिए इसका सदस्य है B. अधिक औपचारिक रूप से, इसे कार्यात्मक संकेतन का उपयोग करके लिखा जा सकता है, f : A → B द्वारा परिभाषित f(X) = X^c के लिए X कोई k-तत्व का सबसेट S और पूरक लिया गया S. यह दिखाने के लिए कि f एक आक्षेप है, पहले यह मान लें f(X₁) = f(X₂), यानी, X₁^c = X₂^c. प्रत्येक पक्ष का पूरक लें (में S), इस तथ्य का उपयोग करते हुए कि एक सेट के पूरक का पूरक मूल सेट है, प्राप्त करने के लिए X₁ = X₂. इससे पता चलता है कि f इंजेक्शन समारोह है | एक-से-एक। अब कोई भी लो n−k-तत्व का सबसेट S में B, कहना Y. में इसका पूरक है S, Y^c, एक है k-तत्व सबसेट, और इसलिए, का एक तत्व A. तब से f(Y^c) = (Y^c)^c = Y, f भी चालू है और इस प्रकार एक आक्षेप है। परिणाम अब आता है क्योंकि इन परिमित समुच्चयों के बीच एक आक्षेप के अस्तित्व से पता चलता है कि उनका आकार समान है, अर्थात, ${\tbinom {n}{k}}={\tbinom {n}{n-k}}$.