In de combinatoriek vormen de Catalan-getallen een rij van natuurlijke getallen die voorkomen in diverse telproblemen. Ze zijn naar de Belgische wiskundige Eugène Catalan genoemd.
Deze getallen kunnen recursief berekend worden via deze formule:
\[\mathsf{C_{n+1} = \dfrac{2\cdot(2n+1)}{n+2} \cdot C_{n} \qquad\text{\textsf{met}}\qquad C_0 = 1}\]Wat resulteert in deze rij:
\[\mathsf{1,\qquad 1,\qquad 2,\qquad 5,\qquad 14,\qquad 42,\qquad 132,\qquad 429,\qquad \ldots}\]Opgave
Schrijf een recursieve functie catalan(n) die voor een natuurlijk getal n, het Catalan-getal met rangnummer n teruggeeft.
Voorbeelden
>>> catalan(1)
1
>>> catalan(6)
132