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

This article is about the method in analytic combinatorics. For the method in invariant theory, see Symbolic method.

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

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

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

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

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

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

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

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

स्पष्ट रूप से हम क्रमपरिवर्तन समूहों के संबंध में भागफल (कक्षाओं) की किसी भी ऐसी शक्ति श्रृंखला को अर्थ प्रदान कर सकते हैं, जहां हम डिग्री एन के समूहों को संयुग्मी वर्गों तक सीमित रखते हैं। $\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 के पास OGF है $f(z)$ और ईजीएफ $G(z)$ का ${\mathcal {C}}(X)$ जहां X को EGF के साथ लेबल किया गया है $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 \})$

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

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

बिना लेबल वाली संरचनाओं के साथ, एक साधारण जनरेटिंग फ़ंक्शन (ओजीएफ) का उपयोग किया जाता है। एक अनुक्रम का OGF $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})$, रकम की अदला-बदली करें, और OGF के स्थान पर स्थानापन्न करें ${\mathcal {B}}$.

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

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

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

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

Construction	Generating function
${\mathcal {A}}={\mathfrak {C}}\{{\mathcal {B}}\}$	$A(z)=\sum _{k=1}^{\infty }{\frac {\phi (k)}{k}}\ln {\frac {1}{1-B(z^{k})}}$ (where $\phi (k)$ is the Euler totient function)
${\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)$; हालाँकि, OGF का उपयोग पुनरावृत्ति संबंध प्राप्त करने के लिए किया जा सकता है, या विश्लेषणात्मक कॉम्बिनेटरिक्स के अधिक उन्नत तरीकों का उपयोग करके, गिनती अनुक्रम के अनुक्रम के जनरेटिंग फ़ंक्शन # एसिम्प्टोटिक विकास की गणना की जा सकती है।

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

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

औपचारिक रूप से, संयोजक वर्गों के एक सेट के लिए एक विशिष्टता $({\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).