कैटलन संख्याएं (Catalan numbers) संख्याओं का एक अनुक्रम है। कैटलन संख्याएं प्राकृतिक संख्याओं का एक अनुक्रम बनाती हैं जो विभिन्न गणना समस्याओं में होती हैं, अक्सर पुनरावर्ती रूप से परिभाषित वस्तुओं से जुड़ी होती हैं।
Cₙ लंबाई 2n के डाइक शब्दों (Dyck words) की संख्या है। एक डाइक शब्द n X's और n Y's से बना एक स्ट्रिंग है जैसे कि स्ट्रिंग का कोई प्रारंभिक खंड X's से अधिक Y's नहीं रखता। उदाहरण के लिए, लंबाई 6 के डाइक शब्द निम्नलिखित हैं
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
प्रतीक X को खुले पैरेंथेसिस और Y को बंद पैरेंथेसिस के रूप में पुनर्व्याख्या करते हुए, Cₙ सही ढंग से मिलान वाले n जोड़े पैरेंथेसिस वाले व्यंजकों की संख्या गिनता है
((())) ()(()) ()()() (())() (()())
Cₙ उन विभिन्न तरीकों की संख्या है जिनसे n + 1 कारकों को पूरी तरह से पैरेंथेसाइज़ किया जा सकता है (या एक बाइनरी ऑपरेटर के n अनुप्रयोगों को जोड़ने के तरीकों की संख्या)। n = 3 के लिए, उदाहरण के लिए, हमारे पास चार कारकों के पांच अलग-अलग पैरेंथेसाइज़ेशन हैं:
((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
एक बाइनरी ऑपरेटर के क्रमिक अनुप्रयोगों को पूर्ण बाइनरी ट्री के संदर्भ में दर्शाया जा सकता है। (एक रूटेड बाइनरी ट्री पूर्ण है यदि प्रत्येक वर्टेक्स के या तो दो बच्चे हैं या कोई बच्चे नहीं हैं।) इससे यह निकलता है कि Cₙ, n + 1 पत्तियों वाले पूर्ण बाइनरी ट्री की संख्या है:
नमूना
इनपुट - 6
आउटपुट - 1 1 2 5 14 42
व्याख्या
n = 0, 1, 2, 3,4,5,6,7,8,9,10, ... के लिए पहली कैटलन संख्याएं हैं
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,
उदाहरण
#include<iostream>
using namespace std;
long int catalan( int n) {
if (n <= 1){
return 1;
}
long int result = 0;
for (int i=0; i
आउटपुट
1 1 2 5 14 42
