Een vraag waar ik niet uitkom

[Lunamaan]

Hoi allemaal,

Er is een vraag waar ik niet uitkom en ik hoop dat jullie kunnen helpen:

Vraag:
Er moeten 50 dozen met flesjes water, 50 dozen fruit, en 30 dozen broodjes worden vervoerd. In de bestelbus passen 25 dozen. Hoeveel verschillende ladingen kun je in de eerste rijtje meenemen als je een volle lading meeneemt?

Volgorde is als het goed is niet belangrijk.

Ik dacht zelf aan 130 ncr 25, maar dan corrigeer ik niet voor het feit dat het niet allemaal verschillende elementen zijn.

Weet een van jullie het antwoord?

[siep]

We hebben de keuze uit n=3 elementen:
w = doos water
f = doos fruit
b = doos broodjes

Nu moeten we daar k=25 uit kiezen, waarbij
- herhalingen zijn toegestaan (moet wel bij keuze uit slechts 3 soorten dozen)
- de volgorde niet belangrijk is (als we ze alle 25 maar meenemen in de bestelbus).

Met wat voor soort combinaties kan je het aantal mogelijkheden hiervoor berekenen?

[Lunamaan]

Bedankt voor de verheldering! Ik begrijp dat dit de vraag is, maar ik weet dus niet hoe ik het moet berekenen. Kun je mij helpen?

[siep]

Zijn in je leerstof de herhalingscombinaties behandeld ?
Meer precies: k-herhalingscombinaties uit n elementen ?

[siep]

In het kort:
Bij k-herhalingscombinaties kan je de volgende notatie gebruiken:
kruisje x voor een keuze
streepje | als scheidingsteken

Met keuze uit 3 elementen (w, f en b) hebben we 2 scheidingstekens nodig:
- vóór het eerste scheidingsteken zetten we het aantal dozen water w
- tussen de scheidingstekens het aantal dozen fruit f
- na het tweede scheidingsteken het aantal dozen brood b

Voorbeeld:

De keuze van 12 dozen water, 8 dozen fruit en 5 dozen brood kunnen we noteren als:

Code: Selecteer alles

      w      |    f     |  b
--------------------------------------------
xxxxxxxxxxxx | xxxxxxxx | xxxxx

Omgekeerd is elk rijtje met 25 kruisjes en 2 scheidingstekens terug te herleiden naar een keuze.
Zo betekent het rijtje

Code: Selecteer alles

xx | xxxxx | xxxxxxxxxxxxxxxxxx

de keuze van 2 dozen water, 5 dozen fruit en 18 dozen brood


Elk zo'n rijtje staat dus voor precies 1 mogelijke lading dozen voor het bestelbusje.
Hoeveel rijtjes van 25+2 = 27 zijn er met de 2 scheidingstekens op verschillende plaatsen (= keuze van 2 uit 27)?

[Lunamaan]

Bedankt dat je de moeite neemt om het mij zelf te laten uitzoeken.

Alleen ik hoopte stiekem op een antwoord met berekening. Het is een vraag die ik moet beantwoorden voor mijn minor programmeren voor verheldering van een programmeerprobleem, ik ben bekend met combinatoriek via de middelbare school.

Ik kom er vast en zeker uit als ik zelf even uitzoek hoe het ook alweer zit met herhalingscombinaties, maar dat moet ik morgen weer even met een frisse blik doen omdat ik er al een hele studiedag op het zitten. Als ik het antwoord of de formule zie denk ik echter dat ik het direct begrijp.

Dus als je dat zou willen doen zou ik erg blij zijn omdat het me wat tijd zou schelen. Anders kijk ik er morgen weer naar.

In ieder geval bedankt voor de uitleg die je tot nu toe gegeven hebt!

[siep]

Als je uit n verschillende elementen er k moet kiezen waarbij herhaling is toegestaan en de volgorde niet van belang is,
dan is het aantal mogelijke herhalingscombinaties
{n-1+k \choose k} = {n-1+k \choose n-1}

k = aantal te kiezen elementen = aantal kruisjes in mijn vorige post
n = het aantal elementen waaruit we kunnen kiezen.
n-1 = het aantal scheidingsstreepjes wat we nodig hebben in de kruisje-streepje notatie.

In jouw geval:
k = 25
n = 3
aantal mogelijke manieren om het busje te laden = { 3-1+25 \choose 3-1 } = {27 \choose 2 } = 351


ALTERNATIEF:
Via analyse van het het algoritme:
Definieer de capaciteit van het busje = C = 25,
w = aantal dozen water,
f = aantal dozen fruit
Zet eerst w = 0 .. C dozen water in het busje, dan f = 0 .. (C-w) dozen fruit, en vul de rest op met dozen brood.
Het volgende algoritme toont en telt dan alle mogelijkheden:

Code: Selecteer alles

C = 25
count = 0
for(w=0 to C)
    for(f=0 to C-w){
        toon deze oplossing = ( w, f, b=C-w-f )
        count = count + 1
        }
print(count)

Dit algoritme vertaalt zich direct in de volgende sommatie:

count = \displaystyle \sum_{w=0}^{C} \sum_{f=0}^{C-w} 1 = \sum_{w=0}^{C} (1+C-w) = \sum_{w=0}^{C} (C+1) - \sum_{w=0}^{C} w

= (C+1)^2 - \frac{C(C+1)}{2} = 26^2 - \frac{25\cdot 26}{2}= 351

[Lunamaan]

Ontzettend bedankt voor je uitgebreide reactie!!

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.

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.

[siep]

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.

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