संयोजन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
== 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 + | यह देखने के लिए कि ये गुणांक 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">\binom{n}{ | द्विपद गुणांकों की स्पष्ट रूप से विभिन्न विधियों से गणना की जा सकती है। विस्तार के लिए उन सभी को प्राप्त करने के लिए {{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'')}}; इससे पास्कल के त्रिभुज का निर्माण होता है। | ||
<math display="block">\binom{n}{k} | व्यक्तिगत द्विपद गुणांक निर्धारित करने के लिए, सूत्र का उपयोग करना अधिक व्यावहारिक है<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">\ | जब 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'')}}!, तो यह निश्चित रूप से उस सूत्र से कम्प्यूटेशनल रूप से कम कुशल है। | |||
अंतिम सूत्र को S के सभी तत्वों के n<nowiki>!</nowiki> क्रमचय पर विचार करके सीधे समझा जा सकता है। ऐसा प्रत्येक क्रमचय अपने पहले k तत्वों का चयन करके k-संयोजन देता है। कई डुप्लिकेट चयन हैं, जो दूसरे के बीच पहले k तत्वों का कोई भी संयुक्त क्रम परिवर्तन और दूसरे के बीच अंतिम (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"> | सरलीकरण किए अतिरिक्त फैक्टोरियल के स्थितियों में सममित सूत्र का उपयोग करना व्यापक गणना देता है।<math display="block"> | ||
| Line 85: | Line 53: | ||
&= \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, ...} पर फिर से स्थापित कर देते है। | कोई निश्चित क्रम में 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 94: | Line 61: | ||
{{See also|मल्टीसेट गुणांक}} | {{See also|मल्टीसेट गुणांक}} | ||
k- 'पुनरावृत्ति के साथ संयोजन', k- 'बहुसंयोजन', आकार k का 'बहुसमूह' आकार n के समूह S से k के समूह द्वारा दिया जाता है, जो आवश्यक रूप से S के अलग-अलग तत्व नहीं होते हैं, जहाँ क्रम में नहीं लिया जाता है खाता: दो अनुक्रम ही बहुसमूह को परिभाषित करते हैं यदि शर्तों को अनुमति देकर दूसरे से प्राप्त किया जा सकता है। दूसरे शब्दों में, यह n तत्वों के समूह से k तत्वों का नमूना है जो डुप्लिकेट अर्थात, प्रतिस्थापन के साथ की अनुमति देता है, किन्तु अलग-अलग ऑर्डरिंग (जैसे {2,1,2} = {1,2,2}) की अवहेलना करता है। एस के प्रत्येक तत्व के लिए अनुक्रमणिका को संबद्ध करें और एस के तत्वों को वस्तुओं के प्रकार के रूप में सोचें, फिर हम बता सकते हैं <math>x_i</math> बहुउपसमुच्चय में प्रकार k तत्वों की संख्या को निरूपित करें। आकार k के बहुउपसमुच्चय की संख्या [[डायोफैंटाइन समीकरण]] के गैर-ऋणात्मक पूर्णांक इसलिए शून्य की अनुमति समाधानों की संख्या है।<ref>{{harvnb|Brualdi|2010|loc=p. 52}}</ref> | k- 'पुनरावृत्ति के साथ संयोजन', k- 'बहुसंयोजन', आकार k का 'बहुसमूह' आकार n के समूह S से k के समूह द्वारा दिया जाता है, जो आवश्यक रूप से S के अलग-अलग तत्व नहीं होते हैं, जहाँ क्रम में नहीं लिया जाता है खाता: दो अनुक्रम ही बहुसमूह को परिभाषित करते हैं यदि शर्तों को अनुमति देकर दूसरे से प्राप्त किया जा सकता है। दूसरे शब्दों में, यह n तत्वों के समूह से k तत्वों का नमूना है जो डुप्लिकेट अर्थात, प्रतिस्थापन के साथ की अनुमति देता है, किन्तु अलग-अलग ऑर्डरिंग (जैसे {2,1,2} = {1,2,2}) की अवहेलना करता है। एस के प्रत्येक तत्व के लिए अनुक्रमणिका को संबद्ध करें और एस के तत्वों को वस्तुओं के प्रकार के रूप में सोचें, फिर हम बता सकते हैं <math>x_i</math> बहुउपसमुच्चय में प्रकार k तत्वों की संख्या को निरूपित करें। आकार k के बहुउपसमुच्चय की संख्या [[डायोफैंटाइन समीकरण]] के गैर-ऋणात्मक पूर्णांक इसलिए शून्य की अनुमति समाधानों की संख्या है।<ref>{{harvnb|Brualdi|2010|loc=p. 52}}</ref><math display="block">x_1 + x_2 + \ldots + x_n = k.</math>यदि 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 –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 –72}}</ref> | ||
| Line 111: | Line 68: | ||
{{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 171: | Line 122: | ||
सभी k के लिए k-संयोजनों की संख्या n तत्वों के समूह के उपसमूह की संख्या है। यह देखने के कई विधियाँ हैं कि यह संख्या 2<sup>N</sup> है। संयोजनों के संदर्भ में, <math display="inline">\sum_{0\leq{k}\leq{n}}\binom n k = 2^n</math>, जो द्विपद गुणांक की n वीं पंक्ति 0 से गिनती का योग है। पास्कल के त्रिकोण में गुणांक पंक्ति का योग। इन संयोजनों उपसमुच्चय को 0 से 2 तक गिने जाने वाले [[आधार 2]] संख्याओं के समूह के 1 अंकों द्वारा गिना जाता है<sup>n</sup> − 1, जहां प्रत्येक अंक स्थिति n के समूह से विषय है। | सभी k के लिए k-संयोजनों की संख्या n तत्वों के समूह के उपसमूह की संख्या है। यह देखने के कई विधियाँ हैं कि यह संख्या 2<sup>N</sup> है। संयोजनों के संदर्भ में, <math display="inline">\sum_{0\leq{k}\leq{n}}\binom n k = 2^n</math>, जो द्विपद गुणांक की n वीं पंक्ति 0 से गिनती का योग है। पास्कल के त्रिकोण में गुणांक पंक्ति का योग। इन संयोजनों उपसमुच्चय को 0 से 2 तक गिने जाने वाले [[आधार 2]] संख्याओं के समूह के 1 अंकों द्वारा गिना जाता है<sup>n</sup> − 1, जहां प्रत्येक अंक स्थिति n के समूह से विषय है। | ||
1 से 3 तक की संख्या वाले 3 कार्ड दिए गए हैं, [[खाली सेट|खाली समूह]] सहित 8 अलग-अलग संयोजन उपसमुच्चय हैं। | 1 से 3 तक की संख्या वाले 3 कार्ड दिए गए हैं, [[खाली सेट|खाली समूह]] सहित 8 अलग-अलग संयोजन उपसमुच्चय हैं।<math display="block">| \{ \{\} ; \{1\} ; \{2\} ; \{1, 2\} ; \{3\} ; \{1, 3\} ; \{2, 3\} ; \{1, 2, 3\} \}| = 2^3 = 8</math>आधार 2 अंकों के रूप में इन उपसमूह (उसी क्रम में) का प्रतिनिधित्व करना। | ||
<math display="block">| \{ \{\} ; \{1\} ; \{2\} ; \{1, 2\} ; \{3\} ; \{1, 3\} ; \{2, 3\} ; \{1, 2, 3\} \}| = 2^3 = 8</math> | |||
आधार 2 अंकों के रूप में इन उपसमूह (उसी क्रम में) का प्रतिनिधित्व करना। | |||
*0 - 000 | *0 - 000 | ||
| Line 191: | Line 139: | ||
== वस्तुओं को डिब्बे में डालने के विधियों की संख्या == | == वस्तुओं को डिब्बे में डालने के विधियों की संख्या == | ||
संयोजन को वस्तुओं के दो समूहों के चयन के रूप में भी माना जा सकता है। वे जो चुने हुए बिन में जाते हैं और वे जो अवांछित बिन में जाते हैं। इसे किसी भी संख्या में डिब्बे के लिए सामान्यीकृत किया जा सकता है, जिसमें यह बाधा है कि प्रत्येक वस्तु को ठीक बिन में जाना चाहिए। वस्तुओं को डिब्बे में डालने के विधियों की संख्या बहुराष्ट्रीय प्रमेय द्वारा दी गई है वस्तुओं को डिब्बे में डालने के विधि। | संयोजन को वस्तुओं के दो समूहों के चयन के रूप में भी माना जा सकता है। वे जो चुने हुए बिन में जाते हैं और वे जो अवांछित बिन में जाते हैं। इसे किसी भी संख्या में डिब्बे के लिए सामान्यीकृत किया जा सकता है, जिसमें यह बाधा है कि प्रत्येक वस्तु को ठीक बिन में जाना चाहिए। वस्तुओं को डिब्बे में डालने के विधियों की संख्या बहुराष्ट्रीय प्रमेय द्वारा दी गई है वस्तुओं को डिब्बे में डालने के विधि।<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 में जाने वाली वस्तुओं की संख्या है। | |||
<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> | |||
== यह भी देखें | == यह भी देखें{{Portal|Mathematics}}== | ||
{{Portal|Mathematics}} | |||
{{div col|colwidth=30em}} | {{div col|colwidth=30em}} | ||
* द्विपद गुणांक | * द्विपद गुणांक | ||
Revision as of 16:08, 29 March 2023
गणित में संयोजन समूह से वस्तुओं का चयन होता है। जिसमें अलग-अलग सदस्य होते हैं, जैसे कि चयन का क्रम मतलब नहीं रखता क्रम परिव