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, varirend 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 + x2 + x3 + x4 + x5...
  1 + x2 + x4 + x6 + x8 + x10 ...
  1 + x5 + x10 + x15 + x20 + x25 + ...
  1 + x10 + x20 + x30 + x40 + x50 + ...
  1 + x20 + x40 + x60 + x80 + x100 + ...
  1 + x50 + x100 + x150 + x200 + x250 + ...
  1 + x100 + x200 + x300 + x400 + x500 + ...
  1 + x200 + x400 + x600 + x800 + x1000  + ...
       
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 cofficint van x200  precies het aantal manieren om x200 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 cofficint van x200 ?
       
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 Bi  waarvoor i < 0  gelijk zijn aan nul)
Nou, als die twee functies gelijk zijn, dan zijn de cofficinten van dezelfde machten van x ook aan elkaar gelijk.
Dat betekent:  An = Bn - Bn - 2

An = Bn - Bn - 2

       
Dat kun je nog anders schrijven als   Bn = An + Bn - 2 
En op precies dezelfde manier kun je zulke recursievergelijkingen gaan maken voor  Cn, Dn, en de rest.
Dat geeft het volgende rijtje recursievergelijkingen:
       
Bn = An + Bn - 2
Cn = Bn + Cn - 5
Dn = Cn + Dn - 10
En = Dn + En - 20
Fn = En + Fn - 50
Gn = Fn + Gn - 100
Hn = Gn + Hn - 200
       
Verder weten we nog dat alle An gelijk zijn aan 1, en dat alle cofficinten 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 cofficinten.

Je ziet er in dat  H200 = 73682

Ofwel:  er zijn 73682 manieren om 2,- in munten uit te betalen.
       
       
  OPGAVEN
       
1. 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

       
2. Hoeveel verschillende optelsommen met de cijfers 1 tm 9 kun je maken waar precies 10 uit komt?
       
  a. Als de volgorde WEL van belang is.  (dus  2 + 2 + 6  is iets anders dan  2 + 6 + 2)
     

512

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

41

       
     
       

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