Welkom
Welkom bij deze mini-les over Catalan-getallen. In deze les zul je leren wat Catalan-getallen zijn, hoe deze zichtbaar zijn bij diverse telproblemen in de combinatoriek en bestuderen we een aantal formules om de Catalan-getallen te bepalen.
In deze les zijn een aantal activiteiten en verwerkingsopdrachten verwerkt die achter elkaar doorlopen moeten worden. De bedoeling is dat de verwerkingsopdrachten uiteindelijk ingeleverd worden om beoordeeld te worden, van de activiteiten zijn de uitwerkingen te vinden op de website.
Laten we eerst beginnen met het oplossen van een wiskundig vraagstuk uit het 6-vwo examen wiskunde A.
Blikstapelingen
Bij het spel blikgooien krijgt de speler één of meer ballen waarmee hij of zij
moet proberen zoveel mogelijk blikken van een toren af te gooien. Zo’n toren is altijd op dezelfde manier opgebouwd: op de onderste laag staat een aantal blikken en op de lagen erboven steeds één minder. Op de foto zie je een toren met zes blikken.
We nemen in deze opgaven aan dat, als een bal de toren raakt, de onderste laag in zijn geheel blijft staan. Neem aan dat een geraakt blik ook werkelijk van de toren afvalt en nooit ‘’mooi’’ op een lager gelegen laag terechtkomt en
ook dat blikken niet blijven staan als één of meer blikken eronder wegvallen.
Lars gooit één bal naar een toren met zes blikken, zoals op de foto. Na zijn worp blijft de onderste laag van drie blikken staan. Er zijn nu vijf mogelijkheden voor de overgebleven toren. Drie van deze mogelijkheden zijn in figuur 1a, 1b en 1c schematisch getekend.
Activiteit 1. Teken de andere twee mogelijkheden
We gaan in deze opgave deze situatie wat theoretischer bekijken. We tellen het aantal mogelijke stapelingen van blikken op een onderste laag van \(n\) blikken. Hierbij staat vanaf de tweede laag ieder blik steeds boven op twee onderliggende blikken. We nemen steeds aan dat er één keer gegooid is en dat de hele onderste laag is blijven staan.
Voor \(n=1\) is er maar één blik, dus is er ook één mogelijke stapeling.
Voor \(n=2\) zijn er twee mogelijke stapelingen. Zie figuur 2.
Je kunt nu met een redenering nagaan dat het aantal mogelijke stapelingen voor \(n=3\) gelijk is aan 5. Deze redenering gaat als volgt:
- Er is één manier met 3 blikken op de onderste laag en 0 blikken op de tweede laag.
- Er zijn twee manieren met 3 blikken op de onderste laag en 1 blik op de tweede laag.
- Er is één manier met 3 blikken op de onderste laag en 2 blikken op de tweede laag (figuur 1b).
- Er is één manier met 3 blikken op de onderste laag, 2 blikken op de tweede laag en 1 blik op de derde laag (figuur 1a).
Dat is samen \(1+2+1+1=5\) mogelijkheden.
Voor \(n=4\) is het aantal mogelijke stapelingen gelijk aan 14.
Activiteit 2. Toon dit aan.
(Hint: Teken eventueel een aantal mogelijkheden)
Voorkennis
Voordat je verder kunt met deze mini-les heb je wel enige voorkennis nodig over recurrente betrekkingen. Je weet wat een recurrente betrekking is en kunt met behulp van de recurrente betrekking diverse termen berekenen onder een beginvoorwaarden. Zie eventueel volgend filmpje.
Daarnaast kun je voor praktische vraagstukken een recurrente betrekking opstellen, zie filmpje, of een combinatorisch argument gebruiken om te bewijzen dat de recurrente betrekking bij de rij hoort. Zie eventueel leereenheid 3.
Daarnaast kun je bij een gegeven identiteit een algebraïsch bewijs leveren om aan te tonen dat ze identiek zijn.
Leerdoelen
In deze mini-les:
- Werf je inzicht in de Catalan-getallen.
- Leer je de recurrente betrekking van de Catalan-getallen te verklaren en op te stellen.
- Werf je inzicht in de verschillende formules voor Catalan-getallen.
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. Telproblemen
We beginnen met een paar telproblemen waarvan zal worden aangetoond dat deze volledig equivalent zijn (net als het telprobleem bij activiteit 2). De oplossing voor elk probleem is namelijk dezelfde reeks getallen die de Catalan-getallen worden genoemd. Daarnaast zullen we verderop in deze les de relaties en expliciete formules voor de Catalan-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 daarbij 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))\).
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. Als we voor \(n=1, 2, 3, 4\) de mogelijkheden uitwerken dan krijgen we de volgende tabel.
Net als bij activiteit 2 lijkt bij dit telprobleem een getallenreeks te ontstaan voor \(a_n\).
1.2 Bergtoppen
Hoeveel ‘’bergtoppen’’ kun je vormen met \(n\) opwaartse en \(n\) neerwaartse schuine strepen?
Verwerkingsopdracht 1.
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. Hieronder zijn voor \(n=1\) en \(n=2\), \(a_n\) al uitgewerkt. Bepaal \(a_n\) voor de overige \(n\) in onderstaand tabel.
| \(n\) |
\(a_n\) |
\(mogelijkheden\) |
| \(0\) |
\(0\) |
\(*\) |
| \(1\) |
\(1\) |
|
| \(2\) |
\(2\) |
|
| \(3\) |
|
|
| \(4\) |
|
|
2. Recursieve definitie
De telproblemen uit de voorgaande paragraaf lijken allemaal dezelfde reeks getallen te genereren (In het facultatieve gedeelte zijn er nog twee telproblemen te vinden voor de liefhebber).
Dit worden ook wel de Catalan-getallen genoemd: 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, …
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. De Belgische wiskundige Charles Catalan ontdekte in de 19e eeuw de volgende formule voor deze Catalan-getallen:
Activiteit 3.
Bereken met behulp van bovenstaande formule \(C_4\).
We gaan nu met behulp van de recursieve formule voor Catalan-getallen aantonen dat een telprobleem uit hoofdstuk 1 voldoet aan dezelfde formule, waardoor het telprobleem dezelfde reeks getallen zal genereren als de Catalan-getallen. Bij het facultatieve gedeelte op deze website wordt dit gedaan voor een telprobleem over handenschudden.
2.1 Het haakjesprobleem
Bij het haakjesprobleem was de vraag op hoeveel verschillende manieren de vermenigvuldiging \(x_1∙x_2∙x_4∙…..∙x_n\) uitgevoerd kan worden bij een set van \(n+1\) getallen, waarbij \(a_n\) het aantal manieren is waarop we een product van \(n\) factoren kunnen berekenen. We zagen dat bij een set waarbij \(n=1,2,3\) of \(4\) geldt dat \(a_0=1,a_1=1, a_2=2, a_3=5 \), en \(a_4=14\) (zie eventueel paragraaf 1.1). Deze zijn voortgekomen bij het uitwerken van een aantal gevallen.
Activiteit 4.
Noem \(a_n\) het aantal verschillende manieren waarop de vermenigvuldiging van \(x_1∙x_2∙x_4∙…..∙x_n\) uitgevoerd kan worden. Waarbij de volgorde van de getallen zelf niet verandert. Stel een recurrente betrekking voor \(a_n\) op voor \(n≥1\).
Verwerkingsopdracht 2.
Toon aan dat de recurrente betrekken van opdracht 8 dezelfde getallen genereert als die van de Catalan-getallen:
3. Een andere formule
We bestuderen hier een andere benadering van de formule voor de Catalan-getallen.
3.1 Bergtoppen
Activiteit 5.
Bereken \(C_1\) t/m \(C_4\) met behulp van bovenstaande gevonden formule.
Verwerkingsopdracht 3.
Verklaar waarom geldt dat:
Verwerkingsopdracht 4.
Bewijs dat:
4. Facultatief
In dit onderdeel zijn er nog een aantal telproblemen te vinden waarbij de Catalan-getallen ook tevoorschijn komen. De bijbehorende opdrachten kunnen worden gemaakt, maar zijn facultatief. De uitwerkingen van deze opgaven zijn te vinden bij de uitwerkingen.
4.1 Telprobleem - 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, zonder dat er armen elkaar kruisen.
Stel \(n=1\) dan kan dat maar op één manier, zie afbeelding hieronder.
Stel \(n=2\) dan zitten er vier mensen aan tafel en zijn er twee manieren waarop ze elkaar de hand kunnen geven, zonder dat hun handen elkaar kruisen, zie afbeelding hieronder.
Facultatief activiteit 1.
Stel \(a_n\) is het aantal manieren waarop \(2n\) mensen elkaar de hand kunnen schudden aan een ronde tafel, zonder dat armen elkaar kruisen. Bepaal het aantal mogelijkheden voor \(n=3\) en \(4\) en vul de tabel verder in, teken daarbij de mogelijkheden!
| \(n\) |
\(a_n\) |
\(mogelijkheden\) |
| \(1\) |
\(1\) |
|
| \(2\) |
\(2\) |
|
| \(3\) |
|
|
| \(4\) |
|
|
4.2 Telprobleem - Polygoon
Op hoeveel manieren kan een polygoon of veelhoek met \(n+2\) zijden verdeeld worden in driehoeken met behulp van diagonalen, zonder dat de diagonalen elkaar kruisen.
Facultatief activiteit 2.
Stel \(a_n\) is het aantal manieren waarop een veelhoek met \(n+2\) zijden verdeeld kan worden in driehoeken met behulp van diagonalen, onder de voorwaarden dat de diagonalen elkaar niet mogen kruisen. Bepaal het aantal mogelijkheden voor \(n=1, 2, 3\) en \(4\) en teken de mogelijkheden.
4.3 Recursieve definitie - Handenschudden
Om een recurrente betrekking op te stellen voor het aantal handdrukken als er \(a_n\) mensen om een ronde tafel zitten te bepalen (zie paragraaf 4.1) kunnen we een soort gelijke analyse loslaten als bij paragraaf 2.1.
Facultatief activiteit 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. Stel een recurrente betrekking op voor \(a_n\) en toon daarmee aan dat deze hetzelfde is als die van de Catalan-getallen.
Uitwerkingen activiteiten
.
Uitwerkingen Activiteiten - Website.pdf
