Een vraag waar ik niet uitkom

Continue & discrete verdelingen, toevalsveranderlijken, betrouwbaarheidsintervallen, correlaties.
Plaats reactie
Lunamaan
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 11 jan 2022, 15:20

Een vraag waar ik niet uitkom

Bericht door Lunamaan » 11 jan 2022, 15:25

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?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Een vraag waar ik niet uitkom

Bericht door arie » 11 jan 2022, 16:53

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
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 11 jan 2022, 15:20

Re: Een vraag waar ik niet uitkom

Bericht door Lunamaan » 11 jan 2022, 16:59

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?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Een vraag waar ik niet uitkom

Bericht door arie » 11 jan 2022, 17:01

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

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Een vraag waar ik niet uitkom

Bericht door arie » 11 jan 2022, 17:27

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
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 11 jan 2022, 15:20

Re: Een vraag waar ik niet uitkom

Bericht door Lunamaan » 11 jan 2022, 18:09

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!

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Een vraag waar ik niet uitkom

Bericht door arie » 11 jan 2022, 20:18

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
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 11 jan 2022, 15:20

Re: Een vraag waar ik niet uitkom

Bericht door Lunamaan » 12 jan 2022, 08:36

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.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Een vraag waar ik niet uitkom

Bericht door arie » 12 jan 2022, 13:04

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\)

Plaats reactie