Lunamaan schreef:
Maar wat als herhaling niet is toegestaan?
Want officieel is het niet toegestaan want we leggen de dozen niet terug nadat ze zijn ingeladen (even terugdenkend aan het vaasmodel), maar in deze formule gaan we daar wel vanuit. Wat niet uitmaakt aangezien er meer dan 25 dozen zijn voor de drie verschillende soorten dozen.
Herhaling zegt dat we de elementen waaruit we kiezen (hier
w,
f of
b) meerdere malen mogen kiezen. Dat kan verschillende manieren:
[1] In ons geval zijn er van elk van deze elementen voldoende exemplaren om het busje te vullen (50, 50 resp 30 stuks terwijl er in totaal maar 25 in het busje passen). Alle dozen w worden als identiek beschouwd, evenals alle dozen f en evenals alle dozen b.
In die zin mogen we onbeperkt w's, f's of b's herhaald kiezen.
De uitkomst is een rijtje van 25 dozen, waarvan de volgorde niet uitmaakt, bv:
w,w,w,w,w,w,w,w,f,f,f,f,f,f,f,f,f,f,f,f,b,b,b,b,b
en deze rijtjes willen we tellen.
[2] Stel je hebt 3 knikkers met de kleuren wit, fuchsia en blauw.
Als je nu 25 trekkingen doet met terugleggen, dan kan je bijvoorbeeld dit rijtje krijgen:
w,b,f,f,w,f,b,f,f,b,w,w,f,f,b,w,f,f,b,w,f,f,w,f,w
Als de volgorde van dit rijtje
wel van belang is, dan heb je voor elke trekking 3 mogelijkheden en kan je zo
\(3^{25} = 847288609443\) verschillende rijtjes trekken.
Als de volgorde van dit rijtje
niet van belang is (d.w.z. als je bijvoorbeeld turft hoeveel witte, fuchsia en blauwe je getrokken hebt), dan vind je w=8 stuks, f=12 stuks, b=5 stuks.
En dan ontstaat weer precies de uitkomst als bij [1]:
w,w,w,w,w,w,w,w,f,f,f,f,f,f,f,f,f,f,f,f,b,b,b,b,b
en van dit soort uitkomsten zijn er zoals we hierboven zagen 351 verschillende.
In geval [1] kiezen we dus met herhaling omdat er onbeperkt veel van dezelfde elementen zijn (waarbij de keuze in het busje belandt), in geval [2] kiezen we met herhaling omdat we terugleggen (nadat we elke individuele uitkomst genoteerd of geturft hebben).
Gezien vanuit het vazenmodel kan je [1] ook zien als onbeperkte voorraad witte, fuchsia en blauwe knikkers, waarvan je er in totaal 25 in 1 vaas stopt, en daarvan het aantal mogelijke einduitkomsten telt.
Lunamaan schreef:
Maar wat als de vraag zo geformuleerd was:
Er moeten 50 dozen met flesjes water, 50 dozen fruit, en 30 dozen broodjes worden vervoerd. Je hebt een vrachtwagen waarin 45 dozen passen. Hoeveel verschillende ladingen kun je in de eerste ritje meenemen als je een volle lading meeneemt?
Nu kunnen we niet van herhaling uitgaan.
Omdat er nu slechts 30 dozen broodjes zijn en er 45 dozen in het busje passen, vallen de mogelijkheden van 31 t/m 45 dozen broodjes in de vrachtwagen af.
Dit is nu niet meer op te lossen met de combinatorische basisstructuren, maar bijvoorbeeld wel met formele machtreeksen en genererende functies, maar dat gaat mogelijk te ver.
Als ik het daarmee oplos, kom ik uit op de coefficient van
\(x^{35}\) in
\(GF(x) = \frac{1-x^{31}}{(1-x)^3}\) , en die is
\({47 \choose 2} - {16 \choose 2} = 961\)
Het werkt nog wel eenvoudig via de sommatie zoals in mijn vorige post:
\(count = \displaystyle \sum_{b=0}^{30} \sum_{w=0}^{45-b} 1 = \sum_{b=0}^{30} (46-b) = 31\cdot 46 - \frac{30\cdot 31}{2} = 961\)
PS: hier nog even in het kort de basismogelijkheden voor n=3 knikkers w, f en b, waarvan we er k=2 kiezen:
- met herhaling, volgorde wel van belang:
ww, wf, wb, fw, ff, fb, bw, bf, bb
\(count = n^k = 3^2 = 9\)
- met herhaling, volgorde niet van belang:
ww, wf (=fw), wb (=bw), ff, fb (=bf), bb
\(count = { n-1+k \choose k } = {4 \choose 2} = 6\)
- zonder herhaling, volgorde wel van belang:
wf, wb, fw, fb, bw, bf (ww, ff en bb zijn nu verboden)
\(count = (n)_k = \frac{n!}{(n-k)!} = \frac{3!}{1!} = 6\)
(ofwel: voor de eerste keuze uit 3, voor de tweede keuze uit 3-1=2, en dat geeft 3*(3-1) = 6 mogelijkheden)
- zonder herhaling, volgorde niet van belang:
wf (=fw), wb (=bw), fb (=bf); (ww, ff en bb zijn nu verboden)
\(count = {n \choose k} = {3 \choose 2} = 3\)