S Wikipedije, slobodne enciklopedije
Catalanovi brojevi predstavljaju niz prirodnih brojeva važnih u kombinatorici . Prvih nekoliko Catalanovih brojeva jesu 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190.. Nazvani su u čast belgijskog matematičara Eugènea Charlesa Catalana .
Definišu se preko binomnih koeficijenata :
C
n
=
1
n
+
1
(
2
n
n
)
=
(
2
n
)
!
(
n
+
1
)
!
n
!
=
∏
k
=
2
n
n
+
k
k
{\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}={\frac {(2n)!}{(n+1)!n!}}=\prod _{k=2}^{n}{\frac {n+k}{k}}}
n
≥
0
{\displaystyle n\geq 0}
Alternativni izraz je:
C
n
=
(
2
n
n
)
−
(
2
n
n
+
1
)
{\displaystyle C_{n}={\binom {2n}{n}}-{\binom {2n}{n+1}}}
n
≥
0
{\displaystyle n\geq 0}
Catalanovi brojevi zadovoljavaju rekurziju:
C
0
=
1
,
C
n
+
1
=
∑
i
=
0
n
C
i
C
n
−
i
{\displaystyle C_{0}=1,C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}}
n
≥
0
{\displaystyle n\geq 0}
Kako je
(
2
n
n
)
=
∑
i
=
0
n
(
n
i
)
2
,
{\displaystyle {\tbinom {2n}{n}}=\sum _{i=0}^{n}{\tbinom {n}{i}}^{2},}
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}.}
Zadovoljavaju i sljedeću rekurziju
C
0
=
1
,
C
n
+
1
=
2
(
2
n
+
1
)
n
+
2
C
n
,
{\displaystyle C_{0}=1,C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},}
Generirajuća funkcija Catalanovih brojeva je:
∑
n
=
0
∞
C
n
z
n
=
1
−
1
−
4
z
2
z
.
{\displaystyle \sum _{n=0}^{\infty }C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.}
Asimptotska vrijednost je:
C
n
∼
4
n
n
3
/
2
π
.
{\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}.}
