संयोजन

This article is about the mathematics of selecting part of a collection. For other uses, see संयोजन (disambiguation).

"COMBIN" and "nCr" redirect here. For other uses, see Combin (disambiguation) and NCR (disambiguation).

गणित में, एक संयोजन एक सेट से वस्तुओं का चयन होता है जिसमें अलग-अलग सदस्य होते हैं, जैसे कि चयन का क्रम मायने नहीं रखता (क्रमपरिवर्तन के विपरीत)। उदाहरण के लिए, तीन फल दिए गए हैं, जैसे एक सेब, एक संतरा और एक नाशपाती, दो के तीन संयोजन हैं जिन्हें इस सेट से निकाला जा सकता है: एक सेब और एक नाशपाती; एक सेब और एक संतरा; या एक नाशपाती और एक संतरा। अधिक औपचारिक रूप से, एक के-एक सेट (गणित) एस का संयोजन एस के के विशिष्ट तत्वों का एक सबसेट है। इसलिए, दो संयोजन समान हैं यदि और केवल यदि प्रत्येक संयोजन में समान सदस्य हैं। (प्रत्येक सेट में सदस्यों की व्यवस्था कोई मायने नहीं रखती है।) यदि सेट में 'एन' तत्व हैं, तो 'के'-संयोजन की संख्या, द्वारा निरूपित $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!$. समुच्चय S के सभी k-संयोजनों के समुच्चय को प्राय: निरूपित किया जाता है $\textstyle {\binom {S}{k}}$.

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

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

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

Main article: Binomial coefficient

5-तत्व सेट के 3-तत्व सबसेट

एन तत्वों के दिए गए सेट एस से के-संयोजनों की संख्या को अक्सर प्राथमिक संयोजक ग्रंथों में दर्शाया जाता है $C(n,k)$, या भिन्नरूप द्वारा जैसे $C_{k}^{n}$, ${}_{n}C_{k}$, ${}^{n}C_{k}$, $C_{n,k}$ या और भी $C_{n}^{k}$ (अंतिम रूप फ्रेंच, रोमानियाई, रूसी, चीनी में मानक है और पोलिश ग्रंथ). वही संख्या हालांकि कई अन्य गणितीय संदर्भों में होती है, जहां इसे द्वारा निरूपित किया जाता है ${\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$$

क > एन के लिए।

यह देखने के लिए कि ये गुणांक एस से के-संयोजनों की गणना करते हैं, पहले एन विशिष्ट चर एक्स के संग्रह पर विचार कर सकते हैं_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 + X)ⁿ, कोई (पहले से दिए गए बुनियादी मामलों के अलावा) पुनरावर्तन संबंध का उपयोग कर सकता है

$${\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},$$

0 <के <एन के लिए, जो इस प्रकार है (1 + X)ⁿ = (1 + X)^{n − 1}(1 + X); इससे पास्कल के त्रिभुज का निर्माण होता है।

व्यक्तिगत द्विपद गुणांक निर्धारित करने के लिए, सूत्र का उपयोग करना अधिक व्यावहारिक है

$${\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.$$

अंश n के n|k-क्रमपरिवर्तनों के क्रमचय#k-क्रमपरिवर्तनों की संख्या देता है, अर्थात, S के k विशिष्ट तत्वों के अनुक्रमों की, जबकि हर ऐसे k-क्रमपरिवर्तनों की संख्या देता है जो समान k-संयोजन देते हैं जब आदेश की अनदेखी की जाती है।

जब k n/2 से अधिक हो जाता है, तो उपरोक्त सूत्र में अंश और भाजक के लिए सामान्य गुणक होते हैं, और उन्हें रद्द करने से संबंध प्राप्त होता है

$${\binom {n}{k}}={\binom {n}{n-k}},$$

0 ≤ k ≤ n के लिए। यह एक समरूपता व्यक्त करता है जो द्विपद सूत्र से स्पष्ट है, और इस तरह के संयोजन के पूरक (सेट सिद्धांत) को ले कर के-संयोजनों के संदर्भ में भी समझा जा सकता है, जो एक (n − k)-संयोजन।

अंत में एक सूत्र है जो इस समरूपता को सीधे प्रदर्शित करता है, और याद रखने में आसान होने का गुण है:

$${\binom {n}{k}}={\frac {n!}{k!(n-k)!}},$$

जहाँ n! n का क्रमगुणन दर्शाता है। यह पिछले सूत्र से भाजक और अंश को गुणा करके प्राप्त किया जाता है (n − k) !, तो यह निश्चित रूप से उस सूत्र से कम्प्यूटेशनल रूप से कम कुशल है।

अंतिम सूत्र को S के सभी तत्वों के n! क्रमचय पर विचार करके सीधे समझा जा सकता है। ऐसा प्रत्येक क्रमचय अपने पहले k तत्वों का चयन करके एक k-संयोजन देता है। कई डुप्लिकेट चयन हैं: एक दूसरे के बीच पहले k तत्वों का कोई भी संयुक्त क्रमपरिवर्तन, और एक दूसरे के बीच अंतिम (n− k) तत्वों का एक ही संयोजन उत्पन्न करता है; यह सूत्र में विभाजन की व्याख्या करता है।

उपरोक्त सूत्रों से तीनों दिशाओं में पास्कल के त्रिभुज में सन्निकट संख्याओं के बीच संबंधों का अनुसरण करें:

$${\binom {n}{k}}={\begin{cases}{\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\{\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\{\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}.$$

साथ में बुनियादी मामले ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$, ये क्रमशः एक ही सेट (पास्कल के त्रिकोण में एक पंक्ति) से संयोजनों की क्रमिक गणना की अनुमति देते हैं, बढ़ते आकारों के सेटों के k-संयोजनों की, और निश्चित आकार के पूरक के साथ संयोजनों की n − k.

गिनती संयोजनों का उदाहरण

एक विशिष्ट उदाहरण के रूप में, एक मानक बावन कार्ड डेक से संभव पांच-कार्ड हाथों की संख्या की गणना कर सकते हैं:

$${52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.$$

वैकल्पिक रूप से कोई फैक्टोरियल के संदर्भ में सूत्र का उपयोग कर सकता है और हर में कारकों के हिस्सों के विरुद्ध अंश में कारकों को रद्द कर सकता है, जिसके बाद केवल शेष कारकों का गुणन आवश्यक है:

$${\begin{alignedat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}\times {\cancel {47!}}}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\\[5pt]&={\frac {(26\times {\cancel {2}})\times (17\times {\cancel {3}})\times (10\times {\cancel {5}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\[5pt]&={26\times 17\times 10\times 49\times 12}\\[5pt]&=2{,}598{,}960.\end{alignedat}}$$

एक अन्य वैकल्पिक संगणना, पहले के समकक्ष, लेखन पर आधारित है

$${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}},$$

जो देता है

$${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.$$

निम्नलिखित क्रम में मूल्यांकन करते समय, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, इसकी गणना केवल पूर्णांक अंकगणित का उपयोग करके की जा सकती है। इसका कारण यह है कि जब प्रत्येक विभाजन होता है, तो उत्पन्न होने वाला मध्यवर्ती परिणाम अपने आप में एक द्विपद गुणांक होता है, इसलिए कोई अवशेष कभी नहीं होता है।

सरलीकरण किए बिना फैक्टोरियल के मामले में सममित सूत्र का उपयोग करना एक व्यापक गणना देता है:

$${\begin{aligned}{52 \choose 5}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\[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\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960.\end{aligned}}$$

के-संयोजनों की गणना

कोई निश्चित क्रम में n तत्वों के दिए गए सेट S के सभी k-संयोजनों की गणना कर सकता है, जो एक अंतराल से एक आक्षेप स्थापित करता है ${\tbinom {n}{k}}$ उन के-संयोजनों के सेट के साथ पूर्णांक। यह मानते हुए कि S को स्वयं ऑर्डर किया गया है, उदाहरण के लिए S = { 1, 2, ..., n }, इसके k-संयोजनों को ऑर्डर करने की दो स्वाभाविक संभावनाएँ हैं: पहले उनके सबसे छोटे तत्वों की तुलना करके (जैसा कि ऊपर दिए गए चित्र में है) या तुलना करके उनके सबसे बड़े तत्व पहले। बाद वाले विकल्प का लाभ यह है कि एस में एक नया सबसे बड़ा तत्व जोड़ने से गणना के शुरुआती हिस्से में बदलाव नहीं आएगा, लेकिन पिछले वाले के बाद बड़े सेट के नए के-संयोजन जोड़ें। इस प्रक्रिया को दोहराते हुए, कभी भी बड़े सेटों के k-संयोजनों के साथ गणना को अनिश्चित काल तक बढ़ाया जा सकता है। यदि इसके अलावा पूर्णांकों के अंतराल को 0 से शुरू करने के लिए लिया जाता है, तो गणना में किसी दिए गए स्थान i पर k-संयोजन की गणना i से आसानी से की जा सकती है, और इस प्रकार प्राप्त होने वाली आपत्ति संयोजन संख्या प्रणाली के रूप में जानी जाती है। इसे कम्प्यूटेशनल गणित में रैंक/रैंकिंग और अनरैंकिंग के रूप में भी जाना जाता है। K संयोजनों की गणना करने के कई तरीके हैं। एक तरीका है 2 से कम सभी बाइनरी नंबरों पर जाना^एन. उन संख्याओं को चुनें जिनमें k नॉनज़रो बिट्स हों, हालाँकि यह छोटे n के लिए भी बहुत अक्षम है (उदाहरण के लिए n = 20 को लगभग एक मिलियन नंबरों पर जाने की आवश्यकता होगी जबकि k = 10 के लिए अनुमत k संयोजनों की अधिकतम संख्या लगभग 186 हजार है)। ऐसी संख्या में इन 1 बिट्स की स्थिति सेट {1, ..., n} का एक विशिष्ट k-संयोजन है। एक और सरल, तेज़ तरीका चयनित तत्वों के k इंडेक्स नंबरों को ट्रैक करना है, {0 .. k−1} (शून्य-आधारित) या {1 .. k} (एक-आधारित) से शुरू होकर पहले अनुमत k-संयोजन के रूप में और फिर बार-बार अंतिम अनुक्रमणिका संख्या में वृद्धि करके अगले अनुमत k-संयोजन पर जाना यदि यह n-1 (शून्य-आधारित) या n (एक-आधारित) या अंतिम अनुक्रमणिका संख्या x से कम है जो अनुक्रमणिका संख्या से कम है यदि ऐसा कोई इंडेक्स मौजूद है तो इसके बाद माइनस एक और इंडेक्स नंबर को x के बाद {x+1, x+2, ...} पर रीसेट करना।

पुनरावृत्ति के साथ संयोजनों की संख्या

See also: Multiset coefficient

एक k- 'पुनरावृत्ति के साथ संयोजन', या k- 'मल्टीकॉम्बिनेशन', या आकार k का 'मल्टीसेट' आकार n के एक सेट S से k के एक सेट द्वारा दिया जाता है, जो आवश्यक रूप से S के अलग-अलग तत्व नहीं होते हैं, जहाँ क्रम में नहीं लिया जाता है खाता: दो अनुक्रम एक ही मल्टीसेट को परिभाषित करते हैं यदि शर्तों को अनुमति देकर दूसरे से प्राप्त किया जा सकता है। दूसरे शब्दों में, यह n तत्वों के एक सेट से k तत्वों का एक नमूना है जो डुप्लिकेट (यानी, प्रतिस्थापन के साथ) की अनुमति देता है, लेकिन अलग-अलग ऑर्डरिंग (जैसे {2,1,2} = {1,2,2}) की अवहेलना करता है। एस के प्रत्येक तत्व के लिए एक इंडेक्स को संबद्ध करें और एस के तत्वों को वस्तुओं के प्रकार के रूप में सोचें, फिर हम बता सकते हैं $x_{i}$ एक बहुउपसमुच्चय में प्रकार I के तत्वों की संख्या को निरूपित करें। आकार k के बहुउपसमुच्चय की संख्या डायोफैंटाइन समीकरण के गैर-ऋणात्मक पूर्णांक (इसलिए शून्य की अनुमति) समाधानों की संख्या है:

$$x_{1}+x_{2}+\ldots +x_{n}=k.$$

यदि S में n अवयव हैं, तो ऐसे k-multisubsets की संख्या को इसके द्वारा निरूपित किया जाता है

$$\left(\!\!{\binom {n}{k}}\!\!\right),$$

एक अंकन जो द्विपद गुणांक के अनुरूप है जो k-उपसमुच्चय की गणना करता है। यह व्यंजक, n बहुचयन k, द्विपद गुणांक के संदर्भ में भी दिया जा सकता है:

$$\left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.$$

स्टार्स और बार्स (कॉम्बिनेटरिक्स) के रूप में जाने जाने वाले प्रतिनिधित्व का उपयोग करके इस संबंध को आसानी से सिद्ध किया जा सकता है।

Proof

उपरोक्त डायोफैंटाइन समीकरण का एक समाधान द्वारा दर्शाया जा सकता है $x_{1}$ सितारे, एक विभाजक (एक बार), फिर $x_{2}$ अधिक सितारे, एक और विभाजक, और इसी तरह। इस प्रतिनिधित्व में तारों की कुल संख्या k है और बार की संख्या n - 1 है (चूंकि n भागों में पृथक्करण के लिए n-1 विभाजक की आवश्यकता होती है)। इस प्रकार, k + n - 1 (या n + k - 1) प्रतीकों (सितारों और बार) की एक स्ट्रिंग एक समाधान के अनुरूप होती है यदि स्ट्रिंग में k तारे हैं। किसी भी समाधान को k में से चुनकर प्रदर्शित किया जा सकता है k + n − 1 सितारों को रखने की स्थिति और शेष पदों को सलाखों से भरना। उदाहरण के लिए समाधान $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ समीकरण का $x_{1}+x_{2}+x_{3}+x_{4}=10$ (n = 4 और k = 10) द्वारा दर्शाया जा सकता है

$$\bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .$$

ऐसे तारों की संख्या 10 तारों को 13 स्थितियों में रखने के तरीकों की संख्या है, ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$ जो 4 अवयवों वाले समुच्चय के 10-बहुसमुच्चयों की संख्या है।

7-सेट (बाएं) के 3-उपसमुच्चय और 5-सेट (दाएं) के तत्वों वाले 3-मल्टीसेट के बीच ऑब्जेक्शन।
यह दर्शाता है कि ${\textstyle {\binom {7}{3}}=\left(\!\!{\binom {5}{3}}\!\!\right)}$.

जैसा कि द्विपद गुणांकों के साथ होता है, इन बहुविकल्पी व्यंजकों के बीच कई संबंध होते हैं। उदाहरण के लिए, के लिए $n\geq 1,k\geq 0$,

$$\left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).$$

यह पहचान उपरोक्त प्रतिनिधित्व में तारों और बारों के आदान-प्रदान से होती है।

बहुउपसमुच्चयों की गिनती का उदाहरण

उदाहरण के लिए, यदि आपके पास चुनने के लिए मेनू में चार प्रकार के डोनट्स (n = 4) हैं और आप तीन डोनट्स (k = 3) चाहते हैं, तो पुनरावृत्ति के साथ डोनट्स चुनने के तरीकों की संख्या की गणना इस प्रकार की जा सकती है

$$\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.$$

इस परिणाम को समुच्चय S = {1,2,3,4} के सभी 3-बहुसमुच्चयों को सूचीबद्ध करके सत्यापित किया जा सकता है। इसे निम्न तालिका में प्रदर्शित किया गया है। दूसरा कॉलम आपके द्वारा वास्तव में चुने गए डोनट्स को सूचीबद्ध करता है, तीसरा कॉलम गैर-नकारात्मक पूर्णांक समाधान दिखाता है $[x_{1},x_{2},x_{3},x_{4}]$ समीकरण का $x_{1}+x_{2}+x_{3}+x_{4}=3$ और अंतिम स्तंभ तारों और पट्टियों को समाधान का प्रतिनिधित्व देता है।

No.	3-multiset	Eq. solution	Stars and bars
1	{1,1,1}	[3,0,0,0]	$\bigstar \bigstar \bigstar |||$
2	{1,1,2}	[2,1,0,0]	$\bigstar \bigstar |\bigstar ||$
3	{1,1,3}	[2,0,1,0]	$\bigstar \bigstar ||\bigstar |$
4	{1,1,4}	[2,0,0,1]	$\bigstar \bigstar |||\bigstar$
5	{1,2,2}	[1,2,0,0]	$\bigstar |\bigstar \bigstar ||$
6	{1,2,3}	[1,1,1,0]	$\bigstar |\bigstar |\bigstar |$
7	{1,2,4}	[1,1,0,1]	$\bigstar |\bigstar ||\bigstar$
8	{1,3,3}	[1,0,2,0]	$\bigstar ||\bigstar \bigstar |$
9	{1,3,4}	[1,0,1,1]	$\bigstar ||\bigstar |\bigstar$
10	{1,4,4}	[1,0,0,2]	$\bigstar |||\bigstar \bigstar$
11	{2,2,2}	[0,3,0,0]	$|\bigstar \bigstar \bigstar ||$
12	{2,2,3}	[0,2,1,0]	$|\bigstar \bigstar |\bigstar |$
13	{2,2,4}	[0,2,0,1]	$|\bigstar \bigstar ||\bigstar$
14	{2,3,3}	[0,1,2,0]	$|\bigstar |\bigstar \bigstar |$
15	{2,3,4}	[0,1,1,1]	$|\bigstar |\bigstar |\bigstar$
16	{2,4,4}	[0,1,0,2]	$|\bigstar ||\bigstar \bigstar$
17	{3,3,3}	[0,0,3,0]	$||\bigstar \bigstar \bigstar |$
18	{3,3,4}	[0,0,2,1]	$||\bigstar \bigstar |\bigstar$
19	{3,4,4}	[0,0,1,2]	$||\bigstar |\bigstar \bigstar$
20	{4,4,4}	[0,0,0,3]	$|||\bigstar \bigstar \bigstar$

== सभी k == के लिए k- संयोजनों की संख्या

See also: Binomial coefficient § Sum of coefficients row

सभी k के लिए k-संयोजनों की संख्या n तत्वों के एक सेट के सबसेट की संख्या है। यह देखने के कई तरीके हैं कि यह संख्या 2 है^एन. संयोजनों के संदर्भ में, ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$, जो द्विपद गुणांक की nवीं पंक्ति (0 से गिनती) का योग है # पास्कल के त्रिकोण में गुणांक पंक्ति का योग। इन संयोजनों (उपसमुच्चयों) को 0 से 2 तक गिने जाने वाले आधार 2 संख्याओं के सेट के 1 अंकों द्वारा गिना जाता हैⁿ − 1, जहां प्रत्येक अंक स्थिति n के सेट से एक आइटम है।

1 से 3 तक की संख्या वाले 3 कार्ड दिए गए हैं, खाली सेट सहित 8 अलग-अलग संयोजन (उपसमुच्चय) हैं:

$$|\{\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\}|=2^{3}=8$$

आधार 2 अंकों के रूप में इन सबसेट (उसी क्रम में) का प्रतिनिधित्व करना:

• 0 - 000
• 1 - 001
• 2 - 010
• 3 - 011
• 4 - 100
• 5 - 101
• 6 - 110
• 7 - 111

संभावना: एक यादृच्छिक संयोजन का नमूना लेना

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

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

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

$${n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}},$$

जहाँ n वस्तुओं की संख्या है, m डिब्बे की संख्या है, और $k_{i}$ बिन i में जाने वाली वस्तुओं की संख्या है।

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

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

$${\binom {n}{k}}={n \choose k,n-k}={\frac {n!}{k!(n-k)!}}.$$

यह भी देखें

• द्विपद गुणांक
• साहचर्य
• ब्लॉक डिजाइन
• केसर ग्राफ
• क्रमचय विषयों की सूची
• मल्टीसेट
• पास्कल का त्रिकोण
• क्रमपरिवर्तन
• संभावना
• सबसेट

संदर्भ

• Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 978-0-88385-333-7
• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pearson Prentice Hall, ISBN 978-0-13-602040-0
• Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
• Mazur, David R. (2010), Combinatorics: A Guided Tour, Mathematical Association of America, ISBN 978-0-88385-762-5
• Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs 14, Mathematical Association of America

बाहरी संबंध

• Topcoder tutorial on combinatorics
• C code to generate all combinations of n elements chosen as k
• Many Common types of permutation and combination math problems, with detailed solutions
• The Unknown Formula For combinations when choices can be repeated and order does not matter
• Combinations with repetitions (by: Akshatha AG and Smitha B)
• The dice roll with a given sum problem An application of the combinations with repetition to rolling multiple dice