Catalan-getal

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de combinatoriek vormen de Catalan-getallen een rij van natuurlijke getallen die voorkomen in diverse telproblemen. Ze zijn vernoemd naar de Belgische wiskundige Eugène Charles Catalan (1814–1894).

Het ne Catalan-getal wordt gegeven door de volgende formule met binomiaalcoëfficiënten

C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ voor }n\ge 0.

De eerste Catalan-getallen [1] voor n = 0, 1, 2, 3, … zijn

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

Eigenschappen[bewerken]

Een alternatieve uitdrukking voor Cn is

C_n = {2n\choose n} - {2n\choose n-1} \quad\mbox{ voor }n\ge 1.

Aan deze formule zien we direct dat Cn een natuurlijk getal is, wat uit de eerdere formule niet a priori duidelijk is.

De Catalan-getallen voldoen ook aan de volgende recursieve formule

C_0 = 1 \quad \mbox{ en } \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\mbox{ voor }n\ge 0.

Ook de volgende formule geldt

C_0 = 1 \quad \mbox{ en } \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,

hiermee kunnen de Catalan-getallen efficiënter berekend worden.

De Catalan-getallen groeien asymptotisch als

C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}

in de zin dat het quotiënt van het ne Catalan-getal en de rechter uitdrukking naar 1 gaat voor n → ∞.

De enige Catalan-getallen C_n die oneven zijn [2], zijn die met n=2^k-1. Alle andere zijn even.

Toepassingen in combinatoriek[bewerken]

Allerlei telproblemen in de combinatoriek hebben Catalan-getallen als oplossingen. Hier zijn enkele voorbeelden, de meeste met illustratie van de gevallen C3 = 5 and C4 = 14.

  • Cn is het aantal Dyck-woorden van lengte 2n. Een Dyck-woord is een string bestaamde uit n X-en en n Y's, zodat geen enkel begindeel van de string meer Y's dan X-en heeft. Bijvoorbeeld, er zijn de volgende Dyck-woorden van lengte 6:
XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.
  • Door in het vorige voorbeeld elke X als haakje openen en Y als haakje sluiten te interpreteren, is Cn ook het aantal correcte manieren om n paren haakjes op te schrijven:
((()))     ()(())     ()()()     (())()     (()())
  • Cn is ook het aantal verschillende manieren waarop n + 1 factoren compleet tussen haakjes kunnen worden gezet, zodat er geen haakjes meer bij kunnen. Voor n = 3, bijvoorbeeld, krijgen we de volgende vijf manieren om de factoren van haakjes te voorzien:
((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))
  • Cn is het aantal binaire bomen vanuit één punt met n + 1 bladeren:
Catalan number binary tree example.png
  • Cn is het aantal paden in een rooster van n × n vierkante cellen die de punten linksonder en rechtsboven verbindt door alleen naar links en naar boven te gaan, zonder boven de diagonaal uit te komen. De volgende figuur laat het geval n = 4 zien:
Catalan number 4x4 grid example.svg
  • Cn is het aantal manieren waarop een convexe veelhoek met n + 2 zijden in driehoeken kan worden verdeeld langs de diagonalen. De figuur toont het geval n = 3:
Catalan number polygon cut into triangles example.svg
  • Cn is het aantal manieren waarop een trapvorm van hoogte n kan worden betegeld met n rechthoeken. De figuur toont het geval n = 4.
Catalan stairstep 4.png

Hankel-matrix[bewerken]

De n×n Hankel-matrix waarin het element (ij) het Catalan-getal Ci+j is, heeft determinant 1, onafhankelijk van de waarde van n. Bijvoorbeeld, voor n = 4 vinden we

\det\begin{bmatrix}1 & 1 & 2 & 5 \\ 1 & 2 & 5 & 14 \\ 2 & 5 & 14 & 42 \\ 5 & 14 & 42 & 132\end{bmatrix} = 1.

Merk op dat als de elementen worden "verschoven", zodat we de Catalan-getallen Ci+j+1 nemen, dat de determinant dan nog steeds gelijk is aan 1, onafhankelijk van de waarde van n. Bijvoorbeeld, voor n = 4 vinden we

\det\begin{bmatrix}1 & 2 & 5 & 14 \\ 2 & 5 & 14 & 42 \\ 5 & 14 & 42 & 132 \\ 14 & 42 & 132 & 429 \end{bmatrix} = 1.

De Catalan-getallen vormen de unieke rij met deze eigenschap.

Geschiedenis[bewerken]

De rij van Catalan-getallen werd voor het eerst beschreven in de achttiende eeuw door Leonhard Euler, die geïnteresseerd was in het verdelen van een veelhoek in driehoeken. De rij werd vernoemd naar Eugène Charles Catalan, die het verband ontdekte met de uitdrukkingen met haakjes, toen hij werkte aan de Torens van Hanoi.

Bronnen[bewerken]

  • Catalan, Eugene. (1844): Note extraite d’une lettre adress´ee. J. Reine Angew. Math., 27:192.
  • Conway and Guy, The Book of Numbers. New York: Copernicus, pp. 96–106, 1996.
  • Gardner, Martin, Time Travel and Other Mathematical Bewilderments, W.H. Freeman and Company, New York, 1988, p. Ch. 20 ISBN 0-7167-1924-X.
  • Stanley, R.P. (1999): Enumerative Combinatorics, Vol. 2. Cambridge University Press. (pp. 219–229)

Externe links[bewerken]

Bronnen, noten en/of referenties
  1. rij A000108 in OEIS
  2. rij A083003 in OEIS