संयोजन

This article is about the mathematics of selecting part of a collection. For other uses, see संयोजन (disambiguation).

"COMBIN" and "nCr" redirect here. For other uses, see Combin (disambiguation) and NCR (disambiguation).

गणित में, एक संयोजन एक सेट से वस्तुओं का चयन होता है जिसमें अलग-अलग सदस्य होते हैं, जैसे कि चयन का क्रम मायने नहीं रखता (क्रमपरिवर्तन के विपरीत)। उदाहरण के लिए, तीन फल दिए गए हैं, जैसे एक सेब, एक संतरा और एक नाशपाती, दो के तीन संयोजन हैं जिन्हें इस सेट से निकाला जा सकता है: एक सेब और एक नाशपाती; एक सेब और एक संतरा; या एक नाशपाती और एक संतरा। अधिक औपचारिक रूप से, एक के-एक सेट (गणित) एस का संयोजन एस के के विशिष्ट तत्वों का एक सबसेट है। इसलिए, दो संयोजन समान हैं यदि और केवल यदि प्रत्येक संयोजन में समान सदस्य हैं। (प्रत्येक सेट में सदस्यों की व्यवस्था कोई मायने नहीं रखती है।) यदि सेट में 'एन' तत्व हैं, तो 'के'-संयोजन की संख्या, द्वारा निरूपित $C(n,k)$ या $C_{k}^{n}$, द्विपद गुणांक के बराबर है

$${\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},$$

जिसे कारख़ाने का का उपयोग करके लिखा जा सकता है $\textstyle {\frac {n!}{k!(n-k)!}}$ जब कभी भी $k\leq n$, और कौन सा कब शून्य है $k>n$. यह सूत्र इस तथ्य से प्राप्त किया जा सकता है कि n सदस्यों के समुच्चय S के प्रत्येक k-संयोजन में है $k!$ क्रमपरिवर्तन तो $P_{k}^{n}=C_{k}^{n}\times k!$ या $C_{k}^{n}=P_{k}^{n}/k!$. समुच्चय S के सभी k-संयोजनों के समुच्चय को प्राय: निरूपित किया जाता है $\textstyle {\binom {S}{k}}$.

एक संयोजन n चीजों का एक संयोजन है जिसे एक बार में बिना दोहराव के k लिया जाता है। उन संयोजनों को संदर्भित करने के लिए जिनमें पुनरावृत्ति की अनुमति है, पुनरावृत्ति के साथ k-संयोजन, k-multiset, या के-चयन, अक्सर उपयोग किए जाते हैं। यदि, उपरोक्त उदाहरण में, किसी एक प्रकार के दो फलों का होना संभव था, तो 3 और 2-चयन होंगे: एक में दो सेब, एक में दो संतरे, और एक में दो नाशपाती।

यद्यपि संयोजनों की पूरी सूची लिखने के लिए तीन फलों का सेट काफी छोटा था, यह अव्यावहारिक हो जाता है क्योंकि सेट का आकार बढ़ जाता है। उदाहरण के लिए, एक हाथ (पोकर) को 52 कार्ड डेक (n = 52) से कार्ड के 5-संयोजन (k = 5) के रूप में वर्णित किया जा सकता है। हाथ के 5 कार्ड अलग-अलग हैं, और हाथ में कार्ड का क्रम मायने नहीं रखता। इस तरह के 2,598,960 संयोजन हैं, और यादृच्छिक रूप से किसी एक हाथ को खींचने की संभावना 1 / 2,598,960 है।

के-संयोजनों की संख्या

Main article: Binomial coefficient

File:Combinations without repetition; 5 choose 3.svg

5-तत्व सेट के 3-तत्व सबसेट

एन तत्वों के दिए गए सेट एस से के-संयोजनों की संख्या को अक्सर प्राथमिक संयोजक ग्रंथों में दर्शाया जाता है $C(n,k)$, या भिन्नरूप द्वारा जैसे $C_{k}^{n}$, ${}_{n}C_{k}$, ${}^{n}C_{k}$, $C_{n,k}$ या और भी $C_{n}^{k}$ (अंतिम रूप फ्रेंच, रोमानियाई, रूसी, चीनी में मानक है और पोलिश ग्रंथ). वही संख्या हालांकि कई अन्य गणितीय संदर्भों में होती है, जहां इसे द्वारा निरूपित किया जाता है ${\tbinom {n}{k}}$ (अक्सर n चुनें k के रूप में पढ़ा जाता है); विशेष रूप से यह द्विपद सूत्र में एक गुणांक के रूप में होता है, इसलिए इसका नाम 'द्विपद गुणांक' है। कोई परिभाषित कर सकता है ${\tbinom {n}{k}}$ सभी प्राकृत संख्याओं k के लिए एक साथ संबंध द्वारा

$$(1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},$$

जिससे यह स्पष्ट होता है

$${\binom {n}{0}}={\binom {n}{n}}=1,$$

और आगे,

$${\binom {n}{k}}=0$$

क > एन के लिए।

यह देखने के लिए कि ये गुणांक एस से के-संयोजनों की गणना करते हैं, पहले एन विशिष्ट चर एक्स के संग्रह पर विचार कर सकते हैं_s S के तत्वों द्वारा लेबल किया गया है, और S के सभी तत्वों पर गुणन का विस्तार करें:

$$\prod _{s\in S}(1+X_{s});$$

इसमें 2 हैⁿ S के सभी उपसमुच्चयों के अनुरूप विशिष्ट शब्द, प्रत्येक उपसमुच्चय संगत चर X का गुणनफल देता है_s. अब सभी X को सेट कर रहा हूँ_s बिना लेबल वाले चर X के बराबर, ताकि उत्पाद बन जाए (1 + X)ⁿ, S से प्रत्येक k-संयोजन के लिए शब्द X बन जाता है^k, ताकि परिणाम में उस घात का गुणांक ऐसे k-संयोजनों की संख्या के बराबर हो।

द्विपद गुणांकों की स्पष्ट रूप से विभिन्न तरीकों से गणना की जा सकती है। तक के विस्तार के लिए उन सभी को प्राप्त करने के लिए (1 + X)ⁿ, कोई (पहले से दिए गए बुनियादी मामलों के अलावा) पुनरावर्तन संबंध का उपयोग कर सकता है

$${\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},$$

0 <के <एन के लिए, जो इस प्रकार है (1 + X)ⁿ = (1 + X)^{n − 1}(1 + X); इससे पास्कल के त्रिभुज का निर्माण होता है।

व्यक्तिगत द्विपद गुणांक निर्धारित करने के लिए, सूत्र का उपयोग करना अधिक व्यावहारिक है

$${\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.$$

अंश n के n|k-क्रमपरिवर्तनों के क्रमचय#k-क्रमपरिवर्तनों की संख्या देता है, अर्थात, S के k विशिष्ट तत्वों के अनुक्रमों की, जबकि हर ऐसे k-क्रमपरिवर्तनों की संख्या देता है जो समान k-संयोजन देते हैं जब आदेश की अनदेखी की जाती है।

जब k n/2 से अधिक हो जाता है, तो उप