संयोजन

गणित में संयोजन समूह से वस्तुओं का चयन होता है। जिसमें अलग-अलग सदस्य होते हैं, जैसे कि चयन का क्रम मतलब नहीं रखता क्रम परिवर्तन के विपरीत हैं। उदाहरण के लिए, तीन फल दिए गए हैं, जैसे सेब, संतरा और नाशपाती, दो के तीन संयोजन हैं जिन्हें इस समूह से निकाला जा सकता है। सेब और नाशपाती, सेब और संतरा, नाशपाती और संतरा। अधिक औपचारिक रूप से, K- समूह (गणित) S का संयोजन S के K विशिष्ट तत्वों का उपसमूह है। इसलिए, दो संयोजन समान हैं यदि और केवल यदि प्रत्येक संयोजन में समान सदस्य हैं। प्रत्येक समूह में सदस्यों की व्यवस्था कोई मतलब नहीं रखती है। यदि समूह में 'N' तत्व हैं, तो 'K'-संयोजन की संख्या, द्वारा निरूपित $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-बहु समुच्चय, या K-चयन, अधिकांशतः उपयोग किए जाते हैं। यदि, उपरोक्त उदाहरण में किसी प्रकार के दो फलों का होना संभव था, दो सेब, दो संतरे, और दो नाशपाती, तो 3 और 2-चयन होंगे।

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

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

Main article: द्विपद गुणांक

File:Combinations without repetition; 5 choose 3.svg

5-तत्व समूह के 3-तत्व सबसमूह

N तत्वों के दिए गए समूह एस से K-संयोजनों की संख्या को अधिकांशतः प्राथमिक संयोजक ग्रंथों में दर्शाया जाता है। $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$$

K > N के लिए।

यह देखने के लिए कि ये गुणांक S से K-संयोजनों की गणना करते हैं, पहले N विशिष्ट चर X_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 <के <N के लिए, जो इस प्रकार है (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 से अधिक हो जाता है, तो उपरोक्त सूत्र में अंश और भाजक के लिए सामान्य गुणक होते हैं, और उन्हें रद्द करने से संबंध प्राप्त होता है

$$(\genfrac{}{}{0ex}{}{n}{k}$$