मुक्त ज्ञानकोश विकिपीडिया से
निम्नलिखित सम्बन्ध द्वारा पारिभाषित प्राकृतिक संख्याएँ कैटालन संख्याएँ (Catalan numbers) कहलाती हैं :
C
n
=
1
n
+
1
(
2
n
n
)
=
(
2
n
)
!
(
n
+
1
)
!
n
!
=
∏
k
=
2
n
n
+
k
k
for
n
≥
0.
{\displaystyle 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
=
(
2
n
n
)
−
(
2
n
n
+
1
)
for
n
≥
0
,
{\displaystyle C_{n}={2n \choose n}-{2n \choose n+1}\quad {\text{ for }}n\geq 0,}
यह उपरोक्त व्यंजक के तुल्य है क्योंकि
(
2
n
n
+
1
)
=
n
n
+
1
(
2
n
n
)
{\displaystyle {\tbinom {2n}{n+1}}={\tfrac {n}{n+1}}{\tbinom {2n}{n}}}
इससे स्पष्ट है कि C n पूर्णांक है जो प्रथम सूत्र से साफ नहीं होता।
ये संख्याएँ निम्नलिखित पुनरावर्तन सम्बन्ध (recurrence relation) का पालन करतीं हैं-
C
0
=
1
and
C
n
+
1
=
∑
i
=
0
n
C
i
C
n
−
i
for
n
≥
0
;
{\displaystyle 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
=
1
n
+
1
∑
i
=
0
n
(
n
i
)
2
.
{\displaystyle C_{n}={\frac {1}{n+1}}\sum _{i=0}^{n}{n \choose i}^{2}.}
C
0
=
1
and
C
n
+
1
=
2
(
2
n
+
1
)
n
+
2
C
n
,
{\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},}
