In paragraaf 1.2 bestudeerden we hoeveel bergtoppen er gevormd kunnen worden met opwaartse en
neerwaartse schuine strepen. Dit is ook een telprobleem waarbij de Catalan-getallen verschijnen. De vraag is hoe we bij dit telprobleem een formule kunnen opstellen die anders is dan de recurrente betrekking gevonden in hoofdstuk 2.
In paragraaf 1.2 werd er gekeken hoevel bergtoppen er gevormd konden worden met opwaartse en
neerwaartse schuine strepen. Als we het feit negeren dat de strepen geen bergtoppen hoeven te vormen, dan kunnen we kiezen uit
opwaartse en
neerwaartse schuine strepen ofwel we kunnen kiezen uit
strepen. Als we het vormen van bergtoppen negeren, dan kunnen we het aantal mogelijke manieren waarop we
opwaartse en
neerwaartse kunnen rangschikken bepalen met
.
Maar daar moeten we dan de niet-bergtoppen van afhalen willen we het aantal mogelijke bergtoppen die gevormd kunnen worden met opwaartse en
neerwaartse schuine strepen bepalen.
Stel elke opwaartse streep geven we aan met , en elke neerwaartse streep met
. Dan stelt elke niet-bergtop een mogelijkheid voor, waarbij er meer opwaartse strepen (meer
-en) zijn dan neerwaartse (
-en), of visa versa. Elke niet-bergtop heeft meer neerwaartse strepen dan opwaartse strepen op een bepaald punt, dus vanaf dat punt, moet een strook omgewisseld worden (
met een
) of andersom. Een niet-bergtop bestaat dus bijvoorbeeld uit
neerwaartse strepen en
opwaartse strepen. Omgekeerd geldt natuurlijk hetzelfde (elke pad met meer opwaartse strepen dan neerwaartse strepen).
De vraag is hoeveel van dit soort niet-bergtoppen er kunnen worden gevormd? Dat is hetzelfde aantal als er gekozen kan worden uit opwaartse strepen uit de
strepen ofwel:
Dus
Activiteit 5.
Bereken t/m
met behulp van bovenstaande gevonden formule.
Verwerkingsopdracht 3.
Verklaar waarom geldt dat:
Verwerkingsopdracht 4.
Bewijs dat: