Catalan-getal
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 (1814–1894) genoemd.
Het -de Catalan-getal wordt door de volgende formule met binomiaalcoëfficiënten gegeven
De eerste Catalan-getallen[1] 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 | brontekst bewerken]Een alternatieve uitdrukking is
Aan deze formule ziet men meteen dat een natuurlijk getal is, wat bij de eerder gegeven formule niet direct duidelijk is.
De Catalan-getallen voldoen ook aan de differentievergelijking:
Met de recursieve formule
kunnen de Catalan-getallen efficiënt worden berekend.
De Catalan-getallen gedragen zich asymptotisch als
- ,
in de zin dat het quotiënt van beide leden in de limiet voor naar 1 gaat.
De enige oneven Catalan-getallen[2] zijn die met ; alle andere zijn even.
Toepassingen in combinatoriek
[bewerken | brontekst bewerken]Allerlei telproblemen in de combinatoriek hebben Catalan-getallen als oplossingen. Hier zijn enkele voorbeelden, de meeste met illustratie van de gevallen en
- is het aantal correcte manieren om paren haakjes op te schrijven:
- is het aantal verschillende manieren waarop factoren compleet tussen haakjes kunnen worden gezet, zodanig dat er geen haakjes meer bij kunnen. Voor , bijvoorbeeld, zijn er de volgende vijf manieren om de factoren van haakjes te voorzien:
- Vergelijk het eerste voorbeeld met het aantal Dyck-woorden van lengte . Een Dyck-woord is een string die alleen uit X-en en Y's bestaat, op zo'n manier dat geen enkel begindeel van de string meer Y's dan X-en heeft. Er zijn bijvoorbeeld de volgende Dyck-woorden van lengte 6:
- is het aantal binaire bomen vanuit één punt met bladeren:
![](http://upload.wikimedia.org/wikipedia/commons/0/01/Catalan_number_binary_tree_example.png)
- is het aantal paden in een rooster van 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 zien:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f4/Catalan_number_4x4_grid_example.svg/450px-Catalan_number_4x4_grid_example.svg.png)
- is het aantal manieren waarop een convexe veelhoek met zijden in driehoeken langs de diagonalen kan worden verdeeld. De figuur toont het geval :
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Catalan_number_polygon_cut_into_triangles_example.svg/400px-Catalan_number_polygon_cut_into_triangles_example.svg.png)
- is het aantal manieren waarop een trapvorm van hoogte met rechthoeken kan worden betegeld. De figuur toont het geval .
![](http://upload.wikimedia.org/wikipedia/commons/c/cb/Catalan_stairstep_4.png)
Hankel-matrix
[bewerken | brontekst bewerken]De -Hankel-matrix met als elementen , heeft determinant 1, onafhankelijk van de waarde van . Voor bijvoorbeeld is
Merk op dat ook als de elementen worden "verschoven", zodat , de determinant dan nog steeds gelijk aan 1 is, onafhankelijk van de waarde van . Voor bijvoorbeeld is
Geschiedenis
[bewerken | brontekst bewerken]De rij van Catalan-getallen werd voor het eerst beschreven in 1751 in een brief aan Goldbach door Leonhard Euler, [3] die geïnteresseerd was in het verdelen van een veelhoek in driehoeken. De rij werd later naar Eugène Charles Catalan genoemd, die het verband met de uitdrukkingen met haakjes ontdekte, toen hij aan de Torens van Hanoi werkte. Johann Andreas von Segner vond in 1758 een recursieve formule, [4] waarvan Euler in de samenvatting bij Segner artikel de oplossing vermeldt. [5] Een door Johann Friedrich Pfaff opgestelde algemenere aftellingsmethode werd in 1795 door Nikolaus Fuß bewezen. [6] In de jaren 1838 en 1839 pakten Gabriel Lamé, [7] Olinde Rodrigues, [8] Jacques Binet [9] [10] en Eugène Catalan [11] [12] het probleem opnieuw op. Eugen Netto schreef in zijn in 1901 gepubliceerde leerboek over de combinatoriek de getallen aan Catalan toe. [13]
- Literatuur
- (fr) E Catalan in Journal für die reine und angewandte Mathematik. Note extraite d’une lettre adressée. 1844 27:192
- (en) Conway en Guy. The Book of Numbers, 1996. blz 96–106
- (en) M Gardner. Time Travel and Other Mathematical Bewilderments, 1988. ISBN 0-7167-1924-X
- Verwijzingen
- (en) RP Stanley Catalan addendum, 25 mei 2013. bij Enumerative Combinatorics, deel 2 blz 219–229 (pdf)
- (en) MathWorld. Catalan number.
- (en) RM Dickau. Catalan numbers.
- Voetnoten
- ↑ rij A000108 in OEIS
- ↑ rij A083003 in OEIS, de oneven Catalan-getallen
- ↑ Brief (PDF-Datei; 137 kB) von Euler an Goldbach vom 4. September 1751, abgedruckt in Paul Heinrich Fuss (Hrsg.): Correspondance mathématique et physique de quelques célèbres géomètres du XVIIIème siècle. (Band 1), St.-Pétersbourg 1843, p. 549–552.
- ↑ Ioh. Andr. de Segner: Enumeratio modorum quibus figurae planae rectilineae per diagonales dividuntur in triangula. Novi commentarii academiae scientiarum imperialis petropolitanae 7 pro annis 1758 et 1759, 1761, p. 203–210 (Latijn).
- ↑ Leonhard Euler: Summarium dissertationum. Novi commentarii academiae scientiarum imperialis petropolitanae 7 pro annis 1758 et 1759, 1761, p. 13–15 (Latijn).
- ↑ Nicolao Fuss: Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi queat. Nova acta academiae scientiarum imperialis petropolitanae 9, 1795, p. 243–251 (Latijn).
- ↑ Gabriel Lamé: Extrait d’une lettre de M. Lamé à M. Liouville sur cette question: Un polygone convexe étant donné, de combien de manières peut-on le partager en triangles au moyen de diagonales? Journal de mathématiques pures et appliquées 3, 1838, p. 505–507 (Frans).
- ↑ Olinde Rodrigues: Sur le nombre de manières de décomposer un polygone en triangles au moyen de diagonales und Sur le nombre de manières d’effectuer un produit de n facteurs. Journal de mathématiques pures et appliquées 3, 1838, p. 547–549 (Frans).
- ↑ J. Binet: Problèmes sur les polygones. Société philomathique de Paris – Séances de 1838 – Extraits des procès-verbaux, p. 127–129 (Frans).
- ↑ J. Binet: Réflexions sur le problème de déterminer le nombre de manières dont une figure rectiligne peut être partagée en triangles au moyen de ses diagonales. Journal de mathématiques pures et appliquées 4, 1839, p. 79–90 (Frans).
- ↑ E. Catalan: Note sur une équation aux différences finies. Journal de mathématiques pures et appliquées 3, 1838, p. 508–516, und 4, 1838, p. 95–99 (Frans).
- ↑ E. Catalan: Solution nouvelle de cette question: Un polygone étant donné, de combien de manières peut-on le partager en triangles au moyen de diagonales? Journal de mathématiques pures et appliquées 4, 1839, p. 91–94 (Frans).
- ↑ Eugen Netto: Lehrbuch der Combinatorik. B. G. Teubner, Leipzig 1901 (Toeschrijving aan Catalan in § 122, p. 192–194 en § 124, p. 195).