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

For other uses of "Composition", see Composition (disambiguation).

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

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

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

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

उदाहरण

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}-प्रतिबंधित रचनाओं को गिनने के लिए फाइबोनैचि अनुक्रम का उपयोग करना, for example, एक समय में एक या दो कदम उठाते हुए, लंबाई 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 भागों में कमजोर रचनाओं की संख्या के बराबर है।

ए-प्रतिबंधित रचनाओं के लिए, बिल्कुल 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