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

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

मूल उदाहरण

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

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

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

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

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

प्रमाण के मुख्य विचार को एक साधारण उदाहरण से समझा जा सकता है: चयन करना 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) लेंl इस तथ्य का उपयोग करते हुए कि एक समुच्चय के पूरक का पूरक मूल समुच्चय है, प्राप्त करने के लिए X₁ = X₂. इससे पता चलता है कि f एक-से-एक है। अब B में S का कोई n−k -तत्व उपसमुच्चय लें, Y कहते हैं। में इसका पूरक है S, Y^c, एक है k-तत्व उपसमुच्चय, और इसलिए, A का एक अवयव हैl चूँकि f(Y^c) = (Y^c)^c = Y, f भी आच्छादक है और इस प्रकार एक आक्षेप है। परिणाम अब आता है क्योंकि इन परिमित समुच्चयों के बीच एक आक्षेप के अस्तित्व से पता चलता है कि उनका आकार समान है, अर्थात, ${\tbinom {n}{k}}={\tbinom {n}{n-k}}$.