संयोजन: Difference between revisions

Revision as of 15:58, 29 March 2023

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

{\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},

जिसे भाज्य का उपयोग करके

\textstyle {\frac {n!}{k!(n-k)!}}

लिखा जा सकता है। जब कभी भी

k\leq n

और कौन सा कब शून्य है

k>n

. यह सूत्र इस तथ्य से प्राप्त किया जा सकता है कि n सदस्यों के समुच्चय S के प्रत्येक k-संयोजन में है

k!

क्रमपरिवर्तन तो

P_{k}^{n}=C_{k}^{n}\times k!

या

C_{k}^{n}=P_{k}^{n}/k!

^[1] समुच्चय S के सभी k-संयोजनों के समुच्चय को प्राय: निरूपित किया जाता है

\textstyle {\binom {S}{k}}

.

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

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

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

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

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

(1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},

जिससे यह स्पष्ट होता है,

{\binom {n}{0}}={\binom {n}{n}}=1,

और आगे,

{\binom {n}{k}}=0

K > N के लिए।

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

\prod _{s\in S}(1+X_{s});

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

द्विपद गुणांकों की स्पष्ट रूप से विभिन्न विधियों से गणना की जा सकती है। विस्तार के लिए उन स

[1]

[2]

[3]

[4]

[5]

[6]

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

Anonymous

Search

संयोजन: Difference between revisions

Namespaces

More

Page actions

Revision as of 15:58, 29 March 2023

Contents

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