] >
Een stack is een belangrijke datastructuur in de informatica. Er kunnen data in worden opgeslagen met de beperking dat toevoegingen en weglatingen slechts aan één uiteinde van de stack (de zogeheten top) kunnen plaatsvinden. We gaan de getallen t/m in die volgorde op een stack plaatsen en gaan het aantal volgordes tellen waarmee ze de stack kunnen verlaten. We beschrijven dat met schijven genummerd van t/m . Deze staan in Figuur 9.5 op pin 1.
Pin 2 is de stack waar de schijven één voor één op komen door ze van pin 1 naar pin 2 te verplaatsen. Staan er schijven op pin 2, dan kan de bovenste van deze schijven de pin verlaten. We plaatsen hem dan op pin 3 zodat op deze pin de schijven van onderen naar boven gerangschikt zijn in de volgorde waarin ze de stack (pin 2) hebben verlaten. Hoeveel van deze rangschikkingen kunnen zo ontstaan?
Een eindstand wordt bereikt na precies zetten. Om iedere tussenstand en iedere eindstand te beschrijven kun je de ‘geschiedenis’ geven die tot die stand heeft geleid. Er zijn twee typen zetten:
Met een rijtje van nullen en enen kan dan aangegeven worden welke zetten er zijn gedaan en ook in welke volgorde. Het rijtje 001011010 geeft dan aan dat er eerst twee keer een schijf van pin 1 naar pin 2 is verplaatst, dan een van 2 naar 3, een van 1 naar 2, twee van 2 naar 3, een van 1 naar 2, een van 2 naar 3 en tenslotte een van 1 naar 2. Het aantal nullen geeft aan hoeveel getallen er op de stack werden geplaatst, het aantal enen hoeveel er van de stack zijn verwijderd. Het gegeven rijtje beschrijft de toestand van Figuur 9.6. Het verschil tussen het aantal nullen en het aantal enen is het aantal schijven op pin 2. Het aantal enen is dus hoogstens gelijk aan het aantal nullen. Dat geldt voor iedere tussentoestand. Een rijtje nullen en enen beschrijft dus alleen een tussenstand als in ieder beginstuk van het rijtje het aantal enen hoogstens gelijk is aan het aantal nullen. Zo’n rijtje zullen we een toegestaan rijtje noemen. Het gegeven rijtje is toegestaan, want de beginstukken zijn
0, 00, 001, 0010, 00101, 001011, 0010110, 00101101, 001011010
en voor deze rijtjes geldt dat het aantal enen hoogstens gelijk is aan het aantal nullen. Het aantal eindstanden is gelijk aan het aantal toegestane rijtjes van lengte . Het probleem van het aantal mogelijke rangschikkingen op pin 3 is daarmee vertaald in de vraag: hoeveel toegestane rijtjes van lengte zijn er?
Voor het aantal toegestane rijtjes van lengte met enen voeren we een notatie in:
9.14 Definitie. Laten en natuurlijke getallen zijn met . Dan definiëren we als het aantal rijtjes in van lengte waarvan precies termen gelijk zijn aan en waarvan ieder beginstuk minstens zoveel termen 0 heeft als termen 1. Het -de Catalangetal is het getal .
De Catalangetallen kunnen op dezelfde manier worden berekend als de binomiaalcoëffciënten, zie Figuur 9.8.
De getallen liggen vast door:
d.w.z. in ieder vakje is het getal gelijk aan de som van de getallen die er in het schema van Figuur 9.8 direct boven liggen. Begin je met een bovenin, dan kan het hele schema met deze regel rij voor rij worden ingevuld. Door een aantal van de getallen op deze manier uit te rekenen kun je de volgende stelling gaan vermoeden:
Bewijs. We schrijven
en laten zien dat deze getallen voldoen aan de regels waarmee de Catalangetallen zijn vastgelegd:
en voor : en . □
In het bijzonder hebben we nu een formule voor het -de Catalangetal:
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Het aantal rangschikkingen op pin bij schijven is dus gelijk aan .
Het aantal van toegestane rijtjes nullen en enen van lengte met enen kun je ook rechtstreeks bepalen door op een slimme manier het aantal niet-toegestane rijtjes te tellen. Dat aantal moet gelijk zijn aan . Hoe is dat in te zien?
Laat een niet-toegestaan rijtje zijn met enen, waarbij . Dan zijn er getallen met zo dat een niet-toegestaan rijtje is (bijvoorbeeld ). Laat nu met het kleinst zijn zo dat het beginstuk van lengte niet-toegestaan is. Voor dit beginstuk geldt dan dat het met een eindigt en dat het aantal enen groter is dan het aantal nullen. Bijvoorbeeld
is een niet-toegestaan rijtje van lengte en het kleinste niet-toegestane beginstuk is
Vervang nu in het kleinste niet-toegestane beginstuk alle nullen door enen en alle enen door nullen. De rest laten we ongewijzigd. In het voorbeeld krijg je dan
Het zo verkregen rijtje is een rijtje van lengte met enen. Van zulke rijtjes zijn er . Elk van deze rijtjes wordt op deze manier verkregen uit een niet-toegestaan rijtje van lengte met enen. Dat is als volgt in te zien. Als je een rijtje van lengte hebt met enen, dan heeft het minder enen dan nullen en is er dus een kleinste beginstuk met minder enen dan nullen. Vervang in dit beginstuk de enen door nullen en de nullen door enen. Dat levert een niet-toegestaan rijtje van lengte met enen. Het is eenvoudig in te zien dat zo niet-toegestane rijtjes van lengte met enen corresponderen met rijtjes van lengte met enen. Daarvan zijn er .
We hebben gezien dat de getallen op eenzelfde manier berekend kunnen worden als binomiaalcoëfficiënten. Voor de Catalangetallen is er een recursieve beschrijving die het mogelijk maakt ze een voor een te berekenen:
Dus:
Deze recursieve beschrijving van kun je als volgt begrijpen. Laat een natuurlijk getal zijn. Bij ieder toegestaan rijtje van nullen en enen is er een kleinste zo dat het beginstuk van lengte uit evenveel enen als nullen bestaat. Dit beginstuk begint met een en eindigt met een . Daartussen staat een toegestaan rijtje van lengte . De rij is dus opgebouwd uit achtereenvolgens
Bij een gegeven zijn er van zulke rijtjes. Het totale aantal is dus