संयोजन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(24 intermediate revisions by 4 users not shown)
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>\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 display="block"> \binom nk = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1},</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-चयन होंगे।
जिसे [[ कारख़ाने का | भाज्य]] का उपयोग करके <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-चयन होंगे।
यद्यपि संयोजनों की पूरी सूची लिखने के लिए तीन फलों का समूह काफी छोटा था। यह अव्यावहारिक हो जाता है क्योंकि समूह का आकार बढ़ जाता है। उदाहरण के लिए, [[हाथ (पोकर)]] को 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">\binom{n}{0} = \binom{n}{n} = 1,</math>और आगे,<math display="block">\binom{n}{k} = 0</math>K > N के लिए इस प्रकार प्रकट कर सकते हैं।
 
<math display="block">(1 + X)^n = \sum_{k\geq0}\binom{n}{k} X^k,</math>
जिससे यह स्पष्ट होता है
 
<math display="block">\binom{n}{0} = \binom{n}{n} = 1,</math>
और आगे,
 
<math display="block">\binom{n}{k} = 0</math>
K > N के लिए।


यह देखने के लिए कि ये गुणांक S से K-संयोजनों की गणना करते हैं, पहले N विशिष्ट चर X<sub>''s''</sub> के संग्रह पर विचार कर सकते हैं S के तत्वों द्वारा लेबल किया गया है और S के सभी तत्वों पर गुणन का विस्तार करें।
यह देखने के लिए कि ये गुणांक S से K-संयोजनों की गणना करते हैं, पहले N विशिष्ट चर X<sub>''s''</sub> के संग्रह पर विचार कर सकते हैं S के तत्वों द्वारा लेबल किया गया है और S के सभी तत्वों पर गुणन का विस्तार करें।<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-संयोजनों की संख्या के बराबर रहता हैं।


<math display="block">\prod_{s\in S}(1+X_s);</math>
द्विपद गुणांकों की स्पष्ट रूप से विभिन्न विधियों से गणना की जा सकती है। विस्तार के लिए उन सभी को प्राप्त करने के लिए {{nowrap|(1 + ''X'')<sup>''n''</sup>}}, कोई पहले से दिए गए मूलभूत स्थितियों के अतिरिक्त पुनरावर्तन संबंध का उपयोग कर सकता है।<math display="block">\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k},</math>0 <K <N के लिए, जो इस प्रकार है {{nowrap|(1 + ''X'')<sup>''n''</sup> }}={{nowrap| (1 + ''X'')<sup>''n'' − 1</sup>(1 + ''X'')}}; इससे पास्कल के त्रिभुज का निर्माण होता है।
इसमें 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>}}, कोई पहले से दिए गए मूलभूत स्थितियों के अतिरिक्त पुनरावर्तन संबंध का उपयोग कर सकता है।
व्यक्तिगत द्विपद गुणांक निर्धारित करने के लिए, सूत्र का उपयोग करना अधिक व्यावहारिक है<math display="block">\binom nk = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}.</math>अंश n के n|k-क्रमपरिवर्तनों के क्रमचय k-क्रम परिवर्तनों की संख्या देता है, अर्थात, S के k विशिष्ट तत्वों के अनुक्रमों की है, जबकि प्रत्येक ऐसे k-क्रम परिवर्तनों की संख्या देता है जो समान k-संयोजन देते हैं जब आदेश की अनदेखी की जाती है।


<math display="block">\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k},</math>
0 <K <N के लिए, जो इस प्रकार है {{nowrap|(1 + ''X'')<sup>''n''</sup> }}={{nowrap| (1 + ''X'')<sup>''n'' − 1</sup>(1 + ''X'')}}; इससे पास्कल के त्रिभुज का निर्माण होता है।


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


<math display="block">\binom nk = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}.</math>
अंत में सूत्र है जो इस समरूपता को सीधे प्रदर्शित करता है और याद रखने में आसान होने का गुण है।<math display="block"> \binom nk = \frac{n!}{k!(n-k)!},</math>जहाँ n<nowiki>!</nowiki> का क्रमगुणनकलन विधि n दर्शाता है। यह पिछले सूत्र से भाजक और अंश को गुणा करके प्राप्त किया जाता है {{nowrap|(''n'' − ''k'')}}!, तो यह निश्चित रूप से उस सूत्र से कम्प्यूटेशनल रूप से कम कुशल है।
अंश n के n|k-क्रमपरिवर्तनों के क्रमचय k-क्रम परिवर्तनों की संख्या देता है, अर्थात, S के k विशिष्ट तत्वों के अनुक्रमों की है, जबकि प्रत्येक ऐसे k-क्रम परिवर्तनों की संख्या देता है जो समान k-संयोजन देते हैं जब आदेश की अनदेखी की जाती है।


जब k n/2 से अधिक हो जाता है, तो उपरोक्त सूत्र में अंश और [[भाजक]] के लिए सामान्य गुणक होते हैं और उन्हें निरसित करने से संबंध प्राप्त होता है


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


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


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


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


उपरोक्त सूत्रों से तीनों दिशाओं में पास्कल के त्रिभुज में सन्निकट संख्याओं के बीच संबंधों का अनुसरण करें।
उपरोक्त सूत्रों से तीनों दिशाओं में पास्कल के त्रिभुज में सन्निकट संख्याओं के बीच संबंधों का अनुसरण करते हैं।<math display="block">
 
<math display="block">
\binom nk =
\binom nk =
\begin{cases}
\begin{cases}
Line 57: Line 33:
\binom {n-1}{k-1} \frac nk &\quad \text{if } n, k > 0
\binom {n-1}{k-1} \frac nk &\quad \text{if } n, k > 0
\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} =  
 
2{,}598{,}960.</math>वैकल्पिक रूप से कोई फैक्टोरियल के संदर्भ में सूत्र का उपयोग कर सकता है और प्रत्येक में कारकों के भागों के विरुद्ध अंश में कारकों को निरसित कर सकता है, जिसके बाद केवल शेष कारकों का गुणन आवश्यक है।<math display="block">\begin{alignat}{2}
<math display="block"> {52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311{,}875{,}200}{120} =  
2{,}598{,}960.</math>
वैकल्पिक रूप से कोई फैक्टोरियल के संदर्भ में सूत्र का उपयोग कर सकता है और प्रत्येक में कारकों के भागों के विरुद्ध अंश में कारकों को निरसित कर सकता है, जिसके बाद केवल शेष कारकों का गुणन आवश्यक है।
<math display="block">\begin{alignat}{2}
   {52 \choose 5}
   {52 \choose 5}
     &= \frac{52!}{5!47!} \\[5pt]
     &= \frac{52!}{5!47!} \\[5pt]
Line 74: Line 45:
     &= {26\times17\times10\times49\times12} \\[5pt]
     &= {26\times17\times10\times49\times12} \\[5pt]
     &= 2{,}598{,}960.
     &= 2{,}598{,}960.
\end{alignat}</math>
\end{alignat}</math>अन्य वैकल्पिक संगणना पहले के समकक्ष लेखन पर आधारित है<math display="block"> {n \choose k} = \frac { ( n - 0 ) }1 \times \frac { ( n - 1 ) }2 \times \frac { ( n - 2 ) }3 \times \cdots \times \frac { ( n - (k - 1) ) }k,</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 display="block"> {n \choose k} = \frac { ( n - 0 ) }1 \times \frac { ( n - 1 ) }2 \times \frac { ( n - 2 ) }3 \times \cdots \times \frac { ( n - (k - 1) ) }k,</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 display="block">
निम्नलिखित क्रम में मूल्यांकन करते समय, {{math|52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5}}, इसकी गणना केवल पूर्णांक अंकगणित का उपयोग करके की जा सकती है। इसका कारण यह है कि जब प्रत्येक विभाजन होता है, तो उत्पन्न होने वाला मध्यवर्ती परिणाम अपने आप में  द्विपद गुणांक होता है, इसलिए कोई अवशेष कभी नहीं होता है।
 
सरलीकरण किए अतिरिक्त फैक्टोरियल के स्थितियों में सममित सूत्र का उपयोग करना व्यापक गणना देता है।
 
<math display="block">
\begin{align}
\begin{align}
  {52 \choose 5} &= \frac{n!}{k!(n-k)!} = \frac{52!}{5!(52-5)!} = \frac{52!}{5!47!} \\[6pt]
  {52 \choose 5} &= \frac{n!}{k!(n-k)!} = \frac{52!}{5!(52-5)!} = \frac{52!}{5!47!} \\[6pt]
&= \tfrac{80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000} \\[6pt]
&= \tfrac{80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000} \\[6pt]
&= 2{,}598{,}960.
&= 2{,}598{,}960.
\end{align}</math>
\end{align}</math>'''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, ...} पर फिर से स्थापित कर देते है।
=== 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, ...} पर रीसेट करना।


== पुनरावृत्ति के साथ संयोजनों की संख्या ==
== पुनरावृत्ति के साथ संयोजनों की संख्या ==
{{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}) की अवहेलना करता है। S के प्रत्येक तत्व के लिए अनुक्रमणिका को संबद्ध करें और एस के तत्वों को वस्तुओं के प्रकार के रूप में सोचें, फिर हम बता सकते हैं <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>यदि S में n अवयव हैं, तो ऐसे k-बहु उपसमुच्चय की संख्या को इसके द्वारा निरूपित किया जाता है।<math display="block">\left(\!\!\binom{n}{k}\!\!\right),</math>अंकन जो द्विपद गुणांक के अनुरूप है जो 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>स्टार्स और बार्स साहचर्य के रूप में जाने जाने वाले प्रतिनिधित्व का उपयोग करके इस संबंध को सुगमता से सिद्ध किया जा सकता है।<ref>In the article [[Stars and bars (combinatorics)]] the roles of {{mvar|n}} and {{mvar|k}} are reversed.</ref>{{Hidden begin |showhide=left|title=प्रमाण|titlestyle = background:lightgray;}}
 
<math display="block">x_1 + x_2 + \ldots + x_n = k.</math>
यदि S में n अवयव हैं, तो ऐसे k-बहु उपसमुच्चय की संख्या को इसके द्वारा निरूपित किया जाता है।
 
<math display="block">\left(\!\!\binom{n}{k}\!\!\right),</math>
अंकन जो द्विपद गुणांक के अनुरूप है जो 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>
स्टार्स और बार्स साहचर्य के रूप में जाने जाने वाले प्रतिनिधित्व का उपयोग करके इस संबंध को आसानी से सिद्ध किया जा सकता है।<ref>In the article [[Stars and bars (combinatorics)]] the roles of {{mvar|n}} and {{mvar|k}} are reversed.</ref>  
{{Hidden begin |showhide=left|title=प्रमाण|titlestyle = background:lightgray;}}
उपरोक्त डायोफैंटाइन समीकरण का एक समाधान द्वारा दर्शाया जा सकता है <math>x_1</math> सितारे, एक विभाजक (एक बार), फिर <math>x_2</math> अधिक सितारे, एक और विभाजक, और इसी तरह। इस प्रतिनिधित्व में तारों की कुल संख्या k है और बार की संख्या n - 1 है (चूंकि n भागों में पृथक्करण के लिए n-1 विभाजक की आवश्यकता होती है)। इस प्रकार, k + n - 1 (या n + k - 1) प्रतीकों (सितारों और बार) की एक स्ट्रिंग एक समाधान के अनुरूप होती है यदि स्ट्रिंग में k तारे हैं। किसी भी समाधान को k में से चुनकर प्रदर्शित किया जा सकता है {{nobreak|''k'' + ''n'' − 1}} सितारों को रखने की स्थिति और शेष पदों को सलाखों से भरना। उदाहरण के लिए समाधान <math>x_1 = 3, x_2 = 2, x_3 = 0, x_4 = 5</math> समीकरण का <math> x_1 + x_2 + x_3 + x_4 = 10</math> (n = 4 और k = 10) द्वारा दर्शाया जा सकता है<ref>{{harvnb|Benjamin|Quinn|2003|loc=pp. 71 &ndash;72}}</ref>
उपरोक्त डायोफैंटाइन समीकरण का एक समाधान द्वारा दर्शाया जा सकता है <math>x_1</math> सितारे, एक विभाजक (एक बार), फिर <math>x_2</math> अधिक सितारे, एक और विभाजक, और इसी तरह। इस प्रतिनिधित्व में तारों की कुल संख्या k है और बार की संख्या n - 1 है (चूंकि n भागों में पृथक्करण के लिए n-1 विभाजक की आवश्यकता होती है)। इस प्रकार, k + n - 1 (या n + k - 1) प्रतीकों (सितारों और बार) की एक स्ट्रिंग एक समाधान के अनुरूप होती है यदि स्ट्रिंग में k तारे हैं। किसी भी समाधान को k में से चुनकर प्रदर्शित किया जा सकता है {{nobreak|''k'' + ''n'' − 1}} सितारों को रखने की स्थिति और शेष पदों को सलाखों से भरना। उदाहरण के लिए समाधान <math>x_1 = 3, x_2 = 2, x_3 = 0, x_4 = 5</math> समीकरण का <math> x_1 + x_2 + x_3 + x_4 = 10</math> (n = 4 और k = 10) द्वारा दर्शाया जा सकता है<ref>{{harvnb|Benjamin|Quinn|2003|loc=pp. 71 &ndash;72}}</ref>


Line 117: Line 67:
{{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>यह पहचान उपरोक्त प्रतिनिधित्व में तारों और बारों के आदान-प्रदान से होती है।<ref>{{harvnb|Benjamin|Quinn|2003|loc=p. 72 (identity 145)}}</ref>
 
<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right).</math>
यह पहचान उपरोक्त प्रतिनिधित्व में तारों और बारों के आदान-प्रदान से होती है।<ref>{{harvnb|Benjamin|Quinn|2003|loc=p. 72 (identity 145)}}</ref>
=== बहुउपसमुच्चय की गिनती का उदाहरण ===
=== बहुउपसमुच्चय की गिनती का उदाहरण ===
उदाहरण के लिए, यदि आपके पास चुनने के लिए मेनू में चार प्रकार के डोनट्स (n = 4) हैं और आप तीन डोनट्स (k = 3) चाहते हैं, तो पुनरावृत्ति के साथ डोनट्स चुनने के विधियों की संख्या की गणना इस प्रकार की जा सकती है
उदाहरण के लिए, यदि आपके पास चुनने के लिए मेनू में चार प्रकार के डोनट्स (n = 4) हैं और आप तीन डोनट्स (k = 3) चाहते हैं, तो पुनरावृत्ति के साथ डोनट्स चुनने के विधियों की संख्या की गणना इस प्रकार की जा सकती है।<math display="block">\left(\!\!\binom{4}{3}\!\!\right) = \binom{4+3-1}3 = \binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20.</math>इस परिणाम को समुच्चय S = {1,2,3,4} के सभी 3-बहुसमुच्चयों को सूचीबद्ध करके सत्यापित किया जा सकता है। इसे निम्न तालिका में प्रदर्शित किया गया है।<ref>{{harvnb|Benjamin|Quinn|2003|loc=p. 71}}</ref> दूसरा स्तंभ आपके द्वारा वास्तव में चुने गए डोनट्स को सूचीबद्ध करता है, तीसरा स्तंभ गैर-नकारात्मक पूर्णांक समाधान दिखाता है <math>[x_1,x_2,x_3,x_4]</math> समीकरण का <math>x_1 + x_2 + x_3 + x_4 = 3</math> और अंतिम स्तंभ तारों और पट्टियों को समाधान का प्रतिनिधित्व देता है।<ref>{{harvnb|Mazur|2010|loc=p. 10}} where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.</ref>
 
<math display="block">\left(\!\!\binom{4}{3}\!\!\right) = \binom{4+3-1}3 = \binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20.</math>
इस परिणाम को समुच्चय S = {1,2,3,4} के सभी 3-बहुसमुच्चयों को सूचीबद्ध करके सत्यापित किया जा सकता है। इसे निम्न तालिका में प्रदर्शित किया गया है।<ref>{{harvnb|Benjamin|Quinn|2003|loc=p. 71}}</ref> दूसरा कॉलम आपके द्वारा वास्तव में चुने गए डोनट्स को सूचीबद्ध करता है, तीसरा कॉलम गैर-नकारात्मक पूर्णांक समाधान दिखाता है <math>[x_1,x_2,x_3,x_4]</math> समीकरण का <math>x_1 + x_2 + x_3 + x_4 = 3</math> और अंतिम स्तंभ तारों और पट्टियों को समाधान का प्रतिनिधित्व देता है।<ref>{{harvnb|Mazur|2010|loc=p. 10}} where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.</ref>
 
{| class="wikitable" style="margin-left: auto; margin-right: auto; border; none"
{| class="wikitable" style="margin-left: auto; margin-right: auto; border; none"
|-
|-
Line 172: Line 115:
|}
|}


सभी k के लिए k- संयोजनों की संख्या
'''सभी k के लिए k- संयोजनों की संख्या'''
{{See also|Binomial coefficient#Sum of coefficients row}}
{{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 के समूह से  आइटम है।


1 से 3 तक की संख्या वाले 3 कार्ड दिए गए हैं, [[खाली सेट|खाली समूह]] सहित 8 अलग-अलग संयोजन (उपसमुच्चय ) हैं:
सभी 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 के समूह से विषय है।
 
<math display="block">| \{ \{\}  ;  \{1\}  ;  \{2\}  ;  \{1, 2\} ; \{3\}  ;  \{1, 3\} \{2, 3\} ;  \{1, 2, 3\} \}| = 2^3 = 8</math>
आधार 2 अंकों के रूप में इन उपसमूह (उसी क्रम में) का प्रतिनिधित्व करना:


1 से 3 तक की संख्या वाले 3 टिकट दिए गए हैं, [[खाली सेट|खाली समूह]] सहित 8 अलग-अलग संयोजन उपसमुच्चय हैं।<math display="block">| \{ \{\}  ;  \{1\}  ;  \{2\}  ;  \{1, 2\} ; \{3\}  ;  \{1, 3\}  ;  \{2, 3\}  ;  \{1, 2, 3\} \}| = 2^3 = 8</math>आधार 2 अंकों के रूप में इन उपसमूह (उसी क्रम में) का प्रतिनिधित्व करना।
*0 - 000
*0 - 000
*1 - 001
*1 - 001
Line 191: Line 130:
*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>जहाँ n वस्तुओं की संख्या है, m डिब्बे की संख्या है, और <math>k_i</math> कोष्ठ i में जाने वाली वस्तुओं की संख्या है।


<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 में जाने वाली वस्तुओं की संख्या है।


यह देखने का  विधि  है कि यह समीकरण क्यों धारण करता है, पहले वस्तुओं को मनमाने ढंग से 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> आइटम अनचाहे बिन में जाते हैं।
यह देखने का विधि है कि यह समीकरण क्यों धारण करता है, पहले वस्तुओं को मनमाने ढंग से 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> है।


<math display="block"> \binom nk = {n \choose k, n-k} = \frac{n!}{k!(n-k)!}. </math>
द्विपद गुणांक वह विशेष स्थिति है जहां k विषय चुने गए कोष्ठ में जाते हैं और शेष <math>n-k</math> विषय अवांछित कोष्ठ में जाते हैं।<math display="block"> \binom nk = {n \choose k, n-k} = \frac{n!}{k!(n-k)!}. </math>


 
== यह भी देखें{{Portal|Mathematics}}==
== यह भी देखें ==
{{Portal|Mathematics}}
{{div col|colwidth=30em}}
{{div col|colwidth=30em}}
* द्विपद गुणांक
* द्विपद गुणांक
Line 237: Line 171:


==बाहरी संबंध==
==बाहरी संबंध==
* [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]
Line 243: Line 177:
* [http://dl.dropbox.com/u/7951257/easymath/Combinations%20with%20Repetitions.pdf Combinations with repetitions (by: Akshatha AG and Smitha B)]{{Dead link|date=November 2019 |bot=InternetArchiveBot |fix-attempted=yes }}
* [http://dl.dropbox.com/u/7951257/easymath/Combinations%20with%20Repetitions.pdf Combinations with repetitions (by: Akshatha AG and Smitha B)]{{Dead link|date=November 2019 |bot=InternetArchiveBot |fix-attempted=yes }}
* [http://www.lucamoroni.it/the-dice-roll-sum-problem/ The dice roll with a given sum problem] An application of the combinations with repetition to rolling multiple dice
* [http://www.lucamoroni.it/the-dice-roll-sum-problem/ The dice roll with a given sum problem] An application of the combinations with repetition to rolling multiple dice
[[Category: साहचर्य]]


[[Category: Machine Translated Page]]
[[Category:Accuracy disputes from April 2017]]
[[Category:All articles with dead external links]]
[[Category:Articles with dead external links from November 2019]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Articles with invalid date parameter in template]]
[[Category:Articles with permanently dead external links]]
[[Category:CS1 中文-language sources (zh)]]
[[Category:Created On 21/03/2023]]
[[Category:Created On 21/03/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Multi-column templates]]
[[Category:Pages using div col with small parameter]]
[[Category:Pages with empty portal template]]
[[Category:Pages with script errors]]
[[Category:Portal templates with redlinked portals]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates using TemplateData]]
[[Category:Templates using under-protected Lua modules]]
[[Category:Wikipedia fully protected templates|Div col]]
[[Category:साहचर्य]]

Latest revision as of 16:28, 27 April 2023

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

जिसे भाज्य का उपयोग करके लिखा जा सकता है। जब कभी भी और कौन सा कब शून्य है। यह सूत्र इस तथ्य से प्राप्त किया जा सकता है कि n सदस्यों के समुच्चय S के प्रत्येक k-संयोजन में है क्रमपरिवर्तन तो या [1] समुच्चय S के सभी k-संयोजनों के समुच्चय को प्राय: द्वारा निरूपित किया जाता है।

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

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

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

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

N तत्वों के दिए गए समूह एस से K-संयोजनों की संख्या को अधिकांशतः प्राथमिक संयोजक ग्रंथों में दर्शाया जाता है। , भिन्नरूप द्वारा जैसे , , , और भी अंतिम रूप फ्रेंच, रोमानियाई, रूसी, चीनी में मानक है[5][6] और पोलिश ग्रंथ। वही संख्या चूंकि कई अन्य गणितीय संदर्भों में होती है, जहां इसे द्वारा निरूपित किया जाता है अधिकांशतः n चुनें k के रूप में पढ़ा जाता है। विशेष रूप से यह द्विपद सूत्र में गुणांक के रूप में होता है, इसलिए इसका नाम 'द्विपद गुणांक' है।कलन विधि सभी प्राकृत संख्याओं k के साथ संबंध द्वारा परिभाषित कर सकता है,

जिससे यह स्पष्ट होता है,
और आगे,
K > N के लिए इस प्रकार प्रकट कर सकते हैं।

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

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

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

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

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

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


जब k n/2 से अधिक हो जाता है, तो उपरोक्त सूत्र में अंश और भाजक के लिए सामान्य गुणक होते हैं और उन्हें निरसित करने से संबंध प्राप्त होता है

0 ≤ k ≤ n के लिए। यह समरूपता व्यक्त करता है जो द्विपद सूत्र से स्पष्ट है, और इस प्रकार के संयोजन के पूरक (समूह सिद्धांत) को ले कर K-संयोजनों के संदर्भ में भी समझा जा सकता है, जो (nk)-संयोजन हैं।

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

जहाँ n! का क्रमगुणनकलन विधि n दर्शाता है। यह पिछले सूत्र से भाजक और अंश को गुणा करके प्राप्त किया जाता है (nk)!, तो यह निश्चित रूप से उस सूत्र से कम्प्यूटेशनल रूप से कम कुशल है।


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


उपरोक्त सूत्रों से तीनों दिशाओं में पास्कल के त्रिभुज में सन्निकट संख्याओं के बीच संबंधों का अनुसरण करते हैं।

साथ में मूलभूत स्थितियों , ये क्रमशः समूह पास्कल के त्रिकोण में पंक्ति से संयोजनों की क्रमिक गणना की अनुमति देते हैं, बढ़ते आकारों के समूहों के k-संयोजनों और निश्चित आकार के पूरक nk के साथ संयोजनों की जाती हैं।

गिनती संयोजनों का उदाहरण

विशिष्ट उदाहरण के रूप में, मानक बावन टिकट डेक से संभव पांच-टिकट हाथों की संख्या की गणना कर सकते हैं।[7]

वैकल्पिक रूप से कोई फैक्टोरियल के संदर्भ में सूत्र का उपयोग कर सकता है और प्रत्येक में कारकों के भागों के विरुद्ध अंश में कारकों को निरसित कर सकता है, जिसके बाद केवल शेष कारकों का गुणन आवश्यक है।
अन्य वैकल्पिक संगणना पहले के समकक्ष लेखन पर आधारित है
जो देता है,
निम्नलिखित क्रम में मूल्यांकन करते समय, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, इसकी गणना केवल पूर्णांक अंकगणित का उपयोग करके की जा सकती है। इसका कारण यह है कि जब प्रत्येक विभाजन होता है, तो उत्पन्न होने वाला मध्यवर्ती परिणाम अपने आप में द्विपद गुणांक होता है, इसलिए कोई अवशेष कभी नहीं होता है।


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

K-संयोजनों की गणना

कोई निश्चित क्रम में n तत्वों के दिए गए समूह S के सभी k-संयोजनों की गणना कर सकता है, जो अंतराल से आक्षेप स्थापित करता है , न K-संयोजनों के समूह के साथ पूर्णांक। यह मानते हुए कि S को स्वयं अनुक्रम किया गया है, उदाहरण के लिए S = { 1, 2, ..., n }, इसके k-संयोजनों को अनुक्रम करने की दो स्वाभाविक संभावनाएँ हैं। पहले उनके सबसे छोटे तत्वों की तुलना करके जैसा कि ऊपर दिए गए चित्र में है, तुलना करके उनके सबसे बड़े तत्व पहले। किया जाता हैं बइसकेवपश्चात विकल्पों का लाभ यह है कि एस में नया सबसे बड़ा तत्व जोड़ने से गणना के प्रारंभिक भागों में बदलाव नहीं आएगा, किन्तु पिछले वाले के बाद बड़े समूह के नए K-संयोजन जोड़ें। इस प्रक्रिया को दोहराते हुए, कभी भी बड़े समूहों के k-संयोजनों के साथ गणना को अनिश्चित काल तक बढ़ाया जा सकता है। यदि इसके अतिरिक्त पूर्णांकों के अंतराल को 0 से प्रारंभ करने के लिए लिया जाता है, तो गणना में किसी दिए गए स्थान i पर k-संयोजन की गणना i से सुगमता से की जा सकती है और इस प्रकार प्राप्त होने वाली आपत्ति संयोजन संख्या प्रणाली के रूप में जानी जाती है। इसे कम्प्यूटेशनल गणित में रैंक/रैंकिंग और अनरैंकिंग के रूप में भी जाना जाता है।[8][9] K संयोजनों की गणना करने के कई विधियाँ हैं। 2N से कम सभी बाइनरी नंबरों पर जाना। उन संख्याओं को चुनें जिनमें k अशून्य बिट्स हों, चूंकि यह छोटे n के लिए भी बहुत अक्षम है उदाहरण के लिए n = 20 को लगभग मिलियन नंबरों पर जाने की आवश्यकता होगी, जबकि k = 10 के लिए अनुमत k संयोजनों की अधिकतम संख्या लगभग 186 हजार है। ऐसी संख्या में इन 1 बिट्स की स्थिति समूह {1, ..., n} का विशिष्ट k-संयोजन है[10] और सरल, तेज़ विधि चयनित तत्वों के k अनुक्रमणिका नंबरों को ट्रैक करना है, {0 .. k−1} (शून्य-आधारित) या {1 .. k} -आधारित से प्रारंभ होकर पहले अनुमत k-संयोजन के रूप में और फिर बार-बार अंतिम अनुक्रमणिका संख्या में वृद्धि करके अगले अनुमत k-संयोजन पर जाना यदि यह n-1 (शून्य-आधारित) या n -आधारित अंतिम अनुक्रमणिका संख्या x से कम है, जो अनुक्रमणिका संख्या से कम है यदि ऐसा कोई अनुक्रमणिका उपस्तिथ है, तो इसके बाद ऋण और अनुक्रमणिका नंबर को x के बाद {x+1, x+2, ...} पर फिर से स्थापित कर देते है।

पुनरावृत्ति के साथ संयोजनों की संख्या

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

यदि S में n अवयव हैं, तो ऐसे k-बहु उपसमुच्चय की संख्या को इसके द्वारा निरूपित किया जाता है।
अंकन जो द्विपद गुणांक के अनुरूप है जो k-उपसमुच्चय की गणना करता है। यह व्यंजक, n बहुचयन k,[12] द्विपद गुणांक के संदर्भ में भी दिया जा सकता है।
स्टार्स और बार्स साहचर्य के रूप में जाने जाने वाले प्रतिनिधित्व का उपयोग करके इस संबंध को सुगमता से सिद्ध किया जा सकता है।[13]

प्रमाण

उपरोक्त डायोफैंटाइन समीकरण का एक समाधान द्वारा दर्शाया जा सकता है सितारे, एक विभाजक (एक बार), फिर अधिक सितारे, एक और विभाजक, और इसी तरह। इस प्रतिनिधित्व में तारों की कुल संख्या k है और बार की संख्या n - 1 है (चूंकि n भागों में पृथक्करण के लिए n-1 विभाजक की आवश्यकता होती है)। इस प्रकार, k + n - 1 (या n + k - 1) प्रतीकों (सितारों और बार) की एक स्ट्रिंग एक समाधान के अनुरूप होती है यदि स्ट्रिंग में k तारे हैं। किसी भी समाधान को k में से चुनकर प्रदर्शित किया जा सकता है k + n − 1 सितारों को रखने की स्थिति और शेष पदों को सलाखों से भरना। उदाहरण के लिए समाधान समीकरण का (n = 4 और k = 10) द्वारा दर्शाया जा सकता है[14]

ऐसे तारों की संख्या 10 तारों को 13 स्थितियों में रखने के तरीकों की संख्या है, जो 4 अवयवों वाले समुच्चय के 10-बहुसमुच्चयों की संख्या है।

7-समूह (बाएं) के 3-उपसमुच्चय और 5-समूह (दाएं) के तत्वों वाले 3-बहुसमूह के बीच असम्मति।
यह दर्शाता है कि .

जैसा कि द्विपद गुणांकों के साथ होता है, इन बहुविकल्पी व्यंजकों के बीच कई संबंध होते हैं। उदाहरण के लिए ,

यह पहचान उपरोक्त प्रतिनिधित्व में तारों और बारों के आदान-प्रदान से होती है।[15]

बहुउपसमुच्चय की गिनती का उदाहरण

उदाहरण के लिए, यदि आपके पास चुनने के लिए मेनू में चार प्रकार के डोनट्स (n = 4) हैं और आप तीन डोनट्स (k = 3) चाहते हैं, तो पुनरावृत्ति के साथ डोनट्स चुनने के विधियों की संख्या की गणना इस प्रकार की जा सकती है।

इस परिणाम को समुच्चय S = {1,2,3,4} के सभी 3-बहुसमुच्चयों को सूचीबद्ध करके सत्यापित किया जा सकता है। इसे निम्न तालिका में प्रदर्शित किया गया है।[16] दूसरा स्तंभ आपके द्वारा वास्तव में चुने गए डोनट्स को सूचीबद्ध करता है, तीसरा स्तंभ गैर-नकारात्मक पूर्णांक समाधान दिखाता है समीकरण का और अंतिम स्तंभ तारों और पट्टियों को समाधान का प्रतिनिधित्व देता है।[17]

नंबर 3-बहु समुच्चय सम समाधान सितारे और बार
1 {1,1,1} [3,0,0,0]
2 {1,1,2} [2,1,0,0]
3 {1,1,3} [2,0,1,0]
4 {1,1,4} [2,0,0,1]
5 {1,2,2} [1,2,0,0]
6 {1,2,3} [1,1,1,0]
7 {1,2,4} [1,1,0,1]
8 {1,3,3} [1,0,2,0]
9 {1,3,4} [1,0,1,1]
10 {1,4,4} [1,0,0,2]
11 {2,2,2} [0,3,0,0]
12 {2,2,3} [0,2,1,0]
13 {2,2,4} [0,2,0,1]
14 {2,3,3} [0,1,2,0]
15 {2,3,4} [0,1,1,1]
16 {2,4,4} [0,1,0,2]
17 {3,3,3} [0,0,3,0]
18 {3,3,4} [0,0,2,1]
19 {3,4,4} [0,0,1,2]
20 {4,4,4} [0,0,0,3]

सभी k के लिए k- संयोजनों की संख्या

सभी k के लिए k-संयोजनों की संख्या n तत्वों के समूह के उपसमूह की संख्या है। यह देखने के कई विधियाँ हैं कि यह संख्या 2N है। संयोजनों के संदर्भ में, , जो द्विपद गुणांक की n वीं पंक्ति 0 से गिनती का योग है। पास्कल के त्रिकोण में गुणांक पंक्ति का योग। इन संयोजनों उपसमुच्चय को 0 से 2 तक गिने जाने वाले आधार 2 संख्याओं के समूह के 1n − 1 अंकों द्वारा गिना जाता है, जहां प्रत्येक अंक स्थिति n के समूह से विषय है।

1 से 3 तक की संख्या वाले 3 टिकट दिए गए हैं, खाली समूह सहित 8 अलग-अलग संयोजन उपसमुच्चय हैं।

आधार 2 अंकों के रूप में इन उपसमूह (उसी क्रम में) का प्रतिनिधित्व करना।

  • 0 - 000
  • 1 - 001
  • 2 - 010
  • 3 - 011
  • 4 - 100
  • 5 - 101
  • 6 - 110
  • 7 - 111

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

किसी दिए गए सूची से यादृच्छिक संयोजन चुनने के लिए विभिन्न कलन विधि हैं। बड़े नमूना आकारों के लिए अस्वीकृति नमूनाकरण अत्यंत धीमा है। आकार N की आबादी से कुशलता से K-संयोजन का चयन करने का विधि आबादी के प्रत्येक तत्व में पुन: प्रयास करना है और प्रत्येक चरण में उस तत्व को गतिशील रूप से बदलती संभावना के साथ चुनें जाते हैं। दूसरा यादृच्छिक गैर-ऋणात्मक पूर्णांक से कम चुनना है और संयोजन संख्या प्रणाली का उपयोग करके इसे संयोजन में परिवर्तित करें।

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

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

जहाँ n वस्तुओं की संख्या है, m डिब्बे की संख्या है, और कोष्ठ i में जाने वाली वस्तुओं की संख्या है।


यह देखने का विधि है कि यह समीकरण क्यों धारण करता है, पहले वस्तुओं को मनमाने ढंग से 1 से n तक नंबर देना है और वस्तुओं को संख्याओं के साथ रखना है क्रम में पहले कोष्ठ में, वस्तुओं के साथ संख्याएँ क्रम में दूसरे कोष्ठ में, और इसी तरह। वहाँ हैं अलग-अलग नम्बर डालना, किन्तु उनमें से कई समतुल्य हैं, क्योंकि कोष्ठ में केवल वस्तुओं का समूह मतलब रखता है, इसमें उनका क्रम नहीं। प्रत्येक डिब्बे की सामग्री का प्रत्येक संयुक्त क्रमचय वस्तुओं को डिब्बे में डालने का समान विधि उत्पन्न करता है। परिणाम स्वरुप , प्रत्येक समकक्ष वर्ग में सम्मलित हैं विशिष्ट संख्याएँ और तुल्यता वर्गों की संख्या है।

द्विपद गुणांक वह विशेष स्थिति है जहां k विषय चुने गए कोष्ठ में जाते हैं और शेष विषय अवांछित कोष्ठ में जाते हैं।

यह भी देखें

टिप्पणियाँ

  1. Reichl, Linda E. (2016). "2.2. Counting Microscopic States". सांख्यिकीय भौतिकी में एक आधुनिक पाठ्यक्रम. WILEY-VCH. p. 30. ISBN 978-3-527-69048-0.
  2. Mazur 2010, p. 10
  3. Ryser 1963, p. 7 also referred to as an unordered selection.
  4. When the term combination is used to refer to either situation (as in (Brualdi 2010)) care must be taken to clarify whether sets or multisets are being discussed.
  5. पूर्णकालिक छात्र के लिए हाई स्कूल पाठ्यपुस्तक (आवश्यक) गणित पुस्तक II बी (in 中文) (2nd ed.). China: People's Education Press. June 2006. pp. 107–116. ISBN 978-7-107-19616-4.
  6. 人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press). People's Education Press. p. 21.
  7. Mazur 2010, p. 21
  8. Lucia Moura. "प्राथमिक मिश्रित वस्तुओं का निर्माण" (PDF). Site.uottawa.ca. Archived (PDF) from the original on 2022-10-09. Retrieved 2017-04-10.
  9. "SAGE : Subsets" (PDF). Sagemath.org. Retrieved 2017-04-10.
  10. "संयोजन - रोसेटा कोड". 23 October 2022.[user-generated source?]
  11. Brualdi 2010, p. 52
  12. Benjamin & Quinn 2003, p. 70
  13. In the article Stars and bars (combinatorics) the roles of n and k are reversed.
  14. Benjamin & Quinn 2003, pp. 71 –72
  15. Benjamin & Quinn 2003, p. 72 (identity 145)
  16. Benjamin & Quinn 2003, p. 71
  17. Mazur 2010, p. 10 where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.


संदर्भ


बाहरी संबंध