WisFaq!

Re: Aantal manieren om N voorwerpen te verdelen over M posities

Hallo,
die cijfers mogen inderdaad hetzelfde zijn.

Ik probeer namelijk een ideale productmix samen te stellen. Je bent verplicht om in totaal 10 producten te nemen uit een totaal van 4 mogelijke producten, en voor elk van de productmixen krijg je dus een ander resultaat (kost/opbrengst per product verschilt). Ik weet dat je dit met lineaire programmatie kan oplossen en dat de Solver in Excel dit min of meer tot een goed einde brengt.
Ik zou nu echter de lijst willen geven van ALLE mogelijkheden.
Zoals gezegd is dit niet echt een probleem om te programmeren; maar terwijl ik bezig was vroeg ik mij dus af of je op voorhand kon berekenen hoeveel mogelijke combinaties er zullen zijn. Aangezien dit aantal nogal snel oploopt wil ik eerst wel eens weten hoeveel combinaties er zijn voordat ik het programma volledig laat lopen.
(Ik gaf het voorbeeld met 10 producten te kiezen uit 4 mogelijke producten, maar in realiteit zullen het 100 producten te kiezen zijn uit 12 verschillende, en ik vrees dat het gewoon onbegonnen werk zal zijn om ALLE mogelijkheden te overlopen, vandaar dat ik het eerst zou willen berekenen).

Hopelijk is dit voldoende informatie ?

Alvast bedankt voor het ongelooflijk snelle antwoord op mijn vorige vraag.

Deze website is een fantastische ontdekking !!

Groeten,
David

David Declercq
7-3-2003

Antwoord

Aha, nou is het mij duidelijk. Je moet dus een totaal van 10 objecten kiezen. Die 10 objecten kun je uit 4 soorten kiezen. Bijvoorbeeld (met dit voorjaar) een doos van 10 viooltjes waarbij je de keuze hebt, uit A(rode), B(witte), C(blauwe) en D(gele). Hoeveel combinaties kun je nu maken?

Kijk eens naar het plaatje. Het aantal combinaties komt overeen met het aantal wegen van linksonder (0,0) naar rechtsboven (3,10). Elke mogelijke weg geeft hierbij een andere combinatie van die gekleurde viooltjes weer.
Het aantal combinaties komt neer op de vraag hoe je nu het aantal mogelijke wegen telt. Welnu een weg bestaat altijd uit 10 stappen omhoog (V) en 3 stappen naar rechts (H). De getekende weg is daarbij weer te geven met: VVHVVVVHVHVVV.
Het aantal combinaties is nu het aantal mogelijkheden om 10 V'tjes over 13 plaatsen te verdelen = (13 boven 10)

Algemeen: Als je k soorten hebt en je m ($>$k) objecten moet afnemen dan wordt de algemene formule dus ( m+k-1 boven m) mogelijkheden, hetgeen nu makkelijk in te zien valt.


Met vriendelijke groet

JaDeX

jadex
7-3-2003