संयोजन: 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>, [[द्विपद गुणांक]] के बराबर है। | ||
<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>\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 कार्ड अलग-अलग हैं और हाथ में कार्ड का क्रम मतलब नहीं | यद्यपि संयोजनों की पूरी सूची लिखने के लिए तीन फलों का समूह काफी छोटा था। यह अव्यावहारिक हो जाता है क्योंकि समूह का आकार बढ़ जाता है। उदाहरण के लिए, [[हाथ (पोकर)]] को 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 के साथ संबंध द्वारा परिभाषित कर सकता है,<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 के | [[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 के लिए इस प्रकार प्रकट कर सकते हैं। | ||
यह देखने के लिए कि ये गुणांक 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> को समूह कर | यह देखने के लिए कि ये गुणांक 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-संयोजनों की संख्या के बराबर रहता हैं। | ||
द्विपद गुणांकों की स्पष्ट रूप से विभिन्न विधियों से गणना की जा सकती है। विस्तार के लिए उन सभी को प्राप्त करने के लिए {{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'')}}; इससे पास्कल के त्रिभुज का निर्माण होता है। | द्विपद गुणांकों की स्पष्ट रूप से विभिन्न विधियों से गणना की जा सकती है। विस्तार के लिए उन सभी को प्राप्त करने के लिए {{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'')}}; इससे पास्कल के त्रिभुज का निर्माण होता है। | ||
| Line 19: | Line 19: | ||
जब k n/2 से अधिक हो जाता है, तो उपरोक्त सूत्र में अंश और [[भाजक]] के लिए सामान्य गुणक होते हैं और उन्हें निरसित करने से संबंध प्राप्त होता है<math display="block"> \binom nk = \binom n{n-k},</math>0 ≤ k ≤ n के लिए। यह समरूपता व्यक्त करता है जो द्विपद सूत्र से स्पष्ट है, और इस प्रकार के संयोजन के [[पूरक (सेट सिद्धांत)|पूरक (समूह सिद्धांत)]] को ले कर K-संयोजनों के संदर्भ में भी समझा जा सकता है, जो {{nowrap|(''n'' − ''k'')}}- | जब 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!}{k!(n-k)!},</math>जहाँ n<nowiki>!</nowiki> का क्रमगुणनकलन विधिn दर्शाता है। यह पिछले सूत्र से भाजक और अंश को गुणा करके प्राप्त किया जाता है {{nowrap|(''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) तत्वों का ही संयोजन उत्पन्न करता है। यह सूत्र में विभाजन की व्याख्या करता है। | अंतिम सूत्र को S के सभी तत्वों के n<nowiki>!</nowiki> क्रमचय पर विचार करके सीधे समझा जा सकता है। ऐसा प्रत्येक क्रमचय अपने पहले k तत्वों का चयन करके k-संयोजन देता है। कई डुप्लिकेट चयन हैं, जो दूसरे के बीच पहले k तत्वों का कोई भी संयुक्त क्रम परिवर्तन और दूसरे के बीच अंतिम (n− k) तत्वों का ही संयोजन उत्पन्न करता है। यह सूत्र में विभाजन की व्याख्या करता है। | ||
उपरोक्त सूत्रों से तीनों दिशाओं में पास्कल के त्रिभुज में सन्निकट संख्याओं के बीच संबंधों का अनुसरण | उपरोक्त सूत्रों से तीनों दिशाओं में पास्कल के त्रिभुज में सन्निकट संख्याओं के बीच संबंधों का अनुसरण करते हैं।<math display="block"> | ||
\binom nk = | \binom nk = | ||
\begin{cases} | \begin{cases} | ||
| Line 33: | Line 34: | ||
\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>\tbinom n0=1=\tbinom nn</math>, ये क्रमशः समूह पास्कल के त्रिकोण में पंक्ति से संयोजनों की क्रमिक गणना की अनुमति देते हैं, बढ़ते आकारों के समूहों के k-संयोजनों और निश्चित आकार के पूरक | </math> | ||
साथ में मूलभूत स्थितियों <math>\tbinom n0=1=\tbinom nn</math>, ये क्रमशः समूह पास्कल के त्रिकोण में पंक्ति से संयोजनों की क्रमिक गणना की अनुमति देते हैं, बढ़ते आकारों के समूहों के k-संयोजनों और निश्चित आकार के पूरक {{nowrap|''n'' − ''k''}} के साथ संयोजनों की जाती हैं। | |||
=== गिनती संयोजनों का उदाहरण === | === गिनती संयोजनों का उदाहरण === | ||
| Line 56: | Line 60: | ||
कोई निश्चित क्रम में n तत्वों के दिए गए समूह S के सभी 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, ...} पर फिर से स्थापित कर देते है। | ||
== पुनरावृत्ति के साथ संयोजनों की संख्या == | == पुनरावृत्ति के साथ संयोजनों की संख्या == | ||
| Line 120: | Line 124: | ||
{{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 | सभी 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 अलग-अलग संयोजन उपसमुच्चय हैं।<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 अंकों के रूप में इन उपसमूह (उसी क्रम में) का प्रतिनिधित्व करना। | ||
| Line 135: | Line 139: | ||
== संभावना: यादृच्छिक संयोजन का नमूना लेना == | == संभावना: यादृच्छिक संयोजन का नमूना लेना == | ||
किसी दिए गए सूची से यादृच्छिक संयोजन चुनने के लिए विभिन्न [[एल्गोरिदम|कलन विधि]] हैं। बड़े नमूना आकारों के लिए [[अस्वीकृति नमूनाकरण]] अत्यंत धीमा है। आकार N की आबादी से कुशलता से K-संयोजन का चयन करने का विधि आबादी के प्रत्येक तत्व में पुन: प्रयास करना है और प्रत्येक चरण में उस तत्व को गतिशील रूप से बदलती संभावना | किसी दिए गए सूची से यादृच्छिक संयोजन चुनने के लिए विभिन्न [[एल्गोरिदम|कलन विधि]] हैं। बड़े नमूना आकारों के लिए [[अस्वीकृति नमूनाकरण]] अत्यंत धीमा है। आकार 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 में जाने वाली वस्तुओं की संख्या है। | ||
यह देखने का विधि है कि यह समीकरण क्यों धारण करता है, पहले वस्तुओं को मनमाने ढंग से 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> विशिष्ट संख्याएँ और तुल्यता वर्गों की संख्या | यह देखने का विधि है कि यह समीकरण क्यों धारण करता है, पहले वस्तुओं को मनमाने ढंग से 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> विषय अवांछित बिन में जाते हैं।<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> | ||
Revision as of 21:51, 30 March 2023
गणित में संयोजन समूह से वस्तुओं का चयन होता है, जिसमें अलग-अलग सदस्य होते हैं, जैसे कि चयन का क्रम मतलब नहीं रखता क्रम परिवर्तन के विपरीत हैं। उदाहरण के लिए, तीन फल दिए गए हैं, जैसे सेब, संतरा और नाशपाती, दो के तीन संयोजन हैं जिन्हें इस समूह से निकाला जा सकता है। सेब और नाशपाती, सेब और संतरा, नाशपाती और संतरा इत्यादि अधिक औपचारिक रूप से, K- समूह (गणित) S का संयोजन S के K विशिष्ट तत्वों का उपसमूह है। इसलिए, दो संयोजन समान हैं यदि और केवल यदि प्रत्येक संयोजन में समान सदस्य हैं। प्रत्येक समूह में सदस्यों की व्यवस्था कोई मतलब नहीं रखती है। यदि समूह में 'N' तत्व हैं, तो 'K'-संयोजन की संख्या, द्वारा निरूपित या , द्विपद गुणांक के बराबर है।
जिसे भाज्य का उपयोग करके लिखा जा सकता है। जब कभी भी और कौन सा कब शून्य है। यह सूत्र इस तथ्य से प्राप्त किया जा सकता है कि n सदस्यों के समुच्चय S के प्रत्येक k-संयोजन में है क्रमपरिवर्तन तो या