गणनात्मक कॉम्बिनेटरिक्स

गणनासूचक साहचर्य साहचर्य का क्षेत्र है जो कुछ पैटर्न बनाने के विधियों की संख्या से संबंधित है। इस प्रकार की समस्या के दो उदाहरण संयोजन की गिनती और क्रमचयों की गिनती कर रहे हैं। अधिक सामान्यतः, परिमित समुच्चय S_i का अनंत संग्रह दिया गया है_i प्राकृतिक संख्याओं द्वारा अनुक्रमित, गणनासूचक साहचर्य गिनती फलन का वर्णन करना चाहता है जो S_n में वस्तुओं की संख्या की गणना करता है प्रत्येक n के लिए चुकीं गिनती गणित में गिनती सेट में तत्वों की संख्या व्यापक गणितीय समस्या है, अनुप्रयोगों में उत्पन्न होने वाली कई समस्याओं का अपेक्षाकृत सरल संयोजन विवरण है। बारह गुना विधियाँ सेट के क्रमपरिवर्तन, संयोजन और विभाजन की गिनती के लिए एकीकृत ढांचा प्रदान करता है।

इस तरह के सबसे सरल कार्य बंद सूत्र हैं, जिन्हें प्राथमिक कार्यों की संरचना के रूप में व्यक्त किया जा सकता है जैसे कि भाज्य, घातांक, और इसी तरह के उदाहरण के लिए, जैसा कि नीचे दिखाया गया है, एन कार्डों के डेक के विभिन्न संभावित क्रमों की संख्या यफ (एन) = एन! है। बंद सूत्र खोजने की समस्या को बीजगणितीय गणना के रूप में जाना जाता है, और इसमें अधिकांशतः पुनरावृत्ति संबंध या फलन उत्पन्न करना और वांछित बंद रूप पर पहुंचने के लिए इसका उपयोग करना सम्मिलित होता है।

अधिकांशतः, जटिल बंद सूत्र गिनती फलन के व्यवहार में थोड़ी अंतर्दृष्टि उत्पन करता है क्योंकि गिने हुए वस्तुओं की संख्या बढ़ती है।

इन स्थितियों में, साधारण स्पर्शोन्मुख विश्लेषण सन्निकटन अच्छा हो सकता है। फलन $g(n)$ के लिए स्पर्शोन्मुख सन्निकटन है $f(n)$ अगर $f(n)/g(n)\rightarrow 1$ जैसा $n\rightarrow \infty$. इस स्थितियों में हम लिखते हैं $f(n)\sim g(n).\,$

कार्य उत्पन्न करना

संयोजी वस्तुओं के परिवारों का वर्णन करने के लिए जनरेटिंग फलन का उपयोग किया जाता है। होने देना ${\mathcal {F}}$ वस्तुओं के परिवार को निरूपित करें और यफ(एक्स) को इसका जनक फलन होने दें। तब

$F(x)=\sum _{n=0}^{\infty }f_{n}x^{n}$

जहाँ $f_{n}$ आकार एन के संयोजी वस्तुओं की संख्या को दर्शाता है। आकार एन के संयोजी वस्तुओं की संख्या इसलिए के गुणांक द्वारा दी गई है $x^{n}$ मिश्रित वस्तुओं के परिवारों पर कुछ सामान्य ऑपरेशन और जनरेटिंग फलन पर इसके प्रभाव को अब विकसित किया जाएगा।

घातीय जनरेटिंग फलन का भी कभी-कभी उपयोग किया जाता है। इस स्थितियों में इसका रूप होगा

$F(x)=\sum _{n=0}^{\infty }f_{n}{\frac {x^{n}}{n!}}$

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

संघ

दो मिश्रित परिवारों को देखते हुए, ${\mathcal {F}}$ और ${\mathcal {G}}$ जनरेटिंग फलन एफ(एक्स) और जी(एक्स) के साथ, दो परिवारों का अलग मिलन (${\mathcal {F}}\cup {\mathcal {G}}$) का जनन फलन एफ(एक्स) + जी(एक्स) है।

जोड़े

ऊपर के रूप में दो संयोजन परिवारों के लिए दो परिवारों के कार्टेशियन उत्पाद (जोड़ी) (${\mathcal {F}}\times {\mathcal {G}}$) का जनन फलन एफ(एक्स) जी(एक्स) है।

अनुक्रम

जैसा कि ऊपर परिभाषित किया गया है, ए (परिमित) अनुक्रम जोड़ी के विचार को सामान्यीकृत करता है। अनुक्रम स्वयं के साथ संयोजी वस्तु के स्वैच्छिक कार्टेशियन उत्पाद हैं। औपचारिक रूप से:

${\mbox{Seq}}({\mathcal {F}})=\epsilon \ \cup \ {\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \cdots$

उपरोक्त को शब्दों में रखने के लिए: खाली अनुक्रम या एक तत्व का अनुक्रम या दो तत्वों का अनुक्रम या तीन तत्वों का अनुक्रम इत्यादि जनरेटिंग फ़ंक्शन होगा:

$1+F(x)+[F(x)]^{2}+[F(x)]^{3}+\cdots ={\frac {1}{1-F(x)}}.$

मिश्रित संरचनाएं

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

बाइनरी और प्लेन ट्री

बाइनरी और प्लेन ट्री लेबल नहीं किया गया मिश्रित संरचना के उदाहरण हैं। पेड़ों में किनारों से जुड़े हुए नोड्स होते हैं जैसे कि कोई चक्र (ग्राफ सिद्धांत) नहीं होता है। सामान्यतः नोड होता है जिसे रूट कहा जाता है, जिसका कोई पैरेंट नोड नहीं होता है। समतल वृक्षों में प्रत्येक नोड में बच्चों की मनमानी संख्या हो सकती है। बाइनरी ट्री में, प्लेन ट्री का विशेष स्थिति, प्रत्येक नोड में या तो दो या कोई संतान नहीं हो सकती है। होने देना ${\mathcal {P}}$ सभी समतल वृक्षों के परिवार को निरूपित करें। तब इस परिवार को पुनरावर्ती रूप से निम्नानुसार परिभाषित किया जा सकता है:

${\mathcal {P}}=\{\bullet \}\times \,{\mbox{Seq}}({\mathcal {P}})$

इस स्थितियों में $\{\bullet \}$ नोड से मिलकर वस्तुओं के परिवार का प्रतिनिधित्व करता है। इसमें जनरेटिंग फलन एक्स है। मान लीजिए पी(एक्स) जनक फलन को निरूपित करता है ${\mathcal {P}}$.

उपरोक्त विवरण को शब्दों में रखना: प्लेन ट्री में एक नोड होता है, जिसमें मनमानी संख्या में सब ट्री जुड़ी होती हैं, जिनमें से प्रत्येक में प्लेन ट्री भी होती है। पहले विकसित संयोजी संरचनाओं के परिवारों पर कार्यवाही का उपयोग करना, यह पुनरावर्ती जनरेटिंग फलन में अनुवाद करता है:

$P(x)=x\,{\frac {1}{1-P(x)}}$

पी (एक्स) के लिए हल करने के बाद:

$P(x)={\frac {1-{\sqrt {1-4x}}}{2}}$

आकार एन के समतल वृक्षों की संख्या के लिए स्पष्ट सूत्र अब एक्स के गुणांक को निकालकर निर्धारित किया जा सकता है।

${\begin{aligned}p_{n}&=[x^{n}]P(x)=[x^{n}]{\frac {1-{\sqrt {1-4x}}}{2}}\\[6pt]&=[x^{n}]{\frac {1}{2}}-[x^{n}]{\frac {1}{2}}{\sqrt {1-4x}}\\[6pt]&=-{\frac {1}{2}}[x^{n}]\sum _{k=0}^{\infty }{{\frac {1}{2}} \choose k}(-4x)^{k}\\[6pt]&=-{\frac {1}{2}}{{\frac {1}{2}} \choose n}(-4)^{n}\\[6pt]&={\frac {1}{n}}{2n-2 \choose n-1}\end{aligned}}$

नोट: अंकन [xⁿ] यफ(एक्स) एक्स के गुणांक को संदर्भित करता है यफ(एक्स) में।

वर्गमूल का श्रृंखला विस्तार द्विपद प्रमेय न्यूटन के सामान्यीकृत द्विपद प्रमेय पर आधारित है न्यूटन का द्विपद प्रमेय का सामान्यीकरण। द्विपद गुणांक का उपयोग करके चौथी से पाँचवीं पंक्ति में हेरफेर करने के लिए सामान्यीकरण और द्विपद श्रृंखला से संबंध की आवश्यकता है।

अंतिम पंक्ति पर व्यंजक कैटलन संख्या (एन − 1)^st के बराबर है इसलिए, p_n = c_n−1.

यह भी देखें

• बीजगणितीय कॉम्बिनेटरिक्स
• असिम्प्टोटिक कॉम्बिनेटरिक्स
• बर्नसाइड लेम्मा
• मिश्रित विस्फोट
• [[संयुक्त प्रजाति थ्योरी]]
• संयुक्त सिद्धांत
• मिश्रित प्रजातियां
• समावेश-बहिष्करण सिद्धांत
• विशिष्ट तत्व की विधि
• पोल्या गणना प्रमेय
• चलनी सिद्धांत

संदर्भ

• Zeilberger, Doron, Enumerative and Algebraic Combinatorics
• Björner, Anders and Stanley, Richard P., A Combinatorial Miscellany
• Graham, Ronald L., Grötschel M., and Lovász, László, eds. (1996). Handbook of Combinatorics, Volumes 1 and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-07169-X.
• Joseph, George Gheverghese (1994) [1991]. The Crest of the Peacock: Non-European Roots of Mathematics (2nd ed.). London: Penguin Books. ISBN 0-14-012529-9.
• Loehr, Nicholas A. (2011). Bijective Combinatorics. CRC Press. ISBN 143984884X, ISBN 978-1439848845.
• Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press. ISBN 0-521-55309-1, ISBN 0-521-56069-1.
• Goulden, Ian P. and Jackson, David M. (2004). Combinatorial Enumeration. Dover Publications. ISBN 0486435970.
• Riordan, John (1958). An Introduction to Combinatorial Analysis, Wiley & Sons, New York (republished).
• Riordan, John (1968). Combinatorial Identities, Wiley & Sons, New York (republished).
• Wilf, Herbert S. (1994). Generatingfunctionology (2nd ed.). Boston, MA: Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001.