संयोजन: 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>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>
Line 6: Line 6:
संयोजन 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-चयन होंगे:  में दो सेब,  में दो संतरे, और  में दो नाशपाती।
संयोजन 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 है।
यद्यपि संयोजनों की पूरी सूची लिखने के लिए तीन फलों का समूह काफी छोटा था, यह अव्यावहारिक हो जाता है क्योंकि समूह का आकार बढ़ जाता है। उदाहरण के लिए,  [[हाथ (पोकर)]] को 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 के रूप में पढ़ा जाता है); विशेष रूप से यह [[द्विपद सूत्र]] में  गुणांक के रूप में होता है, इसलिए इसका नाम 'द्विपद गुणांक' है। कोई परिभाषित कर सकता है <math>\tbinom nk</math> सभी प्राकृत संख्याओं 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 24: Line 24:


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


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


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


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


=== गिनती संयोजनों का उदाहरण ===
=== गिनती संयोजनों का उदाहरण ===
Line 95: Line 95:
=== के-संयोजनों की [[गणना]] ===
=== के-संयोजनों की [[गणना]] ===


कोई निश्चित क्रम में 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>
कोई निश्चित क्रम में 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 संयोजनों की गणना करने के कई तरीके हैं।  तरीका है 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, ...} पर रीसेट करना।
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>
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 118: Line 118:
{{Hidden end}}
{{Hidden end}}


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


<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right).</math>
<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right).</math>
Line 180: Line 180:
{{See also|Binomial coefficient#Sum of coefficients row}}
{{See also|Binomial coefficient#Sum of coefficients row}}


सभी 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 के सेट से  आइटम है।
सभी 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 अलग-अलग संयोजन (उपसमुच्चय) हैं:


<math display="block">| \{ \{\}  ;  \{1\}  ;  \{2\}  ;  \{1, 2\} ; \{3\}  ;  \{1, 3\}  ;  \{2, 3\}  ;  \{1, 2, 3\} \}| = 2^3 = 8</math>
<math display="block">| \{ \{\}  ;  \{1\}  ;  \{2\}  ;  \{1, 2\} ; \{3\}  ;  \{1, 3\}  ;  \{2, 3\}  ;  \{1, 2, 3\} \}| = 2^3 = 8</math>
आधार 2 अंकों के रूप में इन सबसेट (उसी क्रम में) का प्रतिनिधित्व करना:
आधार 2 अंकों के रूप में इन सबसमूह (उसी क्रम में) का प्रतिनिधित्व करना:


*0 - 000
*0 - 000
Line 198: Line 198:
== संभावना:  यादृच्छिक संयोजन का नमूना लेना ==
== संभावना:  यादृच्छिक संयोजन का नमूना लेना ==


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


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


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


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


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


द्विपद गुणांक वह विशेष मामला है जहां k आइटम चुने गए बिन में जाते हैं और शेष <math>n-k</math> आइटम अनचाहे बिन में जाते हैं:
द्विपद गुणांक वह विशेष मामला है जहां k आइटम चुने गए बिन में जाते हैं और शेष <math>n-k</math> आइटम अनचाहे बिन में जाते हैं:

Revision as of 05:31, 25 March 2023

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

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