संयोजन (साहचर्य)

For other uses of "संयोजन", see संयोजन (disambiguation).

गणित में, पूर्णांक n का संयोजन धनात्मक पूर्णांक के अनुक्रम के योग के रूप में n लिखने की विधि है। इस प्रकार दो अनुक्रम जो अपने पदों के क्रम में भिन्न होते हैं, उनके योग की विभिन्न रचनाओं को परिभाषित करते हैं, जबकि उन्हें उस संख्या के समान विभाजन (संख्या सिद्धांत) को परिभाषित करने के लिए माना जाता है। इस प्रकार प्रत्येक पूर्णांक में परिमित रूप से अनेक विशिष्ट रचनाएँ होती हैं। इस प्रकार ऋणात्मक संख्याओं का कोई संघटन नहीं होता है, किन्तु 0 का संघटन होता है, प्रत्येक धनात्मक पूर्णांक n में 2ⁿ⁻¹ विशिष्ट रचनाएँ होती है।

3 बिट बाइनरी अंक प्रणाली और 4 की रचनाओं के मध्य विक्षेप

पूर्णांक n की अशक्त रचना n की रचना के समान है, किन्तु अनुक्रम की नियमो को शून्य होने की अनुमति देती है: इस प्रकार यह अनुक्रम के योग के रूप में n लिखने का विधि है गैर-ऋणात्मक पूर्णांकों का परिणामस्वरूप प्रत्येक धनात्मक पूर्णांक असीम रूप से कई अशक्त रचनाओं को स्वीकार करता है (यदि उनकी लंबाई सीमित नहीं है)। इस प्रकार किसी अशक्त रचना के अंत में कई पद 0 जोड़ने को सामान्यतः अलग अशक्त रचना को परिभाषित करने के लिए नहीं माना जाता है; इस प्रकार दूसरे शब्दों में, अशक्त रचनाओं को नियमो 0 द्वारा अनिश्चित काल तक विस्तारित माना जाता है।

सामान्यीकरण करने के लिए, (गैर-ऋणात्मक या धनात्मक) पूर्णांकों के उपसमुच्चय a के लिए पूर्णांक n की a-प्रतिबंधित रचना, 'में या अधिक तत्वों का क्रमबद्ध संग्रह है। इस प्रकार 'a जिसका योग n है |

उदाहरण

6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
की 32 रचनाएँ। . .
1 + 5
6

6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
3 + 1 + 1 + 1
के 11 विभाजन। . .
3 + 3
6

5 की सोलह रचनाएँ हैं:

• 5
• 4+1
• 3+2
• 3 + 1 + 1
• 2+3
• 2 + 2 + 1
• 2 + 1 + 2
• 2 + 1 + 1 + 1
• 1+4
• 1 + 3 + 1
• 1+2+2
• 1 + 2 + 1 + 1
• 1 + 1 + 3
• 1 + 1 + 2 + 1
• 1 + 1 + 1 + 2
• 1 + 1 + 1 + 1 + 1.

इसकी तुलना 5 के सात विभाजनों से करें:

• 5
• 4+1
• 3+2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1.

रचनाओं के अंशों पर अंकुश लगाना संभव है। उदाहरण के लिए 5 की पाँच रचनाएँ अलग-अलग शब्दों में हैं:

• 5
• 4+1
• 3+2
• 2+3
• 1+4.

इसकी तुलना 5 के तीन विभाजनों के साथ अलग-अलग शब्दों में करें:

• 5
• 4+1
• 3+2.

रचनाओं की संख्या

n +1 से k +1 क्रमित विभाजनों की रचनाओं की संख्या पास्कल के त्रिकोण का निर्माण करती है

n की {1,2}-प्रतिबंधित रचनाओं को गिनने के लिए फाइबोनैचि अनुक्रम का उपयोग करना, उदाहरण के लिए, समय में या दो कदम उठाते हुए, लंबाई n की सीढ़ी पर चढ़ने के विधि की संख्या

परंपरागत रूप से संवृत्त रचना को 0 की एकमात्र रचना के रूप में गिना जाता है, और ऋणात्मक पूर्णांकों की कोई रचना नहीं होती है।

वहाँ 2ⁿ⁻¹ n ≥ 1 की रचनाएँ है; यहाँ प्रमाण है:

सरणी के प्रत्येक n − 1 बॉक्स में या तो प्लस चिह्न या अल्पविराम लगता है

${\big (}\,\overbrace {1\,\square \,1\,\square \,\ldots \,\square \,1\,\square \,1} ^{n}\,{\big )}$

इस प्रकार n की अद्वितीय रचना तैयार करता है। इसके विपरीत, n की प्रत्येक रचना धन और अल्पविराम का निर्धारण निर्धारित करती है। चूँकि n − 1 बाइनरी विकल्प हैं, परिणाम इस प्रकार है। इसी तर्क से पता चलता है कि पुर्णतः k भागों (एक 'k-रचना') में n की रचनाओं की संख्या द्विपद गुणांक ${n-1 \choose k-1}$ द्वारा दी गई है . ध्यान दें कि भागों की सभी संभावित संख्याओं का योग करने पर हमें 2^n-1 प्राप्त होता है n की रचनाओं की कुल संख्या के रूप में:

$\sum _{k=1}^{n}{n-1 \choose k-1}=2^{n-1}.$

अशक्त रचनाओं के लिए, संख्या ${n+k-1 \choose k-1}={n+k-1 \choose n}$ है, क्योंकि n + k की प्रत्येक k-संरचना नियम के अनुसार n की अशक्त संरचना से मेल खाती है

$a_{1}+a_{2}+\ldots +a_{k}=n+k\quad \mapsto \quad (a_{1}-1)+(a_{2}-1)+\ldots +(a_{k}-1)=n$

इस सूत्र से यह पता चलता है कि पुर्णतः k भागों में n की अशक्त रचनाओं की संख्या k - 1 की पुर्णतः n + 1 भागों में अशक्त रचनाओं की संख्या के समान है।

a-प्रतिबंधित रचनाओं के लिए पुर्णतः k भागों में n की रचनाओं की संख्या विस्तारित द्विपद (या बहुपद) गुणांक द्वारा दी गई है ${\binom {k}{n}}_{(1)_{a\in A}}=[x^{n}]\left(\sum _{a\in A}x^{a}\right)^{k}$,

जहां वर्गाकार कोष्ठक $x^{n}$ के गुणांक के निष्कर्षण को दर्शाते हैं इसके बाद आने वाले बहुपद में उपयोग किया जाता है।

सजातीय बहुपद

सदिश समष्टि का आयाम $K[x_{1},\ldots ,x_{n}]_{d}$ क्षेत्र K पर n चरों में घात d के सजातीय बहुपद का n भागों में d की अशक्त रचनाओं की संख्या है। इस प्रकार वास्तव में, समिष्ट का आधार एकपदी के समुच्चय $x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ द्वारा दिया जाता है ऐसा है कि $d_{1}+\ldots +d_{n}=d$. प्रतिपादकों के बाद से $d_{i}$ शून्य होने की अनुमति है, इस प्रकार ऐसे एकपदी की संख्या d की अशक्त रचनाओं की संख्या के समान है।

यह भी देखें

• स्टार्स और बार (संयोजक)

संदर्भ

• Heubach, Silvia; Mansour, Toufik (2009). Combinatorics of Compositions and Words. Discrete Mathematics and its Applications. Boca Raton, Florida: CRC Press. ISBN 978-1-4200-7267-9. Zbl 1184.68373.

बाहरी संबंध

• Partition and composition calculator