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

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

<math>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\ge 0.</math>

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

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

गुण

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

<math>C_n = {2n\choose n} - {2n\choose n+1} \quad\text{ for }n\ge 0,</math>

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

<math>\tbinom{2n}{n+1}=\tfrac{n}{n+1}\tbinom{2n}n</math>.

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

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

<math>C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0;</math>

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

<math>C_n= \frac 1{n+1} \sum_{i=0}^n {n \choose i}^2.</math>

<math>C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,</math>