कैटालन संख्या

निम्नलिखित सम्बन्ध द्वारा पारिभाषित प्राकृतिक संख्याएँ कैटालन संख्याएँ (Catalan numbers) कहलाती हैं :

C_{n} = \frac{1}{n + 1} (\binom{2 n}{n}) = \frac{(2 n)!}{(n + 1)! n!} = \prod_{k = 2}^{n} \frac{n + k}{k} for n \geq 0 .

जहाँ C_n, nवीं कैटालन संख्या है। इनका नामकरण बेल्जियम के गणितज्ञ चार्ल्स कैटालन (1814–1894) के नाम पर किया गया है। n = 0, 1, 2, 3, … आदि के लिए कुछ आरम्भिक कैटालन संख्याएँ ये हैं-

1, 2, 5, 14, 42, 132, 429, 1430, 4862 आदि

गुण

C_n के लिए निम्नलिखित व्यंजक (expression) भी प्रयोग कर सकते हैं-

C_{n} = (\binom{2 n}{n}) - (\binom{2 n}{n + 1}) for n \geq 0,

यह उपरोक्त व्यंजक के तुल्य है क्योंकि

(\binom{2 n}{n + 1}) = \frac{n}{n + 1} (\binom{2 n}{n})

.

इससे स्पष्ट है कि C_n एक पूर्णांक है जो प्रथम सूत्र से साफ नहीं होता।

ये संख्याएँ निम्नलिखित पुनरावर्तन सम्बन्ध (recurrence relation) का पालन करतीं हैं-

C_{0} = 1 and C_{n + 1} = \sum_{i = 0}^{n} C_{i} C_{n - i} for n \geq 0;

इसके अतिरिक्त,

C_{n} = \frac{1}{n + 1} \sum_{i = 0}^{n} {(\binom{n}{i})}^{2} .

C_{0} = 1 and C_{n + 1} = \frac{2 (2 n + 1)}{n + 2} C_{n},

साँचा:आधार

कैटालन संख्या

गुण

नैविगेशन मेन्यू

खोजें