Welkom
Voorkennis
Geschiedenis
In de combinatoriek vormen de Catalan-getallen een rij van natuurlijke getallen die voorkomen in diverse telproblemen. Deze getallen zijn vernoemd naar de Belgische wiskundige Eugène Catalan (1814–1894) genoemd.
Catalan maakte een belangrijke bijdragen aan de wiskunde, waaronder dus de Catalan-getallen, die voorkomen in verschillende gebieden van de combinatoriek en de meetkunde. Daarnaast ontwikkelde hij ook het vermoeden van Catalan, een stelling in de getaltheorie. Catalan wordt beschouwd als een van de belangrijkste wiskundigen van de 19e eeuw en zijn werk heeft een blijvende invloed gehad op de ontwikkeling van de wiskunde en haar toepassingen.
1. Problemen
We beginnen met een reeks problemen waarvan zal worden aangetoond dat deze volledig equivalent zijn. De oplossing voor elk probleem is dezelfde reeks getallen die de Catalaanse getallen worden genoemd. Verderop in deze les zullen we relaties en expliciete formules voor de Catalaanse getallen gaan afleiden.
1.1 Het Haakjesprobleem
Catalan is bekend geworden door de naar hem genoemde getallen. Een bekend voorbeeld daarbij is het haakjesprobleem. Bij Catalan ging het om het aantal manieren waarop je in een uitdrukking haakjes kunt plaatsen. De vraag is op hoeveel verschillende manieren de vermenigvuldiging uitgevoerd kan worden.
Een product \(x_1∙x_2∙x_4∙…..∙x_n \) kan op verschillende manieren uitgevoerd worden. Zo kan de vermenigvuldiging van een set van drie getallen: \(x_1∙x_2∙x_3 \) op twee verschillende manieren worden uitgevoerd: \(((x_1∙x_2)∙x_3) \) of \((x_1∙(x_2∙x_3))\).
Opdracht 1.
Stel dat je een set van \(n+1\) getallen hebt om samen te vermenigvuldigen. We definiëren \(a_n\) als het aantal verschillende manieren waarop de vermenigvuldiging \(x_1∙x_2∙x_4∙…..∙x_n \) uitgevoerd kan worden, waarbij de volgorde van de getallen zelf niet verandert. Werk nu eens voor \(0≤n≤4 \) de gevallen uit in onderstaand tabel.
| \(n\) |
\(a_n\) |
\(mogelijkheden\) |
| \(0 \) |
|
|
| \(1\) |
|
|
| \(2\) |
|
|
| \(3\) |
|
|
| \(4\) |
|
|
1.2 Bergtoppen
Hoeveel ‘’bergtoppen’’ kun je vormen met \(n\) opwaartse en \(n\) neerwaartse schuine strepen?
Opdracht 2.
Stel we definiëren nu \(a_n\) als het aantal verschillende manieren waarop er bergtoppen gevormd kunnen worden met \(n\) opwaartse en \(n\) neerwaartse schuine strepen.
Maak de tabel af voor \(0≤n≤4 \).
| \(n\) |
\(a_n\) |
\(mogelijkheden\) |
| \(0\) |
\(0\) |
\(*\) |
| \(1\) |
\(1\) |
|
| \(2\) |
\(2\) |
|
| \(3\) |
|
|
| \(4\) |
|
|
1.3 Handenschudden
Als \(2n\) mensen aan een ronde tafel zitten te vergaderen, op hoeveel manieren kunnen ze dan allemaal tegelijk iemand de hand schudden aan de ronde tafel, zodat geen van de armen elkaar kruisen?
Opdracht 3.
Stel \(a_n\) is het aantal manieren waarop \(2n\) mensen elkaar de hand kunnen schudden aan een ronde tafel, zonder dat armen elkaar kruisen. In de tabel zijn al het aantal mogelijkheden bepaald voor \(n=1\) en \(n=2\). Bepaal het aantal mogelijkheden voor \(n=3\) en \(4\) en vul de tabel verder in.
| \(n\) |
\(a_n\) |
\(mogelijkheden\) |
| \(1\) |
\(1\) |
|
| \(2\) |
\(2\) |
|
| \(3\) |
|
|
| \(4\) |
|
|
1.4 Polygoon
2. Recursieve definitie
De problemen uit de voorgaande paragraaf lijken allemaal dezelfde reeks getallen te genereren. Dit worden ook wel de Catalan getallen genoemd: 1, 2, 5, 14, 42, 132, 429, etc.. De vraag is natuurlijk of er ook een formule bestaat om de \(n\)-de Catalan getal te berekenen zonder het telkens te moeten uitwerken aan de hand van één van de problemen.
2.1 Het haakjesprobleem
Antwoorden
Uitwerkingen - Website.pdf
