De getallen van Catalan

De getallen van Catalan

De getallen $B(n)$ zijn nauw verwant met de Catalan-getallen. Het $n$-de Catalan-getal is als volgt gedefinieerd:

$$C(n)= \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{n!(n+1)!}$$

voor $n ≥ 1$. Per definitie is $C(0) = 1$.

De rij Catalan-getallen begint dus zo:

$$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, ...$$

In de OEIS vind je deze rij onder nummer A000108. Hier staan vijf toepassingen van de Catalan-getallen.

C(n) is het aantal manieren waarop 2n personen aan een
ronde tafel simultaan elkaar de hand kunnen schudden
(eventueel over de tafel heen) zonder kruisingen.
 
C(n) is het aantal manieren om getallen met n cijfers te vormen
van de vorm $a_1 a_2 ... a_n$ met alle $a_i$’s minstens gelijk
aan $1, a_1 ≤ a_2 ≤ ... ≤ a_n$ en $a_i ≤ i$.
 
C(n) is het aantal manieren om munten te stapelen
(zoals sinaasappels) als je onderaan begint met een rij met n munten.
 
C(n) is het aantal manieren om paren haakjes te
plaatsen in een product met n + 1 factoren.
 
C(n) is het aantal manieren om 2n punten gelegen op een horizontale
lijn twee per twee te verbinden met boogjes die elkaar
niet snijden (waarbij de boogjes boven de punten liggen).