Catalan-getal: verschil tussen versies

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\geq 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

Een alternatieve uitdrukking voor C_n is

C_{n}={2n \choose n}-{2n \choose n-1}\quad {\mbox{ voor }}n\geq 1.

Aan deze formule zien we direct dat C_n 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\geq 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

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

C_n 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 C_n ook het aantal correcte manieren om n paren haakjes op te schrijven:

((())) ()(()) ()()() (())() (()())

C_n 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))

C_n is het aantal binaire bomen vanuit één punt met n + 1 bladeren:

C_n 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:

C_n 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:

C_n is het aantal manieren waarop een trapvorm van hoogte n kan worden betegeld met n rechthoeken. De figuur toont het geval n = 4.

Hankel-matrix

De n×n Hankel-matrix waarin het element (i, j) het Catalan-getal C_i+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 C_i+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

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

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 (1988). Time Travel and Other Mathematical Bewilderments. W.H. Freeman and Company, New York, Ch. 20. ISBN 0-7167-1924-X.

Stanley, R.P. (1999): Enumerative Combinatorics, Vol. 2. Cambridge University Press. (pp. 219–229)

Externe links

Stanley, Richard P.: Catalan addendum bij Enumerative Combinatorics, Volume 2
Mathworld
Dickau, Robert M.: Catalan numbers
Davis, Tom: Catalan numbers.

Bronnen, noten en/of referenties

↑ rij A000108 in OEIS
↑ rij A083003 in OEIS

[1] rij A000108 in OEIS

[2] rij A083003 in OEIS

[1]

[2]

@@ Regel 97: / Regel 97: @@
 [[Categorie:Combinatoriek]]
-[[Categorie:Getal]]
+[[Categorie:Rij van gehele getallen]]
-[[Categorie:Meetkunde]]

Versie van 9 mrt 2015 15:51