voortbrengende functies

© h.hofstede (h.hofstede@hogeland.nl)

Voortbrengende functies.

We beginnen met een erg alledaags probleem.
Stel dat je een bedrag van €2 moet betalen met alleen maar muntgeld.
Zoals je weet zijn er de volgende euromunten beschikbaar:

De vraag is: "Op hoeveel verschillende manieren kun je €2,- betalen met alleen maar munten?"
Tja....
Voorlopig stellen we vast dat dat nogal veel mogelijkheden zijn, variërend van 1 munt van €2 tot 200 munten van €0,01.
Laten we de boel wat systematisch aanpakken.
Ik ga van elke muntsoort eerst maar eens een rijtje maken van stapeltjes met 0, 1, 2, 3, ..... munten daarvan.
Dat ziet er dus zó uit:

Als we nou uit elke rij één stapeltje kiezen (het eerste streepje staat voor een stapeltje met NUL munten erin), dan hebben we precies alle mogelijkheden om welke bedragen dan ook maar te betalen. Dus ook alle bedragen van €2, zitten daar bij.

Hoe pikken we die bedragen van €2, - eruit?

Laten we eerst overstappen op een beetje wiskundigere notatie.
Stel dat x precies 1 cent voorstelt.
Dan kunnen we verschillende stapeltjes als machten van x schrijven (waarom dat handig is zien we zo), bijvoorbeeld:

De rijen met stapeltjes hierboven gaan we nu als som schrijven. Dan zien die rijen er zo uit:

1 + x + x² + x³ + x⁴ + x⁵...

1 + x² + x⁴ + x⁶ + x⁸ + x¹⁰ ...

1 + x⁵ + x¹⁰ + x¹⁵ + x²⁰ + x²⁵ + ...

1 + x¹⁰ + x²⁰ + x³⁰ + x⁴⁰ + x⁵⁰ + ...

1 + x²⁰ + x⁴⁰ + x⁶⁰ + x⁸⁰ + x¹⁰⁰ + ...

1 + x⁵⁰ + x¹⁰⁰ + x¹⁵⁰ + x²⁰⁰ + x²⁵⁰ + ...

1 + x¹⁰⁰ + x²⁰⁰ + x³⁰⁰ + x⁴⁰⁰ + x⁵⁰⁰ + ...

1 + x²⁰⁰ + x⁴⁰⁰ + x⁶⁰⁰ + x⁸⁰⁰ + x¹⁰⁰⁰ + ...

En nou komt de grote truc: Als je al die rijen met elkaar vermenigvuldigt, en dan de haakjes wegwerkt, dan neem je óók uit elke rij precies één "stapeltje" dus krijg je ook alle mogelijkheden.
Maar bij dat vermenigvuldigen tel je de machten van x op, en dat zijn precies de eurocenten!!! De machten van x in de uiteindelijke termen geven dus het aantal eurocenten van je eindbedrag.

Kortom, als je de uiteindelijke veelterm zou kunnen vereenvoudigen dan geeft de coëfficiënt van x²⁰⁰ precies het aantal manieren om x²⁰⁰ te maken, dus ook het aantal manieren om 200 eurocent (€2,-) met stapeltjes te maken.

Zo'n veelterm zie je zou krijgen als je alle haakjes wegwerkt en vereenvoudigt, heet een voortbrengende functie.

Hoe vinden we de coëfficiënt van x²⁰⁰?

Om dat te doen gaan we gebruik maken van de basis-meetkundige rij:

(waarom dat zo is kun je in deze les over de som van een meetkundige rij vinden).
Die rij hierboven is natuurlijk de rij voor de 1 eurocenten hierboven.....
En op dezelfde manier kun je de volgende rijen maken voor de rijen 2-eurocenten, 5-eurocenten, enz.

enz.

Dat betekent dat je, als je al die rijen hierboven met elkaar vermenigvuldigt, de volgende voortbrengende functie vindt:

Blijft nog steeds de vraag: Hoe maken we hier "gewone machten" van x van?

Laten we f(x) langzaamaan gaan opbouwen: Recursie!!.

Bekijk de volgende serie functies:

enz.

Laten we kijken naar het verband tussen de eerste en de tweede van deze vergelijkingen:

(waarbij je moet onthouden dan de B_i waarvoor i < 0 gelijk zijn aan nul)
Nou, als die twee functies gelijk zijn, dan zijn de coëfficiënten van dezelfde machten van x ook aan elkaar gelijk.
Dat betekent: A_n = B_n - B_{n
- 2}

A_n = B_n - B_{n - 2}

Dat kun je nog anders schrijven als B_n = A_n + B_{n - 2}
En op precies dezelfde manier kun je zulke recursievergelijkingen gaan maken voor C_n, D_n, en de rest.
Dat geeft het volgende rijtje recursievergelijkingen:

B_n = A_n + B_{n
- 2}
C_n = B_n + C_{n
- 5}
D_n = C_n + D_{n
- 10}
E_n = D_n + E_{n
- 20}
F_n = E_n + F_{n
- 50}
G_n = F_n + G_{n
- 100}
H_n = G_n + H_{n
- 200}

Verder weten we nog dat alle A_n gelijk zijn aan 1, en dat alle coëfficiënten met een negatieve index gelijk zijn aan nul.

Oké dan. Hoe gaan die berekenen?

Nou als ik zulke recursierelaties zie, dan schreeuwt dat volgens mij maar om één woord:

Hier is een excelblad met daarin de waarden van alle coëfficiënten.

Je ziet er in dat H₂₀₀ = 73682

Ofwel: er zijn 73682 manieren om €2,- in munten uit te betalen.

OPGAVEN

Ik wil een willekeurig aantal dobbelstenen op tafel gooien, maar er moeten in totaal 20 ogen zijn.
Op hoeveel manieren kan ik dat doen?

282

Hoeveel verschillende optelsommen met de cijfers 1 tm 9 kun je maken waar precies 10 uit komt?

Als de volgorde WEL van belang is. (dus 2 + 2 + 6 is iets anders dan 2 + 6 + 2)

512

Als de volgorde NIET van belang is. (dus 2 = 2 + 6 is hetzelfde als 2 + 6 + 2)