प्रतीकात्मक विधि (कॉम्बिनेटरिक्स)

This article is about विश्लेषणात्मक संयोजन विज्ञान में विधि. For अपरिवर्तनीय सिद्धांत में विधि, see प्रतीकात्मक विधि.

संयोजक में, प्रतीकात्मक गणनात्मक संयोजक संयोजक की तकनीक है। यह वस्तुओं की आंतरिक संरचना का उपयोग करके उनके उत्पादन कार्यों के लिए सूत्र प्राप्त करता है। यह विधि अधिकतर फिलिप फ्लेजोलेट से जुड़ी हुई है और रॉबर्ट सेडगेविक (कंप्यूटर वैज्ञानिक), विश्लेषणात्मक संयोजक के साथ उनकी पुस्तक के भाग ए में विस्तृत है, जबकि शेष किताब बताती है कि स्पर्शोन्मुख होने के लिए जटिल विश्लेषण का उपयोग कैसे किया जाए और संबंधित जनरेटिंग फलन पर संभाव्य परिणाम देता है।

दो शताब्दियों के समय, जनरेटिंग फलन उनके गुणांकों पर संबंधित पुनरावृत्तियों के माध्यम से सामने आ रहे थे (जैसा कि डेनियल बर्नौली, लियोनहार्ड यूलर, आर्थर केली, अर्न्स्ट श्रोडर (गणितज्ञ) या श्रोडर के मौलिक कार्यों में देखा जा सकता है। श्रीनिवास रामानुजन, जॉन रिओर्डन (गणितज्ञ), डोनाल्ड नुथ, कॉमटेट) इसके पश्चात् धीरे-धीरे यह अनुभव हुआ कि सृजन कार्य प्रारंभिक असतत संयोजन वस्तुओं के कई अन्य तथ्यों को कैप्चर कर रहे थे, और यह अधिक प्रत्यक्ष औपचारिक विधि से किया जा सकता था: कुछ संयोजन संरचनाओं की पुनरावर्ती प्रकृति कुछ समरूपताओं के माध्यम से, संबंधित उत्पन्न करने वाले कार्यों पर उल्लेखनीय पहचान में अनुवाद करता है। जॉर्ज पोल्या|पोल्या के कार्यों के बाद, 1970 के दशक में इस भावना में और प्रगति की गई थी, जिसमें संयोजन वर्गों और उनके सृजन कार्यों को निर्दिष्ट करने के लिए भाषाओं का सामान्य उपयोग किया गया था, जैसा कि डोमिनिक फोटा और मार्सेल-पॉल शुट्ज़ेनबर्गर या शूट्ज़ेनबर्गर के कार्यों में पाया गया था। क्रमपरिवर्तन पर, प्रीफ़ैब्स पर बेंडर और गोल्डमैन, और आंद्रे जोयाल संयोजक प्रजातियों पर। ध्यान दें कि गणना में यह प्रतीकात्मक विधि ब्लिसार्ड की प्रतीकात्मक विधि से असंबंधित है, जो कि अम्ब्रल कैलकुलस का पुराना नाम है।

संयोजक में प्रतीकात्मक विधि, कॉम्बिनेटरियल संरचनाओं के कई विश्लेषणों का पहला चरण है, जिसके बाद तेजी से गणना योजनाएं, एसिम्प्टोटिक गुण और एसिम्प्टोटिक वितरण, यादृच्छिक पीढ़ी हो सकती हैं, ये सभी कंप्यूटर बीजगणित के माध्यम से स्वचालितकरण के लिए उपयुक्त हैं।

संयोजक संरचनाओं के वर्ग

जनरेटिंग फलन द्वारा दी गई वस्तुओं को n स्लॉट्स के समुच्चय में वितरित करने की समस्या पर विचार करें, जहां डिग्री n का क्रमपरिवर्तन समूह G, भरे हुए स्लॉट विन्यास के समतुल्य संबंध बनाने के लिए स्लॉट्स पर कार्य करता है, और विन्यास के जनरेटिंग फलन के बारे में पूछता है। इस तुल्यता संबंध के संबंध में विन्यास का वजन, जहां विन्यास का वजन स्लॉट में वस्तुओं के वजन का योग है। हम पहले बताएंगे कि लेबल किए गए और बिना लेबल वाले स्थिति में इस समस्या को कैसे हल किया जाए और संयोजक वर्ग के निर्माण को प्रेरित करने के लिए समाधान का उपयोग किया जाता है।

पोलिया गणना प्रमेय इस समस्या को बिना लेबल वाले स्थिति में हल करता है। मान लें कि f(z) वस्तुओं का सामान्य जनरेटिंग फलन (ओजीएफ) है, तो विन्यास का ओजीएफ प्रतिस्थापित चक्र सूचकांक द्वारा दिया जाता है

$Z(G)(f(z),f(z^{2}),\ldots ,f(z^{n})).$

लेबल किए गए स्थिति में हम वस्तुओं के घातीय जनरेटिंग फलन (ईजीएफ) जी (जेड) का उपयोग करते हैं और लेबल गणना प्रमेय प्रयुक्त करते हैं, जो कहता है कि विन्यास का ईजीएफ द्वारा दिया गया है

${\frac {g(z)^{n}}{|G|}}.$

हम बिना लेबल वाले स्थिति में पीईटी या लेबल वाले स्थिति में लेबल गणना प्रमेय का उपयोग करके भरे हुए स्लॉट विन्यास की गणना करने में सक्षम हैं। अब हम तब प्राप्त विन्यास के जेनरेटिंग फलन के बारे में पूछते हैं जब स्लॉट्स का से अधिक समुच्चय होता है, जिसमें प्रत्येक पर क्रमपरिवर्तन समूह कार्य करता है। स्पष्ट रूप से कक्षाएँ प्रतिच्छेद नहीं करती हैं और हम संबंधित जनरेटिंग फलन जोड़ सकते हैं। उदाहरण के लिए, मान लीजिए कि हम समुच्चय पहले समुच्चय पर अभिनय करने वाला समूह $E_{2}$ है , और दूसरे स्लॉट $E_{3}$ पर, . हम इसे X में निम्नलिखित औपचारिक शक्ति श्रृंखला द्वारा दर्शाते हैं:

$X^{2}/E_{2}\;+\;X^{3}/E_{3}$

जहां शब्द $X^{n}/G$ G और K अंतर्गत कक्षाओं के समुच्चय $X^{n}=X\times \cdots \times X$ को दर्शाने के लिए उपयोग किया जाता है , जो स्पष्ट रूप से वस्तुओं को x से n स्लॉट में पुनरावृत्ति के साथ वितरित करने की प्रक्रिया को दर्शाता है। इसी प्रकार, लेबल वाली वस्तुओं X के समुच्चय से इच्छानुसार लंबाई के चक्र बनाने की लेबल की गई समस्या पर विचार करें। इससे चक्रीय समूहों की क्रियाओं की निम्नलिखित श्रृंखला प्राप्त होती है:

$X/C_{1}\;+\;X^{2}/C_{2}\;+\;X^{3}/C_{3}\;+\;X^{4}/C_{4}\;+\cdots .$

स्पष्ट रूप से हम क्रमपरिवर्तन समूहों के संबंध में भागफल (कक्षाओं) की किसी भी ऐसी शक्ति श्रृंखला को अर्थ प्रदान कर सकते हैं, जहां हम डिग्री n के समूहों को संयुग्मी वर्गों तक सीमित रखते हैं। $\operatorname {Cl} (S_{n})$ सममित समूह $S_{n}$ का उपयोग किया जाता है , जो अद्वितीय गुणनखंडन डोमेन बनाता है। (समान संयुग्मन वर्ग के दो समूहों के संबंध में कक्षाएँ समरूपी हैं।) यह निम्नलिखित परिभाषा को प्रेरित करता है।

एक वर्ग ${\mathcal {C}}\in \mathbb {N} [{\mathfrak {A}}]$ संयोजक संरचनाओं की औपचारिक श्रृंखला है

${\mathcal {C}}=\sum _{n\geq 1}\sum _{G\in \operatorname {Cl} (S_{n})}c_{G}(X^{n}/G)$

जहाँ ${\mathfrak {A}}$ (ए परमाणुओं के लिए है) यूएफडी के अभाज्यों का समूह $\{\operatorname {Cl} (S_{n})\}_{n\geq 1}$ और $c_{G}\in \mathbb {N} .$ है निम्नलिखित में हम अपने अंकन को थोड़ा सरल करेंगे और उदाहरणार्थ लिखेंगे।

$E_{2}+E_{3}{\text{ and }}C_{1}+C_{2}+C_{3}+\cdots .$

ऊपर उल्लिखित कक्षाओं के लिए.

फ़्लैजोलेट-सेडगेविक मौलिक प्रमेय

प्रतीकात्मक संयोजक के फ्लैजोलेट-सेडगेविक सिद्धांत में प्रमेय प्रतीकात्मक संचालको के निर्माण के माध्यम से लेबल किए गए और बिना लेबल वाले कॉम्बिनेटरियल वर्गों की गणना समस्या का समाधान करता है जो कॉम्बिनेटरियल संरचनाओं से जुड़े समीकरणों को सीधे (और स्वचालित रूप से) उत्पन्न करने वाले कार्यों में समीकरणों में अनुवाद करना संभव बनाता है। इन संरचनाओं का उपयोग किया जाता है.

माना ${\mathcal {C}}\in \mathbb {N} [{\mathfrak {A}}]$ संयोजक संरचनाओं का वर्ग बनें। ओजीएफ $F(z)$ का ${\mathcal {C}}(X)$ जहां X के पास ओजीएफ है इस प्रकार $f(z)$ और ईजीएफ $G(z)$ का ${\mathcal {C}}(X)$ है जहां X को ईजीएफ के साथ लेबल किया गया है $g(z)$ द्वारा दिए गए हैं

$F(z)=\sum _{n\geq 1}\sum _{G\in \operatorname {Cl} (S_{n})}c_{G}Z(G)(f(z),f(z^{2}),\ldots ,f(z^{n}))$

और

$G(z)=\sum _{n\geq 1}\left(\sum _{G\in \operatorname {Cl} (S_{n})}{\frac {c_{G}}{|G|}}\right)g(z)^{n}.$

लेबल किए गए स्थिति में हमारी अतिरिक्त आवश्यकता है कि X में आकार शून्य के तत्व नही होंता है। कभी-कभी को जोड़ना सुविधाजनक सिद्ध होगा $G(z)$ संवृत्त समुच्चय की प्रति की उपस्थिति को इंगित करने के लिए। दोनों ${\mathcal {C}}\in \mathbb {Z} [{\mathfrak {A}}]$ को अर्थ निर्दिष्ट करना संभव है (सबसे सामान्य उदाहरण बिना लेबल वाले समुच्चय का मामला है) और ${\mathcal {C}}\in \mathbb {Q} [{\mathfrak {A}}].$ प्रमेय को सिद्ध करने के लिए बस पीईटी (पोल्या गणना प्रमेय) और लेबल गणना प्रमेय प्रयुक्त करते है।

इस प्रमेय की शक्ति इस तथ्य में निहित है कि यह संयोजक वर्गों का प्रतिनिधित्व करने वाले कार्यों को उत्पन्न करने पर संचालको का निर्माण करना संभव बनाता है। इस प्रकार संयोजक वर्गों के बीच संरचनात्मक समीकरण सीधे संबंधित उत्पन्न करने वाले कार्यों में समीकरण में बदल हो जाता है। इसके अतिरिक्त, लेबल किए गए स्थिति में यह उस फॉर्मूले से स्पष्ट है जिसे हम $g(z)$ द्वारा प्रतिस्थापित कर सकते हैं परमाणु z द्वारा और परिणामी संचालक की गणना करें, जिसे बाद में ईजीएफ पर प्रयुक्त किया जा सकता है। अब हम सबसे महत्वपूर्ण संचालको का निर्माण करना जारी रखते हैं। पाठक चक्र सूचकांक पृष्ठ पर उपस्थित डेटा से तुलना करना चाह सकते हैं।

अनुक्रम संचालिका SEQ

यह संचालक क्लास से मेल खाता है

$1+E_{1}+E_{2}+E_{3}+\cdots$

और अनुक्रमों का प्रतिनिधित्व करता है, अर्थात स्लॉटों को क्रमपरिवर्तित नहीं किया जा रहा है और पूर्णतया संवृत्त अनुक्रम है।

$F(z)=1+\sum _{n\geq 1}Z(E_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))=1+\sum _{n\geq 1}f(z)^{n}={\frac {1}{1-f(z)}}$

और

$G(z)=1+\sum _{n\geq 1}\left({\frac {1}{|E_{n}|}}\right)g(z)^{n}={\frac {1}{1-g(z)}}.$

साइकिल संचालक CYC

यह संचालक क्लास से मेल खाता है

$C_{1}+C_{2}+C_{3}+\cdots$

अर्थात, चक्र जिसमें कम से कम वस्तु हो। अपने पास

$F(z)=\sum _{n\geq 1}Z(C_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))=\sum _{n\geq 1}{\frac {1}{n}}\sum _{d\mid n}\varphi (d)f(z^{d})^{n/d}$

या

$F(z)=\sum _{k\geq 1}\varphi (k)\sum _{m\geq 1}{\frac {1}{km}}f(z^{k})^{m}=\sum _{k\geq 1}{\frac {\varphi (k)}{k}}\log {\frac {1}{1-f(z^{k})}}$

और

$G(z)=\sum _{n\geq 1}\left({\frac {1}{|C_{n}|}}\right)g(z)^{n}=\log {\frac {1}{1-g(z)}}.$

यह संचालक, समुच्चय संचालक के साथ मिलकर SET, और विशिष्ट डिग्री तक उनके प्रतिबंधों का उपयोग यादृच्छिक क्रमपरिवर्तन आंकड़ों की गणना करने के लिए किया जाता है। इस संचालक के दो उपयोगी प्रतिबंध हैं, अर्थात् सम और विषम चक्र होते है।

लेबल किया गया सम साइकिल संचालक CYC_even है

$C_{2}+C_{4}+C_{6}+\cdots$

कौन सी पैदावार

$G(z)=\sum _{n\geq 1}\left({\frac {1}{|C_{2n}|}}\right)g(z)^{2n}={\frac {1}{2}}\log {\frac {1}{1-g(z)^{2}}}.$

इसका तात्पर्य यह है कि लेबल किया गया विषम चक्र संचालक CYC_odd है

$C_{1}+C_{3}+C_{5}+\cdots$

द्वारा दिया गया है

$G(z)=\log {\frac {1}{1-g(z)}}-{\frac {1}{2}}\log {\frac {1}{1-g(z)^{2}}}={\frac {1}{2}}\log {\frac {1+g(z)}{1-g(z)}}.$

मल्टीसेट/समुच्चय संचालक MSET/SET

शृंखला

$1+S_{1}+S_{2}+S_{3}+\cdots$

अर्थात, सममित समूह को स्लॉट्स पर प्रयुक्त किया जाता है। यह बिना लेबल वाले केस में मल्टीसेट बनाता है और लेबल किए गए केस में समुच्चय करता है (लेबल किए गए केस में कोई मल्टीसेट नहीं होता है क्योंकि लेबल अलग-अलग स्लॉट में रखे गए समुच्चय से ही ऑब्जेक्ट के कई उदाहरणों को अलग करते हैं)। हम संवृत्त समुच्चय को लेबल किए गए और बिना लेबल वाले दोनों स्थितियों में सम्मिलित करते हैं।

अनलेबल केस फलन का उपयोग करके किया जाता है

$M(f(z),y)=\sum _{n\geq 0}y^{n}Z(S_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))$

जिससे

${\mathfrak {M}}(f(z))=M(f(z),1).$

$M(f(z),1)$ का मूल्यांकन है हमने प्राप्त

$F(z)=\exp \left(\sum _{\ell \geq 1}{\frac {f(z^{\ell })}{\ell }}\right).$

हमारे पास लेबल किए गए स्थिति के लिए है

$G(z)=1+\sum _{n\geq 1}\left({\frac {1}{|S_{n}|}}\right)g(z)^{n}=\sum _{n\geq 0}{\frac {g(z)^{n}}{n!}}=\exp g(z).$

लेबल किए गए स्थिति में हम संचालक को इस SET द्वारा निरूपित करते हैं , और बिना लेबल वाले स्थिति में, द्वारा MSET निरूपित करते हैं. ऐसा इसलिए है क्योंकि लेबल किए गए स्थिति में कोई मल्टीसेट नहीं हैं (लेबल मिश्रित संयोजन वर्ग के घटकों को अलग करते हैं) जबकि अनलेबल स्थिति में मल्टीसेट और समुच्चय होते हैं,

$F(z)=\exp \left(\sum _{\ell \geq 1}(-1)^{\ell -1}{\frac {f(z^{\ell })}{\ell }}\right).$

प्रक्रिया

सामान्यतः, व्यक्ति तटस्थ वर्ग ${\mathcal {E}}$ से प्रारंभ करता है , जिसमें आकार 0 की वस्तु होती है (तटस्थ वस्तु, जिसे अधिकांशतः $\epsilon$ द्वारा दर्शाया जाता है ), और या अधिक परमाणु वर्ग ${\mathcal {Z}}$, प्रत्येक में आकार 1 की एकल वस्तु होती है। अगला, समुच्चय सिद्धांत या समुच्चय-सैद्धांतिक संबंध जिसमें विभिन्न सरल संचालन सम्मिलित होते हैं, जैसे कि असंयुक्त संघ, कार्टेशियन उत्पाद, समुच्चय (गणित), अनुक्रम और मल्टीसेट पहले से ही अधिक जटिल वर्गों को परिभाषित करते हैं परिभाषित वर्ग ये संबंध प्रत्यावर्ती हो सकते हैं. प्रतीकात्मक संयोजक की सुंदरता इसमें निहित है कि समुच्चय सैद्धांतिक, या प्रतीकात्मक, संबंध सीधे बीजगणित संबंधों में अनुवादित होते हैं जिनमें उत्पन्न कार्य सम्मिलित होते हैं।

इस लेख में, हम कॉम्बिनेटरियल क्लासों को दर्शाने के लिए स्क्रिप्ट अपरकेस अक्षरों और जनरेटिंग फलन (इसलिए क्लास) के लिए संबंधित सादे अक्षरों का उपयोग करने की परंपरा ${\mathcal {A}}$ का पालन करते है सृजनात्मक कार्य $A(z)$ है).

प्रतीकात्मक संयोजक में सामान्यतः दो प्रकार के जनरेटिंग फलन का उपयोग किया जाता है - सामान्य जनरेटिंग फलन, जिसका उपयोग बिना लेबल वाली वस्तुओं के कॉम्बिनेटरियल वर्गों के लिए किया जाता है, और घातीय जनरेटिंग फलन, लेबल वाली वस्तुओं के वर्गों के लिए उपयोग किया जाता है।

यह दिखाना सामान्य है कि उत्पन्न करने वाले कार्य (या तो सामान्य या घातांकीय) ${\mathcal {E}}$ और ${\mathcal {Z}}$ हैं इस प्रकार $E(z)=1$ और $Z(z)=z$, क्रमश असंयुक्त संघ भी सरल है असंयुक्त समुच्चयों के लिए ${\mathcal {B}}$ और ${\mathcal {C}}$, ${\mathcal {A}}={\mathcal {B}}\cup {\mathcal {C}}$ तात्पर्य $A(z)=B(z)+C(z)$. अन्य परिचालनों से संबंधित संबंध इस बात पर निर्भर करते हैं कि हम लेबल वाली या बिना लेबल वाली संरचनाओं (और सामान्य या घातीय उत्पन्न करने वाले कार्यों) के बारे में बात कर रहे हैं।

संयुक्त योग

संघों को विघटित करने के लिए संघ (समुच्चय सिद्धांत) का प्रतिबंध महत्वपूर्ण है; चूँकि, प्रतीकात्मक संयोजक के औपचारिक विनिर्देश में, यह ट्रैक करना बहुत परेशानी भरा है कि कौन से समुच्चय असंयुक्त हैं। इसके अतिरिक्त, हम ऐसे निर्माण का उपयोग करते हैं जो गारंटी देता है कि कोई प्रतिच्छेदन नहीं है (चूँकि सावधान रहें; यह संचालन के शब्दार्थ को भी प्रभावित करता है)। दो समुच्चयों के संयुक्त योग को परिभाषित करने में ${\mathcal {A}}$ और ${\mathcal {B}}$ उदाहरण के लिए, हम प्रत्येक समुच्चय के सदस्यों को अलग मार्कर से चिह्नित करते हैं इस प्रकार $\circ$ के सदस्यों के लिए ${\mathcal {A}}$ और $\bullet$ के सदस्यों के लिए ${\mathcal {B}}$. संयुक्त योग तब है:

${\mathcal {A}}+{\mathcal {B}}=({\mathcal {A}}\times \{\circ \})\cup ({\mathcal {B}}\times \{\bullet \})$

यह वह संचालन है जो औपचारिक रूप से जोड़ से मेल खाता है।

अचिह्नित संरचनाएँ

बिना लेबल वाली संरचनाओं के साथ, साधारण जनरेटिंग फलन (ओजीएफ) का उपयोग किया जाता है। अनुक्रम का ओजीएफ $A_{n}$ परिभाषित किया जाता है

$A(x)=\sum _{n=0}^{\infty }A_{n}x^{n}$

उत्पाद

दो संयोजक वर्गों का कार्टेशियन उत्पाद ${\mathcal {A}}$ और ${\mathcal {B}}$ किसी क्रमित युग्म के आकार को युग्म में तत्वों के आकार के योग के रूप में परिभाषित करके निर्दिष्ट किया जाता है। इस प्रकार हमारे पास $a\in {\mathcal {A}}$ और $b\in {\mathcal {B}}$, $|(a,b)|=|a|+|b|$. है यह अधिक सहज परिभाषा होनी चाहिए. अब हम ध्यान देते हैं कि तत्वों की संख्या ${\mathcal {A}}\times {\mathcal {B}}$ आकार का n है

$\sum _{k=0}^{n}A_{k}B_{n-k}.$

ओजीएफ की परिभाषा और कुछ प्राथमिक बीजगणित का उपयोग करके, हम यह दिखा सकते हैं

${\mathcal {A}}={\mathcal {B}}\times {\mathcal {C}}$ तात्पर्य $A(z)=B(z)\cdot C(z).$

अनुक्रम

अनुक्रम निर्माण, द्वारा निरूपित ${\mathcal {A}}={\mathfrak {G}}\{{\mathcal {B}}\}$ परिभाषित किया जाता है

${\mathfrak {G}}\{{\mathcal {B}}\}={\mathcal {E}}+{\mathcal {B}}+({\mathcal {B}}\times {\mathcal {B}})+({\mathcal {B}}\times {\mathcal {B}}\times {\mathcal {B}})+\cdots .$

दूसरे शब्दों में, अनुक्रम तटस्थ तत्व या का तत्व है ${\mathcal {B}}$, या ऑर्डर किया हुआ जोड़ा, ऑर्डर किया गया ट्रिपल, आदि। इससे संबंध बनता है

$A(z)=1+B(z)+B(z)^{2}+B(z)^{3}+\cdots ={\frac {1}{1-B(z)}}.$

समुच्चय

समुच्चय (या पावरसमुच्चय) निर्माण, द्वारा दर्शाया गया ${\mathcal {A}}={\mathfrak {P}}\{{\mathcal {B}}\}$ परिभाषित किया जाता है

${\mathfrak {P}}\{{\mathcal {B}}\}=\prod _{\beta \in {\mathcal {B}}}({\mathcal {E}}+\{\beta \}),$

जो रिश्ते की ओर ले जाता है

${\begin{aligned}A(z)&{}=\prod _{\beta \in {\mathcal {B}}}(1+z^{|\beta |})\\&{}=\prod _{n=1}^{\infty }(1+z^{n})^{B_{n}}\\&{}=\exp \left(\ln \prod _{n=1}^{\infty }(1+z^{n})^{B_{n}}\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }B_{n}\ln(1+z^{n})\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }B_{n}\cdot \sum _{k=1}^{\infty }{\frac {(-1)^{k-1}z^{nk}}{k}}\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}}{k}}\cdot \sum _{n=1}^{\infty }B_{n}z^{nk}\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}B(z^{k})}{k}}\right),\end{aligned}}$

जहां विस्तार

$\ln(1+u)=\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}u^{k}}{k}}$

लाइन 4 से लाइन 5 तक जाने के लिए उपयोग किया जाता था।

मल्टीसेट

मल्टीसेट निर्माण, निरूपित ${\mathcal {A}}={\mathfrak {M}}\{{\mathcal {B}}\}$ समुच्चय निर्माण का सामान्यीकरण है। समुच्चय निर्माण में, प्रत्येक तत्व शून्य या बार हो सकता है। मल्टीसेट में, प्रत्येक तत्व इच्छानुसार कई बार दिखाई दे सकता है। इसलिए,

${\mathfrak {M}}\{{\mathcal {B}}\}=\prod _{\beta \in {\mathcal {B}}}{\mathfrak {G}}\{\beta \}.$

इससे सम्बन्ध बनता है

${\begin{aligned}A(z)&{}=\prod _{\beta \in {\mathcal {B}}}(1-z^{|\beta |})^{-1}\\&{}=\prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\\&{}=\exp \left(\ln \prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }-B_{n}\ln(1-z^{n})\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {B(z^{k})}{k}}\right),\end{aligned}}$

जहां, उपरोक्त समुच्चय निर्माण के समान, हम विस्तार $\ln(1-z^{n})$ करते हैं , वास्तु की विनिमय करें, और ओजीएफ के स्थान पर ${\mathcal {B}}$ स्थानापन्न करें .

अन्य प्रारंभिक निर्माण

अन्य महत्वपूर्ण प्रारंभिक निर्माण हैं:

• चक्र निर्माण (${\mathfrak {C}}\{{\mathcal {B}}\}$), अनुक्रमों की तरह सिवाय इसके कि चक्रीय घुमावों को अलग नहीं माना जाता है
• इंगित करना ($\Theta {\mathcal {B}}$), जिसमें प्रत्येक सदस्य B को इसके परमाणुओं में से के लिए तटस्थ (शून्य आकार) सूचक द्वारा संवर्धित किया जाता है
• प्रतिस्थापन (${\mathcal {B}}\circ {\mathcal {C}}$), जिसमें प्रत्येक परमाणु सदस्य है B को सदस्य C द्वारा प्रतिस्थापित किया जाता है .

इन निर्माणों की व्युत्पत्तियाँ यहाँ दिखाने के लिए बहुत जटिल हैं। यहाँ परिणाम हैं:

निर्माण	जनरेटिंग फ़ंक्शन
${\mathcal {A}}={\mathfrak {C}}\{{\mathcal {B}}\}$	$A(z)=\sum _{k=1}^{\infty }{\frac {\phi (k)}{k}}\ln {\frac {1}{1-B(z^{k})}}$ (जहाँ $\phi (k)$ यूलर टोटिएंट फलन है)
${\mathcal {A}}=\Theta {\mathcal {B}}$	$A(z)=z{\frac {d}{dz}}B(z)$
${\mathcal {A}}={\mathcal {B}}\circ {\mathcal {C}}$	$A(z)=B(C(z))$

उदाहरण

इन प्राथमिक निर्माणों का उपयोग करके कई संयोजक वर्ग बनाए जा सकते हैं। उदाहरण के लिए, समतल ट्री (ग्राफ़) का वर्ग (अर्थात, समतल में ट्री का एम्बेडिंग होना, जिससे उपट्री का क्रम रखता हो) पुनरावर्तन संबंध द्वारा निर्दिष्ट किया जाता है

${\mathcal {G}}={\mathcal {Z}}\times \operatorname {SEQ} \{{\mathcal {G}}\}.$

दूसरे शब्दों में, ट्री आकार 1 का रूट नोड और उपट्री का क्रम है। यह देता है

$G(z)={\frac {z}{1-G(z)}}$

हम G(z) को गुणा करके $1-G(z)$ हल करते हैं

$G(z)-G(z)^{2}=z$

z को घटाने और द्विघात सूत्र का उपयोग करके G(z) को हल करने से प्राप्त होता है

$G(z)={\frac {1-{\sqrt {1-4z}}}{2}}.$

एक अन्य उदाहरण (और क्लासिक संयोजक समस्या) पूर्णांक विभाजन है। सबसे पहले, धनात्मक पूर्णांकों ${\mathcal {I}}$ के वर्ग को परिभाषित करें , जहां प्रत्येक पूर्णांक का आकार उसका मान है:

${\mathcal {I}}={\mathcal {Z}}\times \operatorname {SEQ} \{{\mathcal {Z}}\}$

${\mathcal {I}}$ का ओजीएफ है

$I(z)={\frac {z}{1-z}}.$

अब, विभाजनों के समुच्चय ${\mathcal {P}}$ को परिभाषित करें जैसा

${\mathcal {P}}=\operatorname {MSET} \{{\mathcal {I}}\}.$

${\mathcal {P}}$ का ओजीएफ है

$P(z)=\exp \left(I(z)+{\frac {1}{2}}I(z^{2})+{\frac {1}{3}}I(z^{3})+\cdots \right).$

सामान्यतः, $P(z)$ इसके लिए कोई बंद फॉर्म नहीं है ; चूँकि, ओजीएफ का उपयोग पुनरावृत्ति संबंध प्राप्त करने के लिए किया जा सकता है, या विश्लेषणात्मक संयोजक के अधिक उन्नत विधियों का उपयोग करके, गिनती अनुक्रम के अनुक्रम के जनरेटिंग फलन एसिम्प्टोटिक विकास की गणना की जा सकती है।

विनिर्देश और निर्दिष्ट वर्ग

ऊपर उल्लिखित प्राथमिक निर्माण विशिष्टता की धारणा को परिभाषित करने की अनुमति देते हैं। वे विनिर्देश कई संयोजन वर्गों के साथ पुनरावर्ती समीकरणों के समुच्चय का उपयोग करने की अनुमति देते हैं।

औपचारिक रूप से, संयोजक वर्गों के समुच्चय के लिए विशिष्टता $({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})$ का समुच्चय $r$ है समीकरण ${\mathcal {A}}_{i}=\Phi _{i}({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})$, जहाँ $\Phi _{i}$ अभिव्यक्ति है, जिसके परमाणु ${\mathcal {E}},{\mathcal {Z}}$ हैं और यह ${\mathcal {A}}_{i}$ और जिनके संचालक ऊपर सूचीबद्ध प्राथमिक निर्माण हैं।

संयोजन संरचनाओं के वर्ग को तब रचनात्मक या निर्दिष्ट कहा जाता है जब वह किसी विनिर्देश को स्वीकार करता है।

उदाहरण के लिए, ट्री का समूह जिनकी पत्तियों की गहराई सम (क्रमशः, विषम) है, को दो वर्गों ${\mathcal {A}}_{\text{even}}$ और ${\mathcal {A}}_{\text{odd}}$ के साथ विनिर्देश का उपयोग करके परिभाषित किया जा सकता है. उन वर्गों ${\mathcal {A}}_{\text{odd}}={\mathcal {Z}}\times \operatorname {Seq} _{\geq 1}{\mathcal {A}}_{\text{even}}$ और ${\mathcal {A}}_{\text{even}}={\mathcal {Z}}\times \operatorname {Seq} {\mathcal {A}}_{\text{odd}}$ को समीकरण को संतुष्ट करना चाहिए.

लेबल संरचनाएं

किसी वस्तु को अशक्त रूप से लेबल किया जाता है यदि उसके प्रत्येक परमाणु में गैर-नकारात्मक पूर्णांक लेबल होता है, और इनमें से प्रत्येक लेबल अलग होता है। किसी ऑब्जेक्ट को (दृढ़ता से या अच्छी तरह से) लेबल किया जाता है, इसके अतिरिक्त, इन लेबलों में लगातार पूर्णांक सम्मिलित $[1\ldots n]$ होते हैं . ध्यान दें: कुछ कॉम्बिनेटरियल वर्गों को लेबल वाली संरचनाओं या बिना लेबल वाली संरचनाओं के रूप में निर्दिष्ट किया जाता है, किन्तु कुछ दोनों विशिष्टताओं को सरली से स्वीकार कर लेते हैं। लेबल संरचनाओं का अच्छा उदाहरण ग्राफ़ (अलग गणित) का वर्ग है।

लेबल वाली संरचनाओं के साथ, घातीय जनरेटिंग फलन (ईजीएफ) का उपयोग किया जाता है। अनुक्रम का ईजीएफ $A_{n}$ परिभाषित किया जाता है

$A(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}.$

उत्पाद

लेबल वाली संरचनाओं के लिए, हमें बिना लेबल वाली संरचनाओं की तुलना में उत्पाद के लिए अलग परिभाषा का उपयोग करना चाहिए। वास्तव में, यदि हम केवल कार्टेशियन उत्पाद का उपयोग करते हैं, जिससे परिणामी संरचनाएं अच्छी तरह से लेबल भी नहीं की जाती है। इसके अतिरिक्त, हम तथाकथित लेबल वाले उत्पाद का उपयोग करते हैं, जिसे ${\mathcal {A}}\star {\mathcal {B}}.$ द्वारा दर्शाया गया है एक जोड़ी के लिए $\beta \in {\mathcal {B}}$ और $\gamma \in {\mathcal {C}}$, हम दोनों संरचनाओं को संरचना में संयोजित करना चाहते हैं। परिणाम को अच्छी तरह से लेबल करने के लिए, इसमें परमाणुओं $\beta$ और $\gamma$ की कुछ पुनः लेबलिंग की आवश्यकता होती है . हम अपना ध्यान उन पुन: लेबलिंग तक सीमित रखेंगे जो मूल लेबल के क्रम के अनुरूप हैं। ध्यान दें कि पुनः लेबलिंग करने के अभी भी कई विधि हैं; इस प्रकार, सदस्यों की प्रत्येक जोड़ी उत्पाद में भी सदस्य नहीं, किन्तु नए सदस्यों का समूह निर्धारित करती है। इस निर्माण का विवरण लेबल गणना प्रमेय के पृष्ठ पर पाया जाता है।

इस विकास में सहायता के लिए, आइए हम फलन $\rho$ को परिभाषित करें, , जो अपने तर्क के रूप में (संभवतः अशक्त) लेबल वाली वस्तु $\alpha$ को लेता है और अपने परमाणुओं को क्रम-संगत विधि से पुनः लेबल करता है जिससे $\rho (\alpha )$ अच्छी तरह से लेबल किया गया है. फिर हम दो वस्तुओं के लिए लेबल किए गए उत्पाद $\alpha$ और $\beta$ को परिभाषित करते हैं जैसा

$\alpha \star \beta =\{(\alpha ',\beta '):(\alpha ',\beta '){\text{ is well-labelled, }}\rho (\alpha ')=\alpha ,\rho (\beta ')=\beta \}.$

अंत में, दो वर्गों का लेबल वाला उत्पाद ${\mathcal {A}}$ और ${\mathcal {B}}$ है

${\mathcal {A}}\star {\mathcal {B}}=\bigcup _{\alpha \in {\mathcal {A}},\beta \in {\mathcal {B}}}(\alpha \star \beta ).$

ईजीएफ को आकार की वस्तुओं $k$ और $n-k$, को नोट करके प्राप्त किया जा सकता है वहाँ ${n \choose k}$पुनः लेबलिंग करने के विधि. इसलिए, आकार की वस्तुओं की कुल संख्या $n$ है

$\sum _{k=0}^{n}{n \choose k}A_{k}B_{n-k}.$

नियमो के लिए यह द्विपद कनवल्शन संबंध ईजीजी को गुणा करने के बराबर है,

$A(z)\cdot B(z).$

अनुक्रम

अनुक्रम निर्माण ${\mathcal {A}}={\mathfrak {G}}\{{\mathcal {B}}\}$ बिना लेबल वाले स्थिति के समान ही परिभाषित किया गया है:

${\mathfrak {G}}\{{\mathcal {B}}\}={\mathcal {E}}+{\mathcal {B}}+({\mathcal {B}}\star {\mathcal {B}})+({\mathcal {B}}\star {\mathcal {B}}\star {\mathcal {B}})+\cdots$

और फिर, जैसा कि ऊपर बताया गया है,

$A(z)={\frac {1}{1-B(z)}}$

समुच्चय

लेबल की गई संरचनाओं में, का समुच्चय $k$ तत्व पूर्णतया $k!$ क्रम मेल खाते हैं . यह बिना लेबल वाले स्थिति से अलग है, जहां कुछ क्रमपरिवर्तन मेल खा सकते हैं। इस प्रकार ${\mathcal {A}}={\mathfrak {P}}\{{\mathcal {B}}\}$ के लिए , अपने पास

$A(z)=\sum _{k=0}^{\infty }{\frac {B(z)^{k}}{k!}}=\exp(B(z))$

साइकिल

लेबल वाले केस की तुलना में साइकिल चलाना भी सरल है। लंबाई का चक्र $k$ से मेल खाती है विशिष्ट अनुक्रम $k$ इस प्रकार ${\mathcal {A}}={\mathfrak {C}}\{{\mathcal {B}}\}$ के लिए , अपने पास

$A(z)=\sum _{k=0}^{\infty }{\frac {B(z)^{k}}{k}}=\ln \left({\frac {1}{1-B(z)}}\right).$

डिब्बाबंद उत्पाद

लेबल की गई संरचनाओं में, न्यूनतम-बॉक्स वाला उत्पाद ${\mathcal {A}}_{\min }={\mathcal {B}}^{\square }\star {\mathcal {C}}$ मूल उत्पाद का रूपांतर है जिसके लिए तत्व की आवश्यकता होती है इस प्रकार ${\mathcal {B}}$ न्यूनतम लेबल वाले उत्पाद में. इसी प्रकार, हम अधिकतम-बॉक्स वाले उत्पाद को भी परिभाषित कर सकते हैं, जिसे ${\mathcal {A}}_{\max }={\mathcal {B}}^{\blacksquare }\star {\mathcal {C}}$ द्वारा दर्शाया गया है , उसी विधि से,

$A_{\min }(z)=A_{\max }(z)=\int _{0}^{z}B'(t)C(t)\,dt.$

या समकक्ष,

$A_{\min }'(t)=A_{\max }'(t)=B'(t)C(t).$

उदाहरण

एक बढ़ता हुआ केली ट्री लेबल वाला गैर-समतल और जड़ वाला ट्री है जिसके जड़ से निकलने वाली किसी भी शाखा के लेबल बढ़ते क्रम का निर्माण करते हैं। इस प्रकार ${\mathcal {L}}$ ऐसे ट्री का वर्ग बनें। पुनरावर्ती विशिष्टता ${\mathcal {L}}={\mathcal {Z}}^{\square }\star \operatorname {SET} ({\mathcal {L}}).$ है

अन्य प्रारंभिक निर्माण

संचालक CYC_even, CYC_odd, SET_even, और

SET_odd सम और विषम लंबाई के चक्रों और सम और विषम कार्डिनैलिटी के सेट का प्रतिनिधित्व करते हैं।

उदाहरण

दूसरे प्रकार की स्टर्लिंग संख्याएँ संरचनात्मक अपघटन का उपयोग करके प्राप्त और विश्लेषण की जा सकती हैं

$\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})).$

विघटन

$\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}}))$

पहली तरह के अहस्ताक्षरित स्टर्लिंग संख्याओं का अध्ययन करने और यादृच्छिक क्रमपरिवर्तन आंकड़ों की व्युत्पत्ति में उपयोग किया जाता है। प्रतीकात्मक संयोजक के भीतर स्टर्लिंग संख्याओं से जुड़े घातीय जनरेटिंग फलन की विस्तृत जांच स्टर्लिंग संख्याओं और प्रतीकात्मक संयोजक में घातीय जनरेटिंग फलन के पृष्ठ पर पाई जा सकती है।

यह भी देखें

• संयुक्त प्रजातियाँ

संदर्भ

• François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire des structures arborescentes, LaCIM, Montréal (1994). English version: Combinatorial Species and Tree-like Structures, Cambridge University Press (1998).
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press (2009). (available online: http://algo.inria.fr/flajolet/Publications/book.pdf)
• Micha Hofri, Analysis of Algorithms: Computational Methods and Mathematical Tools, Oxford University Press (1995).