Catalan-Zahl

Die Catalan-Zahlen oder catalanschen Zahlen bilden eine Folge natürlicher Zahlen, die in vielen Problemen der Kombinatorik auftritt und eine ähnlich wichtige Rolle wie die Binomialkoeffizienten oder die Fibonacci-Zahlen spielt. Sie sind nach dem belgischen Mathematiker Eugène Charles Catalan benannt.

Die Folge der Catalan-Zahlen ${\displaystyle C_{0},C_{1},C_{2},C_{3},\dotsc }$ beginnt mit

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, … (Folge A000108 in OEIS)

Die Catalan-Zahlen sind für ${\displaystyle n\geq 0}$ gegeben durch

${\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}={\frac {(2n)!}{(n+1)!\,n!}},}$

wobei ${\displaystyle {\tbinom {2n}{n}}}$ der mittlere Binomialkoeffizient ist. Mit ${\displaystyle {\tbinom {2n}{n+1}}={\tfrac {n}{n+1}}{\tbinom {2n}{n}}}$ erhält man, dass die Formel äquivalent zu

${\displaystyle C_{n}={\binom {2n}{n}}-{\binom {2n}{n+1}}}$

ist und somit tatsächlich nur ganze Zahlen liefert.