संयोजन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
गणित में '''संयोजन''' समूह से वस्तुओं का चयन होता है। जिसमें अलग-अलग सदस्य होते हैं, जैसे कि चयन का क्रम मतलब नहीं रखता क्रम [[परिवर्तन]] के विपरीत हैं। उदाहरण के लिए, तीन फल दिए गए हैं, जैसे सेब, संतरा और नाशपाती, दो के तीन संयोजन हैं जिन्हें इस समूह से निकाला जा सकता है। सेब और नाशपाती, सेब और संतरा, नाशपाती और संतरा। अधिक औपचारिक रूप से, ''K''- [[सेट (गणित)|समूह (गणित)]] ''S'' का संयोजन ''S'' के ''K'' विशिष्ट तत्वों का उपसमूह है। इसलिए, दो संयोजन समान हैं यदि और केवल यदि प्रत्येक संयोजन में समान सदस्य हैं। प्रत्येक समूह में सदस्यों की व्यवस्था कोई मतलब नहीं रखती है। यदि समूह में 'N' तत्व हैं, तो 'K'-संयोजन की संख्या, द्वारा निरूपित <math>C(n,k)</math> या <math>C^n_k</math>, [[द्विपद गुणांक]] के बराबर है।
गणित में '''संयोजन''' समूह से वस्तुओं का चयन होता है। जिसमें अलग-अलग सदस्य होते हैं, जैसे कि चयन का क्रम मतलब नहीं रखता क्रम [[परिवर्तन]] के विपरीत हैं। उदाहरण के लिए, तीन फल दिए गए हैं, जैसे सेब, संतरा और नाशपाती, दो के तीन संयोजन हैं जिन्हें इस समूह से निकाला जा सकता है। सेब और नाशपाती, सेब और संतरा, नाशपाती और संतरा। अधिक औपचारिक रूप से, ''K''- [[सेट (गणित)|समूह (गणित)]] ''S'' का संयोजन ''S'' के ''K'' विशिष्ट तत्वों का उपसमूह है। इसलिए, दो संयोजन समान हैं यदि और केवल यदि प्रत्येक संयोजन में समान सदस्य हैं। प्रत्येक समूह में सदस्यों की व्यवस्था कोई मतलब नहीं रखती है। यदि समूह में 'N' तत्व हैं, तो 'K'-संयोजन की संख्या, द्वारा निरूपित <math>C(n,k)</math> या <math>C^n_k</math>, [[द्विपद गुणांक]] के बराबर है।


<math display="block"> \binom nk = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1},</math>
<math display="block"> \binom nk = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1},</math>
जिसे [[ कारख़ाने का | भाज्य]] का उपयोग करके <math>\textstyle\frac{n!}{k!(n-k)!}</math> लिखा जा सकता है। जब कभी भी <math>k\leq n</math> और कौन सा कब शून्य है <math>k>n</math>. यह सूत्र इस तथ्य से प्राप्त किया जा सकता है कि n सदस्यों के समुच्चय S के प्रत्येक k-संयोजन में है <math>k!</math> क्रमपरिवर्तन तो <math>P^n_k = C^n_k \times k!</math> या <math>C^n_k = P^n_k / k!</math>.<ref>{{Cite book|last=Reichl|first=Linda E.|title=सांख्यिकीय भौतिकी में एक आधुनिक पाठ्यक्रम|publisher=WILEY-VCH|year=2016|isbn=978-3-527-69048-0|pages=30|chapter=2.2. Counting Microscopic States}}</ref> समुच्चय S के सभी k-संयोजनों के समुच्चय को प्राय: निरूपित किया जाता है <math>\textstyle\binom Sk</math>.
जिसे [[ कारख़ाने का |भाज्य]] का उपयोग करके <math>\textstyle\frac{n!}{k!(n-k)!}</math> लिखा जा सकता है। जब कभी भी <math>k\leq n</math> और कौन सा कब शून्य है <math>k>n</math>. यह सूत्र इस तथ्य से प्राप्त किया जा सकता है कि n सदस्यों के समुच्चय S के प्रत्येक k-संयोजन में है <math>k!</math> क्रमपरिवर्तन तो <math>P^n_k = C^n_k \times k!</math> या <math>C^n_k = P^n_k / k!</math>.<ref>{{Cite book|last=Reichl|first=Linda E.|title=सांख्यिकीय भौतिकी में एक आधुनिक पाठ्यक्रम|publisher=WILEY-VCH|year=2016|isbn=978-3-527-69048-0|pages=30|chapter=2.2. Counting Microscopic States}}</ref> समुच्चय S के सभी k-संयोजनों के समुच्चय को प्राय: निरूपित किया जाता है <math>\textstyle\binom Sk</math>.


संयोजन n चीजों का संयोजन है जिसे बार में अतिरिक्त दोहराव k लिया जाता है। उन संयोजनों को संदर्भित करने के लिए जिनमें पुनरावृत्ति की अनुमति है, पुनरावृत्ति के साथ k-संयोजन, k-[[multiset|बहु समुच्चय]],<ref>{{harvnb|Mazur|2010|loc=p. 10}}</ref> या K-चयन,<ref>{{harvnb|Ryser|1963|loc=p. 7}} also referred to as an ''unordered selection''.</ref> अधिकांशतः उपयोग किए जाते हैं।<ref>When the term ''combination'' is used to refer to either situation (as in {{harv|Brualdi|2010}}) care must be taken to clarify whether sets or multisets are being discussed.</ref> यदि, उपरोक्त उदाहरण में किसी प्रकार के दो फलों का होना संभव था, दो सेब, दो संतरे, और दो नाशपाती, तो 3 और 2-चयन होंगे।
संयोजन n चीजों का संयोजन है जिसे बार में अतिरिक्त दोहराव k लिया जाता है। उन संयोजनों को संदर्भित करने के लिए जिनमें पुनरावृत्ति की अनुमति है, पुनरावृत्ति के साथ k-संयोजन, k-[[multiset|बहु समुच्चय]],<ref>{{harvnb|Mazur|2010|loc=p. 10}}</ref> या K-चयन,<ref>{{harvnb|Ryser|1963|loc=p. 7}} also referred to as an ''unordered selection''.</ref> अधिकांशतः उपयोग किए जाते हैं।<ref>When the term ''combination'' is used to refer to either situation (as in {{harv|Brualdi|2010}}) care must be taken to clarify whether sets or multisets are being discussed.</ref> यदि, उपरोक्त उदाहरण में किसी प्रकार के दो फलों का होना संभव था, दो सेब, दो संतरे, और दो नाशपाती, तो 3 और 2-चयन होंगे।


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


== K-संयोजनों की संख्या ==
== K-संयोजनों की संख्या ==
{{main|द्विपद गुणांक}}
{{main|द्विपद गुणांक}}
[[File:Combinations without repetition; 5 choose 3.svg|thumb|5-तत्व समूह के 3-तत्व सबसमूह]]N तत्वों के दिए गए समूह एस से K-संयोजनों की संख्या को अधिकांशतः प्राथमिक संयोजक ग्रंथों में दर्शाया जाता है। <math>C(n,k)</math>, भिन्नरूप द्वारा जैसे <math>C^n_k</math>, <math>{}_nC_k</math>, <math>{}^nC_k</math>, <math>C_{n,k}</math> और भी <math>C_n^k</math> अंतिम रूप फ्रेंच, रोमानियाई, रूसी, चीनी में मानक है<ref>{{cite book |title = पूर्णकालिक छात्र के लिए हाई स्कूल पाठ्यपुस्तक (आवश्यक) गणित पुस्तक II बी| edition=2nd | location = China|language = zh |date=June 2006| publisher = People's Education Press| pages = 107–116 | isbn = 978-7-107-19616-4 }}</ref><ref>{{cite book |url=http://www.shuxue9.com/pep/gzxuanxiu23/ebook/31.html|title=人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press)| publisher =People's Education Press | page=21 }}</ref> और पोलिश ग्रंथ। वही संख्या चूंकि कई अन्य गणितीय संदर्भों में होती है, जहां इसे द्वारा निरूपित किया जाता है <math>\tbinom nk</math> अधिकांशतः n चुनें k के रूप में पढ़ा जाता है। विशेष रूप से यह [[द्विपद सूत्र]] में गुणांक के रूप में होता है, इसलिए इसका नाम 'द्विपद गुणांक' है। कोई परिभाषित कर सकता है <math>\tbinom nk</math> सभी प्राकृत संख्याओं k के लिए साथ संबंध द्वारा
[[File:Combinations without repetition; 5 choose 3.svg|thumb|5-तत्व समूह के 3-तत्व सबसमूह]]N तत्वों के दिए गए समूह एस से K-संयोजनों की संख्या को अधिकांशतः प्राथमिक संयोजक ग्रंथों में दर्शाया जाता है। <math>C(n,k)</math>, भिन्नरूप द्वारा जैसे <math>C^n_k</math>, <math>{}_nC_k</math>, <math>{}^nC_k</math>, <math>C_{n,k}</math> और भी <math>C_n^k</math> अंतिम रूप फ्रेंच, रोमानियाई, रूसी, चीनी में मानक है<ref>{{cite book |title = पूर्णकालिक छात्र के लिए हाई स्कूल पाठ्यपुस्तक (आवश्यक) गणित पुस्तक II बी| edition=2nd | location = China|language = zh |date=June 2006| publisher = People's Education Press| pages = 107–116 | isbn = 978-7-107-19616-4 }}</ref><ref>{{cite book |url=http://www.shuxue9.com/pep/gzxuanxiu23/ebook/31.html|title=人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press)| publisher =People's Education Press | page=21 }}</ref> और पोलिश ग्रंथ। वही संख्या चूंकि कई अन्य गणितीय संदर्भों में होती है, जहां इसे द्वारा निरूपित किया जाता है <math>\tbinom nk</math> अधिकांशतः n चुनें k के रूप में पढ़ा जाता है। विशेष रूप से यह [[द्विपद सूत्र]] में गुणांक के रूप में होता है, इसलिए इसका नाम 'द्विपद गुणांक' है। कोई परिभाषित कर सकता है <math>\tbinom nk</math> सभी प्राकृत संख्याओं k के लिए साथ संबंध द्वारा


<math display="block">(1 + X)^n = \sum_{k\geq0}\binom{n}{k} X^k,</math>
<math display="block">(1 + X)^n = \sum_{k\geq0}\binom{n}{k} X^k,</math>
Line 24: Line 24:


<math display="block">\prod_{s\in S}(1+X_s);</math>
<math display="block">\prod_{s\in S}(1+X_s);</math>
इसमें 2<sup>n</sup> है S के सभी उपसमुच्चय ों के अनुरूप विशिष्ट शब्द, प्रत्येक उपसमुच्चय संगत चर X<sub>''s''</sub> का गुणनफल देता है। अब सभी X<sub>''s''</sub> को समूह कर रहा हूँ अतिरिक्त लेबल वाले चर X के बराबर, जिससे कि उत्पाद बन जाए {{nowrap|(1 + ''X'')<sup>''n''</sup>}}, S से प्रत्येक k-संयोजन के लिए शब्द X<sup>k</sup> बन जाता है, जिससे कि परिणाम में उस घात का गुणांक ऐसे k-संयोजनों की संख्या के बराबर हो।
इसमें 2<sup>n</sup> है S के सभी उपसमुच्चय ों के अनुरूप विशिष्ट शब्द, प्रत्येक उपसमुच्चय संगत चर X<sub>''s''</sub> का गुणनफल देता है। अब सभी X<sub>''s''</sub> को समूह कर रहा हूँ अतिरिक्त लेबल वाले चर X के बराबर, जिससे कि उत्पाद बन जाए {{nowrap|(1 + ''X'')<sup>''n''</sup>}}, S से प्रत्येक k-संयोजन के लिए शब्द X<sup>k</sup> बन जाता है, जिससे कि परिणाम में उस घात का गुणांक ऐसे k-संयोजनों की संख्या के बराबर हो।


द्विपद गुणांकों की स्पष्ट रूप से विभिन्न विधियों से गणना की जा सकती है। विस्तार के लिए उन सभी को प्राप्त करने के लिए {{nowrap|(1 + ''X'')<sup>''n''</sup>}}, कोई पहले से दिए गए मूलभूत स्थितियों के अतिरिक्त पुनरावर्तन संबंध का उपयोग कर सकता है।
द्विपद गुणांकों की स्पष्ट रूप से विभिन्न विधियों से गणना की जा सकती है। विस्तार के लिए उन सभी को प्राप्त करने के लिए {{nowrap|(1 + ''X'')<sup>''n''</sup>}}, कोई पहले से दिए गए मूलभूत स्थितियों के अतिरिक्त पुनरावर्तन संबंध का उपयोग कर सकता है।
Line 39: Line 39:


<math display="block"> \binom nk = \binom n{n-k},</math>
<math display="block"> \binom nk = \binom n{n-k},</math>
0 ≤ k ≤ n के लिए। यह समरूपता व्यक्त करता है जो द्विपद सूत्र से स्पष्ट है, और इस प्रकार के संयोजन के [[पूरक (सेट सिद्धांत)|पूरक (समूह सिद्धांत)]] को ले कर K-संयोजनों के संदर्भ में भी समझा जा सकता है, जो {{nowrap|(''n'' − ''k'')}}-संयोजन।
0 ≤ k ≤ n के लिए। यह समरूपता व्यक्त करता है जो द्विपद सूत्र से स्पष्ट है, और इस प्रकार के संयोजन के [[पूरक (सेट सिद्धांत)|पूरक (समूह सिद्धांत)]] को ले कर K-संयोजनों के संदर्भ में भी समझा जा सकता है, जो {{nowrap|(''n'' − ''k'')}}-संयोजन।


अंत में सूत्र है जो इस समरूपता को सीधे प्रदर्शित करता है और याद रखने में आसान होने का गुण है।
अंत में सूत्र है जो इस समरूपता को सीधे प्रदर्शित करता है और याद रखने में आसान होने का गुण है।


<math display="block"> \binom nk = \frac{n!}{k!(n-k)!},</math>
<math display="block"> \binom nk = \frac{n!}{k!(n-k)!},</math>
जहाँ n<nowiki>!</nowiki> n का क्रमगुणन दर्शाता है। यह पिछले सूत्र से भाजक और अंश को गुणा करके प्राप्त किया जाता है {{nowrap|(''n'' − ''k'')}} !, तो यह निश्चित रूप से उस सूत्र से कम्प्यूटेशनल रूप से कम कुशल है।
जहाँ n<nowiki>!</nowiki> n का क्रमगुणन दर्शाता है। यह पिछले सूत्र से भाजक और अंश को गुणा करके प्राप्त किया जाता है {{nowrap|(''n'' − ''k'')}} !, तो यह निश्चित रूप से उस सूत्र से कम्प्यूटेशनल रूप से कम कुशल है।


अंतिम सूत्र को S के सभी तत्वों के n<nowiki>!</nowiki> क्रमचय पर विचार करके सीधे समझा जा सकता है। ऐसा प्रत्येक क्रमचय अपने पहले k तत्वों का चयन करके k-संयोजन देता है। कई डुप्लिकेट चयन हैं, जो दूसरे के बीच पहले k तत्वों का कोई भी संयुक्त क्रम परिवर्तन और दूसरे के बीच अंतिम (n− k) तत्वों का ही संयोजन उत्पन्न करता है। यह सूत्र में विभाजन की व्याख्या करता है।
अंतिम सूत्र को S के सभी तत्वों के n<nowiki>!</nowiki> क्रमचय पर विचार करके सीधे समझा जा सकता है। ऐसा प्रत्येक क्रमचय अपने पहले k तत्वों का चयन करके k-संयोजन देता है। कई डुप्लिकेट चयन हैं, जो दूसरे के बीच पहले k तत्वों का कोई भी संयुक्त क्रम परिवर्तन और दूसरे के बीच अंतिम (n− k) तत्वों का ही संयोजन उत्पन्न करता है। यह सूत्र में विभाजन की व्याख्या करता है।


उपरोक्त सूत्रों से तीनों दिशाओं में पास्कल के त्रिभुज में सन्निकट संख्याओं के बीच संबंधों का अनुसरण करें।
उपरोक्त सूत्रों से तीनों दिशाओं में पास्कल के त्रिभुज में सन्निकट संख्याओं के बीच संबंधों का अनुसरण करें।
Line 58: Line 58:
\end{cases}.
\end{cases}.
</math>
</math>
साथ में मूलभूत स्थितियों <math>\tbinom n0=1=\tbinom nn</math>, ये क्रमशः समूह पास्कल के त्रिकोण में पंक्ति से संयोजनों की क्रमिक गणना की अनुमति देते हैं, बढ़ते आकारों के समूहों के k-संयोजनों और निश्चित आकार के पूरक के साथ संयोजनों की {{nowrap|''n'' − ''k''}}.
साथ में मूलभूत स्थितियों <math>\tbinom n0=1=\tbinom nn</math>, ये क्रमशः समूह पास्कल के त्रिकोण में पंक्ति से संयोजनों की क्रमिक गणना की अनुमति देते हैं, बढ़ते आकारों के समूहों के k-संयोजनों और निश्चित आकार के पूरक के साथ संयोजनों की {{nowrap|''n'' − ''k''}}.


=== गिनती संयोजनों का उदाहरण ===
=== गिनती संयोजनों का उदाहरण ===
विशिष्ट उदाहरण के रूप में, मानक बावन कार्ड डेक से संभव पांच-कार्ड हाथों की संख्या की गणना कर सकते हैं।<ref>{{harvnb|Mazur|2010|loc=p. 21}}</ref>
विशिष्ट उदाहरण के रूप में, मानक बावन कार्ड डेक से संभव पांच-कार्ड हाथों की संख्या की गणना कर सकते हैं।<ref>{{harvnb|Mazur|2010|loc=p. 21}}</ref>


<math display="block"> {52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311{,}875{,}200}{120} =  
<math display="block"> {52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311{,}875{,}200}{120} =  
Line 81: Line 81:


<math display="block"> {52 \choose 5} = \frac{52}1 \times \frac{51}2 \times \frac{50}3 \times \frac{49}4 \times \frac{48}5 = 2{,}598{,}960.</math>
<math display="block"> {52 \choose 5} = \frac{52}1 \times \frac{51}2 \times \frac{50}3 \times \frac{49}4 \times \frac{48}5 = 2{,}598{,}960.</math>
निम्नलिखित क्रम में मूल्यांकन करते समय, {{math|52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5}}, इसकी गणना केवल पूर्णांक अंकगणित का उपयोग करके की जा सकती है। इसका कारण यह है कि जब प्रत्येक विभाजन होता है, तो उत्पन्न होने वाला मध्यवर्ती परिणाम अपने आप में द्विपद गुणांक होता है, इसलिए कोई अवशेष कभी नहीं होता है।
निम्नलिखित क्रम में मूल्यांकन करते समय, {{math|52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5}}, इसकी गणना केवल पूर्णांक अंकगणित का उपयोग करके की जा सकती है। इसका कारण यह है कि जब प्रत्येक विभाजन होता है, तो उत्पन्न होने वाला मध्यवर्ती परिणाम अपने आप में द्विपद गुणांक होता है, इसलिए कोई अवशेष कभी नहीं होता है।


सरलीकरण किए अतिरिक्त फैक्टोरियल के स्थितियों में सममित सूत्र का उपयोग करना व्यापक गणना देता है।
सरलीकरण किए अतिरिक्त फैक्टोरियल के स्थितियों में सममित सूत्र का उपयोग करना व्यापक गणना देता है।


<math display="block">
<math display="block">
Line 95: Line 95:
=== K-संयोजनों की [[गणना]] ===
=== K-संयोजनों की [[गणना]] ===


कोई निश्चित क्रम में n तत्वों के दिए गए समूह S के सभी k-संयोजनों की गणना कर सकता है, जो अंतराल से आक्षेप स्थापित करता है <math>\tbinom nk</math> उन K-संयोजनों के समूह के साथ पूर्णांक। यह मानते हुए कि S को स्वयं अनुक्रम किया गया है, उदाहरण के लिए S = { 1, 2, ..., n }, इसके k-संयोजनों को अनुक्रम करने की दो स्वाभाविक संभावनाएँ हैं। पहले उनके सबसे छोटे तत्वों की तुलना करके जैसा कि ऊपर दिए गए चित्र में है, तुलना करके उनके सबसे बड़े तत्व पहले। बाद वाले विकल्प का लाभ यह है कि एस में नया सबसे बड़ा तत्व जोड़ने से गणना के प्रारंभिक भागों में बदलाव नहीं आएगा, किन्तु पिछले वाले के बाद बड़े समूह के नए K-संयोजन जोड़ें। इस प्रक्रिया को दोहराते हुए, कभी भी बड़े समूहों के k-संयोजनों के साथ गणना को अनिश्चित काल तक बढ़ाया जा सकता है। यदि इसके अतिरिक्त पूर्णांकों के अंतराल को 0 से प्रारंभ करने के लिए लिया जाता है, तो गणना में किसी दिए गए स्थान i पर k-संयोजन की गणना i से आसानी से की जा सकती है और इस प्रकार प्राप्त होने वाली आपत्ति [[संयोजन संख्या प्रणाली]] के रूप में जानी जाती है। इसे कम्प्यूटेशनल गणित में रैंक/रैंकिंग और अनरैंकिंग के रूप में भी जाना जाता है।<ref>{{cite web|url=http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf |archive-date=2022-10-09 |url-status=live |title=प्राथमिक मिश्रित वस्तुओं का निर्माण|author=Lucia Moura |website=Site.uottawa.ca |access-date=2017-04-10}}</ref><ref>{{cite web|url=http://www.sagemath.org/doc/reference/sage/combinat/subset.html |format=PDF |title=SAGE : Subsets |website=Sagemath.org |access-date=2017-04-10}}</ref>K संयोजनों की गणना करने के कई विधियाँ हैं। 2<sup>N</sup> से कम सभी बाइनरी नंबरों पर जाना। उन संख्याओं को चुनें जिनमें k अशून्य बिट्स हों, चूंकि यह छोटे n के लिए भी बहुत अक्षम है उदाहरण के लिए n = 20 को लगभग मिलियन नंबरों पर जाने की आवश्यकता होगी, जबकि k = 10 के लिए अनुमत k संयोजनों की अधिकतम संख्या लगभग 186 हजार है। ऐसी संख्या में इन 1 बिट्स की स्थिति समूह {1, ..., n} का विशिष्ट k-संयोजन है<ref>{{cite web|url=http://rosettacode.org/wiki/Combinations|title=संयोजन - रोसेटा कोड|date=23 October 2022 }}{{ugc|date=April 2017}}</ref> और सरल, तेज़ विधि चयनित तत्वों के k अनुक्रमणिका नंबरों को ट्रैक करना है, {0 .. k−1} (शून्य-आधारित) या {1 .. k} (एक-आधारित) से प्रारंभ होकर पहले अनुमत k-संयोजन के रूप में और फिर बार-बार अंतिम अनुक्रमणिका संख्या में वृद्धि करके अगले अनुमत k-संयोजन पर जाना यदि यह n-1 (शून्य-आधारित) या n (एक-आधारित) या अंतिम अनुक्रमणिका संख्या x से कम है जो अनुक्रमणिका संख्या से कम है यदि ऐसा कोई अनुक्रमणिका उपस्तिथ है तो इसके बाद ऋण और अनुक्रमणिका नंबर को x के बाद {x+1, x+2, ...} पर रीसेट करना।
कोई निश्चित क्रम में n तत्वों के दिए गए समूह S के सभी k-संयोजनों की गणना कर सकता है, जो अंतराल से आक्षेप स्थापित करता है <math>\tbinom nk</math> उन K-संयोजनों के समूह के साथ पूर्णांक। यह मानते हुए कि S को स्वयं अनुक्रम किया गया है, उदाहरण के लिए S = { 1, 2, ..., n }, इसके k-संयोजनों को अनुक्रम करने की दो स्वाभाविक संभावनाएँ हैं। पहले उनके सबसे छोटे तत्वों की तुलना करके जैसा कि ऊपर दिए गए चित्र में है, तुलना करके उनके सबसे बड़े तत्व पहले। बाद वाले विकल्प का लाभ यह है कि एस में नया सबसे बड़ा तत्व जोड़ने से गणना के प्रारंभिक भागों में बदलाव नहीं आएगा, किन्तु पिछले वाले के बाद बड़े समूह के नए K-संयोजन जोड़ें। इस प्रक्रिया को दोहराते हुए, कभी भी बड़े समूहों के k-संयोजनों के साथ गणना को अनिश्चित काल तक बढ़ाया जा सकता है। यदि इसके अतिरिक्त पूर्णांकों के अंतराल को 0 से प्रारंभ करने के लिए लिया जाता है, तो गणना में किसी दिए गए स्थान i पर k-संयोजन की गणना i से आसानी से की जा सकती है और इस प्रकार प्राप्त होने वाली आपत्ति [[संयोजन संख्या प्रणाली]] के रूप में जानी जाती है। इसे कम्प्यूटेशनल गणित में रैंक/रैंकिंग और अनरैंकिंग के रूप में भी जाना जाता है।<ref>{{cite web|url=http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf |archive-date=2022-10-09 |url-status=live |title=प्राथमिक मिश्रित वस्तुओं का निर्माण|author=Lucia Moura |website=Site.uottawa.ca |access-date=2017-04-10}}</ref><ref>{{cite web|url=http://www.sagemath.org/doc/reference/sage/combinat/subset.html |format=PDF |title=SAGE : Subsets |website=Sagemath.org |access-date=2017-04-10}}</ref>K संयोजनों की गणना करने के कई विधियाँ हैं। 2<sup>N</sup> से कम सभी बाइनरी नंबरों पर जाना। उन संख्याओं को चुनें जिनमें k अशून्य बिट्स हों, चूंकि यह छोटे n के लिए भी बहुत अक्षम है उदाहरण के लिए n = 20 को लगभग मिलियन नंबरों पर जाने की आवश्यकता होगी, जबकि k = 10 के लिए अनुमत k संयोजनों की अधिकतम संख्या लगभग 186 हजार है। ऐसी संख्या में इन 1 बिट्स की स्थिति समूह {1, ..., n} का विशिष्ट k-संयोजन है<ref>{{cite web|url=http://rosettacode.org/wiki/Combinations|title=संयोजन - रोसेटा कोड|date=23 October 2022 }}{{ugc|date=April 2017}}</ref> और सरल, तेज़ विधि चयनित तत्वों के k अनुक्रमणिका नंबरों को ट्रैक करना है, {0 .. k−1} (शून्य-आधारित) या {1 .. k} (एक-आधारित) से प्रारंभ होकर पहले अनुमत k-संयोजन के रूप में और फिर बार-बार अंतिम अनुक्रमणिका संख्या में वृद्धि करके अगले अनुमत k-संयोजन पर जाना यदि यह n-1 (शून्य-आधारित) या n (एक-आधारित) या अंतिम अनुक्रमणिका संख्या x से कम है जो अनुक्रमणिका संख्या से कम है यदि ऐसा कोई अनुक्रमणिका उपस्तिथ है तो इसके बाद ऋण और अनुक्रमणिका नंबर को x के बाद {x+1, x+2, ...} पर रीसेट करना।


== पुनरावृत्ति के साथ संयोजनों की संख्या ==
== पुनरावृत्ति के साथ संयोजनों की संख्या ==
{{See also|मल्टीसेट गुणांक}}
{{See also|मल्टीसेट गुणांक}}


k- 'पुनरावृत्ति के साथ संयोजन', या k- 'बहुसंयोजन', आकार k का 'मल्टीसमूह' आकार n के समूह S से k के समूह द्वारा दिया जाता है, जो आवश्यक रूप से S के अलग-अलग तत्व नहीं होते हैं, जहाँ क्रम में नहीं लिया जाता है खाता: दो अनुक्रम ही मल्टीसमूह को परिभाषित करते हैं यदि शर्तों को अनुमति देकर दूसरे से प्राप्त किया जा सकता है। दूसरे शब्दों में, यह n तत्वों के समूह से k तत्वों का नमूना है जो डुप्लिकेट अर्थात, प्रतिस्थापन के साथ की अनुमति देता है, किन्तु अलग-अलग ऑर्डरिंग (जैसे {2,1,2} = {1,2,2}) की अवहेलना करता है। एस के प्रत्येक तत्व के लिए अनुक्रमणिका को संबद्ध करें और एस के तत्वों को वस्तुओं के प्रकार के रूप में सोचें, फिर हम बता सकते हैं <math>x_i</math> बहुउपसमुच्चय में प्रकार k तत्वों की संख्या को निरूपित करें। आकार k के बहुउपसमुच्चय की संख्या [[डायोफैंटाइन समीकरण]] के गैर-ऋणात्मक पूर्णांक इसलिए शून्य की अनुमति समाधानों की संख्या है।<ref>{{harvnb|Brualdi|2010|loc=p. 52}}</ref>
k- 'पुनरावृत्ति के साथ संयोजन', या k- 'बहुसंयोजन', आकार k का 'मल्टीसमूह' आकार n के समूह S से k के समूह द्वारा दिया जाता है, जो आवश्यक रूप से S के अलग-अलग तत्व नहीं होते हैं, जहाँ क्रम में नहीं लिया जाता है खाता: दो अनुक्रम ही मल्टीसमूह को परिभाषित करते हैं यदि शर्तों को अनुमति देकर दूसरे से प्राप्त किया जा सकता है। दूसरे शब्दों में, यह n तत्वों के समूह से k तत्वों का नमूना है जो डुप्लिकेट अर्थात, प्रतिस्थापन के साथ की अनुमति देता है, किन्तु अलग-अलग ऑर्डरिंग (जैसे {2,1,2} = {1,2,2}) की अवहेलना करता है। एस के प्रत्येक तत्व के लिए अनुक्रमणिका को संबद्ध करें और एस के तत्वों को वस्तुओं के प्रकार के रूप में सोचें, फिर हम बता सकते हैं <math>x_i</math> बहुउपसमुच्चय में प्रकार k तत्वों की संख्या को निरूपित करें। आकार k के बहुउपसमुच्चय की संख्या [[डायोफैंटाइन समीकरण]] के गैर-ऋणात्मक पूर्णांक इसलिए शून्य की अनुमति समाधानों की संख्या है।<ref>{{harvnb|Brualdi|2010|loc=p. 52}}</ref>


<math display="block">x_1 + x_2 + \ldots + x_n = k.</math>
<math display="block">x_1 + x_2 + \ldots + x_n = k.</math>
यदि S में n अवयव हैं, तो ऐसे k-बहु उपसमुच्चय की संख्या को इसके द्वारा निरूपित किया जाता है।
यदि S में n अवयव हैं, तो ऐसे k-बहु उपसमुच्चय की संख्या को इसके द्वारा निरूपित किया जाता है।


<math display="block">\left(\!\!\binom{n}{k}\!\!\right),</math>
<math display="block">\left(\!\!\binom{n}{k}\!\!\right),</math>
अंकन जो द्विपद गुणांक के अनुरूप है जो k-उपसमुच्चय की गणना करता है। यह व्यंजक, n बहुचयन k,<ref>{{harvnb|Benjamin|Quinn|2003|loc=p. 70}}</ref> द्विपद गुणांक के संदर्भ में भी दिया जा सकता है।
अंकन जो द्विपद गुणांक के अनुरूप है जो k-उपसमुच्चय की गणना करता है। यह व्यंजक, n बहुचयन k,<ref>{{harvnb|Benjamin|Quinn|2003|loc=p. 70}}</ref> द्विपद गुणांक के संदर्भ में भी दिया जा सकता है।


<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}.</math>
<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}.</math>
Line 117: Line 117:
{{Hidden end}}
{{Hidden end}}


[[File:Combinations with repetition; 5 multichoose 3.svg|thumb|370px|7-समूह (बाएं) के 3-उपसमुच्चय और 5-समूह (दाएं) के तत्वों वाले 3-मल्टीसमूह के बीच ऑब्जेक्शन।<br />यह दर्शाता है कि <math display="inline"> \binom{7}{3} = \left(\!\! \binom{5}{3}\!\!\right)</math>.]]जैसा कि द्विपद गुणांकों के साथ होता है, इन बहुविकल्पी व्यंजकों के बीच कई संबंध होते हैं। उदाहरण के लिए, के लिए <math> n \ge 1, k \ge 0</math>,
[[File:Combinations with repetition; 5 multichoose 3.svg|thumb|370px|7-समूह (बाएं) के 3-उपसमुच्चय और 5-समूह (दाएं) के तत्वों वाले 3-मल्टीसमूह के बीच ऑब्जेक्शन।<br />यह दर्शाता है कि <math display="inline"> \binom{7}{3} = \left(\!\! \binom{5}{3}\!\!\right)</math>.]]जैसा कि द्विपद गुणांकों के साथ होता है, इन बहुविकल्पी व्यंजकों के बीच कई संबंध होते हैं। उदाहरण के लिए, के लिए <math> n \ge 1, k \ge 0</math>,


<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right).</math>
<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right).</math>
Line 175: Line 175:
{{See also|द्विपद गुणांक गुणांक पंक्ति का योग}}
{{See also|द्विपद गुणांक गुणांक पंक्ति का योग}}


सभी k के लिए k-संयोजनों की संख्या n तत्वों के समूह के उपसमूह की संख्या है। यह देखने के कई विधियाँ हैं कि यह संख्या 2<sup>N</sup> है। संयोजनों के संदर्भ में, <math display="inline">\sum_{0\leq{k}\leq{n}}\binom n k = 2^n</math>, जो द्विपद गुणांक की nवीं पंक्ति 0 से गिनती का योग है।पास्कल के त्रिकोण में गुणांक पंक्ति का योग। इन संयोजनों उपसमुच्चय को 0 से 2 तक गिने जाने वाले [[आधार 2]] संख्याओं के समूह के 1 अंकों द्वारा गिना जाता है<sup>n</sup> − 1, जहां प्रत्येक अंक स्थिति n के समूह से विषय है।
सभी k के लिए k-संयोजनों की संख्या n तत्वों के समूह के उपसमूह की संख्या है। यह देखने के कई विधियाँ हैं कि यह संख्या 2<sup>N</sup> है। संयोजनों के संदर्भ में, <math display="inline">\sum_{0\leq{k}\leq{n}}\binom n k = 2^n</math>, जो द्विपद गुणांक की nवीं पंक्ति 0 से गिनती का योग है।पास्कल के त्रिकोण में गुणांक पंक्ति का योग। इन संयोजनों उपसमुच्चय को 0 से 2 तक गिने जाने वाले [[आधार 2]] संख्याओं के समूह के 1 अंकों द्वारा गिना जाता है<sup>n</sup> − 1, जहां प्रत्येक अंक स्थिति n के समूह से विषय है।


1 से 3 तक की संख्या वाले 3 कार्ड दिए गए हैं, [[खाली सेट|खाली समूह]] सहित 8 अलग-अलग संयोजन उपसमुच्चय हैं।
1 से 3 तक की संख्या वाले 3 कार्ड दिए गए हैं, [[खाली सेट|खाली समूह]] सहित 8 अलग-अलग संयोजन उपसमुच्चय हैं।
Line 191: Line 191:
*7 - 111
*7 - 111


== संभावना: यादृच्छिक संयोजन का नमूना लेना ==
== संभावना: यादृच्छिक संयोजन का नमूना लेना ==


किसी दिए गए सूची से यादृच्छिक संयोजन चुनने के लिए विभिन्न [[एल्गोरिदम]] हैं। बड़े नमूना आकारों के लिए [[अस्वीकृति नमूनाकरण]] अत्यंत धीमा है। आकार N की आबादी से कुशलता से K-संयोजन का चयन करने का विधि आबादी के प्रत्येक तत्व में पुन: प्रयास करना है और प्रत्येक चरण में उस तत्व को गतिशील रूप से बदलती संभावना के साथ चुनें <math display="inline">\frac{k-\#\text{samples chosen}}{n- \#\text{samples visited}}</math> (जलाशय नमूना देखें)। दूसरा यादृच्छिक गैर-ऋणात्मक पूर्णांक से कम चुनना है <math>\textstyle\binom nk</math> और संयोजन संख्या प्रणाली का उपयोग करके इसे संयोजन में परिवर्तित करें।
किसी दिए गए सूची से यादृच्छिक संयोजन चुनने के लिए विभिन्न [[एल्गोरिदम]] हैं। बड़े नमूना आकारों के लिए [[अस्वीकृति नमूनाकरण]] अत्यंत धीमा है। आकार N की आबादी से कुशलता से K-संयोजन का चयन करने का विधि आबादी के प्रत्येक तत्व में पुन: प्रयास करना है और प्रत्येक चरण में उस तत्व को गतिशील रूप से बदलती संभावना के साथ चुनें <math display="inline">\frac{k-\#\text{samples chosen}}{n- \#\text{samples visited}}</math> (जलाशय नमूना देखें)। दूसरा यादृच्छिक गैर-ऋणात्मक पूर्णांक से कम चुनना है <math>\textstyle\binom nk</math> और संयोजन संख्या प्रणाली का उपयोग करके इसे संयोजन में परिवर्तित करें।


== वस्तुओं को डिब्बे में डालने के विधियों की संख्या ==
== वस्तुओं को डिब्बे में डालने के विधियों की संख्या ==


संयोजन को वस्तुओं के दो समूहों के चयन के रूप में भी माना जा सकता है। वे जो चुने हुए बिन में जाते हैं और वे जो अवांछित बिन में जाते हैं। इसे किसी भी संख्या में डिब्बे के लिए सामान्यीकृत किया जा सकता है, जिसमें यह बाधा है कि प्रत्येक वस्तु को ठीक बिन में जाना चाहिए। वस्तुओं को डिब्बे में डालने के विधियों की संख्या बहुराष्ट्रीय प्रमेय द्वारा दी गई है वस्तुओं को डिब्बे में डालने के विधियों  
संयोजन को वस्तुओं के दो समूहों के चयन के रूप में भी माना जा सकता है। वे जो चुने हुए बिन में जाते हैं और वे जो अवांछित बिन में जाते हैं। इसे किसी भी संख्या में डिब्बे के लिए सामान्यीकृत किया जा सकता है, जिसमें यह बाधा है कि प्रत्येक वस्तु को ठीक बिन में जाना चाहिए। वस्तुओं को डिब्बे में डालने के विधियों की संख्या बहुराष्ट्रीय प्रमेय द्वारा दी गई है वस्तुओं को डिब्बे में डालने के विधियों  


<math display="block"> {n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!},</math>
<math display="block"> {n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!},</math>
जहाँ n वस्तुओं की संख्या है, m डिब्बे की संख्या है, और <math>k_i</math> बिन i में जाने वाली वस्तुओं की संख्या है।
जहाँ n वस्तुओं की संख्या है, m डिब्बे की संख्या है, और <math>k_i</math> बिन i में जाने वाली वस्तुओं की संख्या है।


यह देखने का विधि है कि यह समीकरण क्यों धारण करता है, पहले वस्तुओं को मनमाने ढंग से 1 से n तक नंबर देना है और वस्तुओं को संख्याओं के साथ रखना है <math>1, 2, \ldots, k_1</math> क्रम में पहले बिन में, वस्तुओं के साथ संख्याएँ <math>k_1+1, k_1+2, \ldots, k_2</math> क्रम में दूसरे बिन में, और इसी तरह। वहाँ हैं <math>n!</math> अलग-अलग नंबरिंग, किन्तु उनमें से कई समतुल्य हैं, क्योंकि बिन में केवल वस्तुओं का समूह मतलब रखता है, इसमें उनका क्रम नहीं। प्रत्येक डिब्बे की सामग्री का प्रत्येक संयुक्त क्रमचय वस्तुओं को डिब्बे में डालने का समान विधि उत्पन्न करता है। परिणाम स्वरुप , प्रत्येक समकक्ष वर्ग में सम्मलित हैं <math>k_1!\, k_2! \cdots k_m!</math> विशिष्ट संख्याएँ और तुल्यता वर्गों की संख्या है <math>\textstyle\frac{n!}{k_1!\, k_2! \cdots k_m!}</math>.
यह देखने का विधि है कि यह समीकरण क्यों धारण करता है, पहले वस्तुओं को मनमाने ढंग से 1 से n तक नंबर देना है और वस्तुओं को संख्याओं के साथ रखना है <math>1, 2, \ldots, k_1</math> क्रम में पहले बिन में, वस्तुओं के साथ संख्याएँ <math>k_1+1, k_1+2, \ldots, k_2</math> क्रम में दूसरे बिन में, और इसी तरह। वहाँ हैं <math>n!</math> अलग-अलग नंबरिंग, किन्तु उनमें से कई समतुल्य हैं, क्योंकि बिन में केवल वस्तुओं का समूह मतलब रखता है, इसमें उनका क्रम नहीं। प्रत्येक डिब्बे की सामग्री का प्रत्येक संयुक्त क्रमचय वस्तुओं को डिब्बे में डालने का समान विधि उत्पन्न करता है। परिणाम स्वरुप , प्रत्येक समकक्ष वर्ग में सम्मलित हैं <math>k_1!\, k_2! \cdots k_m!</math> विशिष्ट संख्याएँ और तुल्यता वर्गों की संख्या है <math>\textstyle\frac{n!}{k_1!\, k_2! \cdots k_m!}</math>.


द्विपद गुणांक वह विशेष स्थिति है जहां k विषय चुने गए बिन में जाते हैं और शेष <math>n-k</math> विषय अवांछित बिन में जाते हैं।
द्विपद गुणांक वह विशेष स्थिति है जहां k विषय चुने गए बिन में जाते हैं और शेष <math>n-k</math> विषय अवांछित बिन में जाते हैं।
Line 237: Line 237:


==बाहरी संबंध==
==बाहरी संबंध==
* [https://www.topcoder.com/community/data-science/data-science-tutorials/basics-of-combinatorics/ Topcoder tutorial on combinatorics ]
* [https://www.topcoder.com/community/data-science/data-science-tutorials/basics-of-combinatorics/ Topcoder tutorial on combinatorics]
* [http://compprog.wordpress.com/2007/10/17/generating-combinations-1/ C code to generate all combinations of n elements chosen as k]
* [http://compprog.wordpress.com/2007/10/17/generating-combinations-1/ C code to generate all combinations of n elements chosen as k]
* [http://mathforum.org/library/drmath/sets/high_perms_combs.html Many Common types of permutation and combination math problems, with detailed solutions]
* [http://mathforum.org/library/drmath/sets/high_perms_combs.html Many Common types of permutation and combination math problems, with detailed solutions]

Revision as of 06:45, 25 March 2023

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