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

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

$C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}\qquad {\mbox{ 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}={2n \choose n}-{2n \choose n+1}\quad {\text{ for }}n\geq 0,$

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

${\tbinom {2n}{n+1}}={\tfrac {n}{n+1}}{\tbinom {2n}{n}}$.

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

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

$C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0;$

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

$C_{n}={\frac {1}{n+1}}\sum _{i=0}^{n}{n \choose i}^{2}.$

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