कैटलन संख्या

निस्संदेह, सबसे उल्लेखनीय गणितीय तथ्य पहचान है । इसमें, आश्चर्यजनक रूप से, गणित के विभिन्न क्षेत्रों से प्रतीत होता है कि पूरी तरह से असंबंधित स्थिरांक। इस पहचान को साबित करना इतना मुश्किल नहीं है, लेकिन इसे समझने के लिए कुछ ही प्रबंध हैं, सबसे गहरे अर्थ को समझें।
एक और उल्लेखनीय तथ्य के रूप में, मैं कैटलन की संख्या को याद करना चाहूंगा, जो आश्चर्यजनक रूप से विभिन्न प्रकार की दहनशील समस्याओं के रूप में सामने आती है। दुर्भाग्य से, वे एक विशिष्ट स्कूल पाठ्यक्रम के विचार से बाहर हैं, लेकिन मुझे यकीन है कि किसी भी कंप्यूटर विज्ञान विशेषज्ञ को उनसे परिचित होना चाहिए।

कैटलन संख्या स्वयं सूत्र C (n) = (2n) /! N (! (N + 1) द्वारा व्यक्त की गई है; जहाँ विस्मयादिबोधक बिंदु, हमेशा की तरह, एक भाज्य को दर्शाता है। अनुक्रम की शुरुआत इस तरह दिखती है: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 ...
अंग्रेजी विकिपीडिया का दावा है कि कम से कम 66 अलग-अलग डिज़ाइन ज्ञात हैं जो कैटलन संख्याओं की उपस्थिति का कारण बनते हैं। यहाँ उनमें से कुछ हैं:

• सही कोष्ठक क्रम कोष्ठक खोलने और बंद करने के सेट हैं जिसमें प्रत्येक खोलने वाले कोष्ठक एक समापन से मेल खाते हैं। कैटलन संख्या द्वारा ब्रैकेट के जोड़े की निश्चित संख्या के साथ संभावित अनुक्रमों की संख्या व्यक्त की जाती है। उदाहरण के लिए, चार जोड़ी कोष्ठकों के 14 सही क्रम:
  (((((()))), ((() () () () () () ((())) () () () () () () () ()), (() () (),
  (() () (), () () () () () (() (), () () () () () () () () () () () ()), () () () ()
  
  
• बाइनरी पेड़ - पेड़, जिनमें से प्रत्येक नोड से (पत्तियों को छोड़कर) बिल्कुल दो शाखाएं निकलती हैं। दी गई संख्या के साथ बाइनरी पेड़ों की संख्या कैटलन की संख्या है। आंकड़ा प्रत्येक में 4 पत्तियों के साथ पांच पेड़ दिखाता है।
  
  इस तरह के पेड़ों की चर्चा पहले ही होबे पर की गई थी
  
  
• कोई पेड़। दी गई संख्या के साथ गैरिसोमोर्फिक पेड़ों की संख्या भी कैटलन की संख्या के बराबर है। ऐसे पेड़ों पर भी चर्चा हुई।
  
  
• एक वर्ग में मोनोटोन पथ - वर्ग के निचले बाएं कोने से ऊपरी दाएं तक के मार्ग, जो ग्रिड लाइनों को ऊपर या दाईं ओर का पालन करते हैं और विकर्ण के ऊपर नहीं जाते हैं। आंकड़ा एक 3x3 वर्ग के लिए ऐसे सभी पथ दिखाता है।
  
  
  
• बहुभुज त्रिभुज। विकर्णों द्वारा उत्तल बहुभुज के विभिन्न त्रिभुजों की संख्या कैटलन संख्या के बराबर होती है।
  
  
  
• बहुभुज के शीर्षों को जोड़े में विभाजित करना। सर्कल पर अंकों की एक संख्या को असंतुष्ट जीवा के साथ जोड़े में जोड़ा जा सकता है। ऐसे संघों की संख्या कैटलन की संख्या के बराबर भी है।
  
  
  
• यंग टेबल एक आयत है जो लगातार संख्याओं से भरी होती है ताकि वे सभी पंक्तियों और स्तंभों में विकसित हों। कैटलन संख्या द्वारा 2xn यंग टेबल की संख्या भी व्यक्त की जाती है।
  
  

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

अनुपालन १

ब्रैकेट अनुक्रमों और नीरस वर्ग पथ के बीच पत्राचार का निर्माण करना बहुत आसान है। ब्रैकेट अनुक्रम को बाएं से दाएं पढ़ना, हम निचले बाएं कोने से शुरू होने वाले मार्ग का निर्माण करेंगे - प्रत्येक उद्घाटन ब्रैकेट के लिए हम एक क्षैतिज खंड खींचते हैं, एक समापन ब्रैकेट के लिए - ऊर्ध्वाधर।
चूंकि अनुक्रम में कोष्ठक खोलने और बंद करने की समान संख्या थी, इसलिए मार्ग ऊपरी दाएं कोने में समाप्त हो जाएगा, और तथ्य यह है कि प्रत्येक उद्घाटन ब्रैकेट संबंधित क्लोजिंग ब्रैकेट की तुलना में पहले है (क्योंकि अनुक्रम सही है) यह सुनिश्चित करता है कि रास्ता नहीं जाता है वर्ग का ऊपरी आधा। जाहिर है, यह निर्माण प्रतिवर्ती है और प्रत्येक मोनोटोन पथ से एक ब्रैकेट अनुक्रम प्राप्त किया जा सकता है।
उपरोक्त आकृति में, संबंधित कोष्ठक और रेखा खंड एक रंग में चिह्नित हैं। यह स्पष्ट रूप से देखा जाता है कि कोष्ठक की एक जोड़ी के समान खंड "एक दूसरे को देखते हैं":

अनुपालन २

दूसरी समस्या के रूप में, हम सही ब्रैकेट अनुक्रमों और 2xn युंगम तालिकाओं के बीच एक पत्राचार का निर्माण करते हैं। यहाँ भी, सब कुछ सरल है। हम कोष्ठक को बाएं से दाएं की संख्या देते हैं। यदि ब्रैकेट खुल रहा है, तो शीर्ष पंक्ति पर उसके अनुरूप संख्या लिखें। अगर यह बंद हो जाता है, तो नीचे तक। चूँकि i-th ओपनिंग ब्रैकेट हमेशा i-th क्लोजिंग ब्रैकेट के बाईं ओर होता है, इसलिए ओपनिंग ब्रैकेट से संबंधित संख्या क्लोजिंग नंबर की तुलना में कम होगी। तो, तालिका में शीर्ष संख्या एक ही कॉलम में नीचे से कम होगी, यानी सही ब्रैकेट अनुक्रम से, हमें यंग टेबल मिला। यह निर्माण प्रतिवर्ती भी है, जिसका अर्थ है कि एक-से-एक पत्राचार प्राप्त किया जाता है।

अनुपालन ३

अब आइए बाइनरी पेड़ों से निपटते हैं। सजातीय संचालन के साथ एक अभिव्यक्ति में द्विआधारी पेड़ों और कोष्ठकों के बीच पत्राचार को देखना बहुत आसान है, लेकिन इससे थोड़ा सा अनुक्रम प्राप्त होता है। बाइनरी पेड़ों को सही ब्रैकेट अनुक्रमों से बांधने के लिए, आपको थोड़ा अलग दृष्टिकोण का उपयोग करने की आवश्यकता है। हम ट्रावेलर क्रम में मानक ट्री ट्रैवर्सल और संख्याओं का उपयोग करेंगे (हम रूट को 0 के रूप में लेंगे)। अब, यदि संख्या में परिवर्तन के दौरान हम माता-पिता से बच्चे तक चले गए, तो हमने उद्घाटन ब्रैकेट को i-th स्थान पर रखा। अन्यथा, समापन सेट करें।

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

अनुपालन ४

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

जैसा कि आप देख सकते हैं, परिणामस्वरूप विभाजन में प्रत्येक त्रिभुज के तीन पक्ष एक मूल नोड और उसके दो वंशों के अनुरूप हैं। इसलिए, यदि आप दो अलग-अलग पेड़ लेते हैं, तो आपको दो अलग-अलग विभाजन मिलते हैं।

एक उपसंहार के बजाय

खैर, निष्कर्ष में, मैं एक प्लेट दूंगा जो तीसरे नंबर के कैटलन के लिए वस्तुओं के पत्राचार को दर्शाता है।