कैटलन नंबर कहां पाए जाते हैं?
-कोष्ठकों के जोड़े की दी गई संख्या के साथ psp की संख्या
-दिए गए पत्तों की संख्या वाले बाइनरी ट्री की संख्या
- n * n वर्ग में निचले बाएँ कोने से ऊपरी दाएँ कोने तक के पथों की संख्या जो विकर्ण को स्पर्श नहीं करते हैं
-त्रिकोणों में n-गॉन के विभाजनों की संख्या
कैसे गिनें?1) nth कैटलन संख्या के लिए सूत्र:
2)
• आइए 2n लंबाई का एक PSS लें
•जाहिर तौर पर यह एक ओपनिंग ब्रेस के साथ शुरू होता है
•तो, कहते हैं पी = (ए)बी, जहां ए और बी – भी psp (इसके अलावा, A और B खाली हो सकते हैं)
•यदि A की लंबाई = 2k है, तो अनुक्रम A की रचना Ck तरीकों से की जा सकती है
•फिर B की लंबाई = 2(n – k - 1) और B की रचना Cn-k-1 तरीकों से की जा सकती है
•हम dp के लिए सूत्र देखते हैं: Cn = sum(Ck * Cn-k-1) for all k <
उपयोग किया गया सामन: