संयोजन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
गणित में | गणित में संयोजन सेट से वस्तुओं का चयन होता है जिसमें अलग-अलग सदस्य होते हैं, जैसे कि चयन का क्रम मायने नहीं रखता (क्रम[[परिवर्तन]] के विपरीत)। उदाहरण के लिए, तीन फल दिए गए हैं, जैसे सेब, संतरा और नाशपाती, दो के तीन संयोजन हैं जिन्हें इस सेट से निकाला जा सकता है: सेब और नाशपाती; सेब और संतरा; या नाशपाती और संतरा। अधिक औपचारिक रूप से, ''के''- [[सेट (गणित)]] ''एस'' का संयोजन ''एस'' के ''के'' विशिष्ट तत्वों का सबसेट है। इसलिए, दो संयोजन समान हैं यदि और केवल यदि प्रत्येक संयोजन में समान सदस्य हैं। (प्रत्येक सेट में सदस्यों की व्यवस्था कोई मायने नहीं रखती है।) यदि सेट में 'एन' तत्व हैं, तो 'के'-संयोजन की संख्या, द्वारा निरूपित <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> या के-चयन,<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 है। | ||
== के-संयोजनों की संख्या == | == के-संयोजनों की संख्या == | ||
{{main|Binomial coefficient}} | {{main|Binomial coefficient}} | ||
[[File:Combinations without repetition; 5 choose 3.svg|thumb|5-तत्व सेट के 3-तत्व सबसेट]]एन तत्वों के दिए गए सेट एस से के-संयोजनों की संख्या को अक्सर प्राथमिक संयोजक ग्रंथों में दर्शाया जाता है <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> और पोलिश ग्रंथ{{citation needed|date=April 2012}}). वही संख्या हालांकि कई अन्य गणितीय संदर्भों में होती है, जहां इसे द्वारा निरूपित किया जाता है <math>\tbinom nk</math> (अक्सर n चुनें k के रूप में पढ़ा जाता है); विशेष रूप से यह [[द्विपद सूत्र]] में | [[File:Combinations without repetition; 5 choose 3.svg|thumb|5-तत्व सेट के 3-तत्व सबसेट]]एन तत्वों के दिए गए सेट एस से के-संयोजनों की संख्या को अक्सर प्राथमिक संयोजक ग्रंथों में दर्शाया जाता है <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> और पोलिश ग्रंथ{{citation needed|date=April 2012}}). वही संख्या हालांकि कई अन्य गणितीय संदर्भों में होती है, जहां इसे द्वारा निरूपित किया जाता है <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 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 के लिए। यह | 0 ≤ k ≤ n के लिए। यह समरूपता व्यक्त करता है जो द्विपद सूत्र से स्पष्ट है, और इस तरह के संयोजन के [[पूरक (सेट सिद्धांत)]] को ले कर के-संयोजनों के संदर्भ में भी समझा जा सकता है, जो {{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 तत्वों का चयन करके | अंतिम सूत्र को 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>, ये क्रमशः | साथ में बुनियादी मामले <math>\tbinom n0=1=\tbinom nn</math>, ये क्रमशः ही सेट (पास्कल के त्रिकोण में पंक्ति) से संयोजनों की क्रमिक गणना की अनुमति देते हैं, बढ़ते आकारों के सेटों के k-संयोजनों की, और निश्चित आकार के पूरक के साथ संयोजनों की {{nowrap|''n'' − ''k''}}. | ||
=== गिनती संयोजनों का उदाहरण === | === गिनती संयोजनों का उदाहरण === | ||
विशिष्ट उदाहरण के रूप में, मानक बावन कार्ड डेक से संभव पांच-कार्ड हाथों की संख्या की गणना कर सकते हैं:<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 75: | Line 75: | ||
&= 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"> {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> | ||
| 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: | ||
=== के-संयोजनों की [[गणना]] === | === के-संयोजनों की [[गणना]] === | ||
कोई निश्चित क्रम में n तत्वों के दिए गए सेट S के सभी k-संयोजनों की गणना कर सकता है, जो | कोई निश्चित क्रम में n तत्वों के दिए गए सेट S के सभी k-संयोजनों की गणना कर सकता है, जो अंतराल से आक्षेप स्थापित करता है <math>\tbinom nk</math> उन के-संयोजनों के सेट के साथ पूर्णांक। यह मानते हुए कि S को स्वयं ऑर्डर किया गया है, उदाहरण के लिए S = { 1, 2, ..., n }, इसके 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 संयोजनों की गणना करने के कई तरीके हैं। | K संयोजनों की गणना करने के कई तरीके हैं। तरीका है 2 से कम सभी बाइनरी नंबरों पर जाना<sup>एन</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|Multiset coefficient}} | {{See also|Multiset coefficient}} | ||
k- 'पुनरावृत्ति के साथ संयोजन', या k- 'मल्टीकॉम्बिनेशन', या आकार k का 'मल्टीसेट' आकार n के सेट S से k के सेट द्वारा दिया जाता है, जो आवश्यक रूप से S के अलग-अलग तत्व नहीं होते हैं, जहाँ क्रम में नहीं लिया जाता है खाता: दो अनुक्रम ही मल्टीसेट को परिभाषित करते हैं यदि शर्तों को अनुमति देकर दूसरे से प्राप्त किया जा सकता है। दूसरे शब्दों में, यह n तत्वों के सेट से k तत्वों का नमूना है जो डुप्लिकेट (यानी, प्रतिस्थापन के साथ) की अनुमति देता है, लेकिन अलग-अलग ऑर्डरिंग (जैसे {2,1,2} = {1,2,2}) की अवहेलना करता है। एस के प्रत्येक तत्व के लिए इंडेक्स को संबद्ध करें और एस के तत्वों को वस्तुओं के प्रकार के रूप में सोचें, फिर हम बता सकते हैं <math>x_i</math> बहुउपसमुच्चय में प्रकार I के तत्वों की संख्या को निरूपित करें। आकार 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> | ||
| Line 107: | Line 107: | ||
<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> द्विपद गुणांक के संदर्भ में भी दिया जा सकता है: | |||
<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 180: | Line 180: | ||
{{See also|Binomial coefficient#Sum of coefficients row}} | {{See also|Binomial coefficient#Sum of coefficients row}} | ||
सभी k के लिए k-संयोजनों की संख्या n तत्वों के | सभी k के लिए k-संयोजनों की संख्या n तत्वों के सेट के सबसेट की संख्या है। यह देखने के कई तरीके हैं कि यह संख्या 2 है<sup>एन</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 196: | Line 196: | ||
*7 - 111 | *7 - 111 | ||
== संभावना: | == संभावना: यादृच्छिक संयोजन का नमूना लेना == | ||
किसी दिए गए सेट या सूची से | किसी दिए गए सेट या सूची से यादृच्छिक संयोजन चुनने के लिए विभिन्न [[एल्गोरिदम]] हैं। बड़े नमूना आकारों के लिए [[अस्वीकृति नमूनाकरण]] बेहद धीमा है। आकार एन की आबादी से कुशलता से के-संयोजन का चयन करने का तरीका आबादी के प्रत्येक तत्व में पुन: प्रयास करना है, और प्रत्येक चरण में उस तत्व को गतिशील रूप से बदलती संभावना के साथ चुनें <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>. | ||
द्विपद गुणांक वह विशेष मामला है जहां k आइटम चुने गए बिन में जाते हैं और शेष <math>n-k</math> आइटम अनचाहे बिन में जाते हैं: | द्विपद गुणांक वह विशेष मामला है जहां k आइटम चुने गए बिन में जाते हैं और शेष <math>n-k</math> आइटम अनचाहे बिन में जाते हैं: | ||
Revision as of 05:29, 25 March 2023
गणित में संयोजन सेट से वस्तुओं का चयन होता है जिसमें अलग-अलग सदस्य होते हैं, जैसे कि चयन का क्रम मायने नहीं रखता (क्रमपरिवर्तन के विपरीत)। उदाहरण के लिए, तीन फल दिए गए हैं, जैसे सेब, संतरा और नाशपाती, दो के तीन संयोजन हैं जिन्हें इस सेट से निकाला जा सकता है: सेब और नाशपाती; सेब और संतरा; या नाशपाती और संतरा। अधिक औपचारिक रूप से, के- सेट (गणित) एस का संयोजन एस के के विशिष्ट तत्वों का सबसेट है। इसलिए, दो संयोजन समान हैं यदि और केवल यदि प्रत्येक संयोजन में समान सदस्य हैं। (प्रत्येक सेट में सदस्यों की व्यवस्था कोई मायने नहीं रखती है।) यदि सेट में 'एन' तत्व हैं, तो 'के'-संयोजन की संख्या, द्वारा निरूपित या , द्विपद गुणांक के बराबर है
जिसे कारख़ाने का का उपयोग करके लिखा जा सकता है