Combinaties met herhaling
Combinaties met herhaling lijken op de gewone combinaties, alleen laten we nu toe dat elementen uit de onderliggende verzameling M herhaald worden.
Definitie en formule
We beginnen met een leuk voorbeeld: je loopt een winkel binnen en wilt voor een kampeerweekend twaalf flesjes bier kopen. In het schap staan vier verschillende merken. Je hebt nu verschillende mogelijkheden om de flesjes te kopen: je kunt bijvoorbeeld 5 Heineken, 2 Grolsch, 1 Amstel en 4 Brand kopen, of je kunt van elk merk precies drie flesjes kopen. Hoeveel verschillende mogelijkheden zijn er om de flesjes te kopen als je er precies twaalf wilt hebben?
We hebben dus de basisverzameling M = {Heineken, Grolsch, Amstel, Brand} en we vragen ons af hoeveel k-tallen met k = 12 er zijn die elementen uit de verzameling M bevatten en waarbij de volgorde er niet toe doet.
De afleiding van de formule is al een stuk ingewikkelder dan bij de andere combinatorische opgaven. Eerst stellen we ons onze boodschappen voor als een rij nullen en enen, zodanig dat het aantal enen overeenkomt met het aantal gekochte flesjes van een bepaald merk en een nul de merken van elkaar scheidt. De rij 111011101111101 zegt ons dus dat we drie Heineken hebben gekocht (de eerste drie enen), dan drie Grolsch (0 is het scheidingsteken, de volgende drie enen), dan vijf Amstel (0 scheidingsteken en dan vijf enen) en ten slotte één Brand. Het hele principe zie je in de volgende afbeelding:
Als we 6 Heineken, 4 Grolsch, 2 Brand en geen Amstel wilden kopen, zou de rij er zo uitzien:
We zien dat de lengte van deze rij altijd 15 is: er moeten 12 enen in staan, om in totaal 12 biertjes te kopen. En er moeten drie scheidingstekens in staan, om vier verschillende merken van elkaar te kunnen scheiden. We moeten nu nog berekenen hoeveel van zulke rijen van lengte 15 er zijn die precies drie nullen bevatten.
Het is genoeg om de plaatsen van de nullen te berekenen: zodra we 3 nullen tussen de 12 enen hebben verdeeld, hebben we een geldige combinatie bieren. Anders gezegd: we hebben 15 hokjes en we moeten er 3 van met een nul vullen. De overige hokjes vullen we automatisch met enen.
Dit is al een eenvoudige opgave over combinaties zonder herhaling. We nummeren de 15 hokjes met de getallen {1, …, 15} en kiezen nu uit deze verzameling steeds drietallen getallen, zodat we drie indices krijgen waar we een nul neerzetten. Voor de combinatie {2, 4, 7} krijgen we bijvoorbeeld de rij: 101011011111111. Op de 2e, 4e en 7e plaats staat een nul, de rest zijn enen. Er zijn dus in totaal
verschillende manieren om de nullen over de 15 hokjes te verdelen en dus ook 455 verschillende mogelijkheden om 12 biertjes te kopen als we vier verschillende soorten bier hebben.
Deze redenering kunnen we generaliseren. Als we een verzameling M met n elementen hebben en daaruit k-tallen kiezen waarbij elementen herhaald mogen worden, dan stellen we een rij nullen en enen samen van lengte n + k − 1 (k enen en n − 1 nullen) en bepalen we op hoeveel manieren we n − 1 nullen kunnen verdelen. Het aantal combinaties met herhaling is dus gelijk aan
De laatste omvorming mochten we doen dankzij de basisrelaties tussen binomiaalcoëfficiënten.
Uitgewerkte voorbeelden
- Op hoeveel manieren kunnen we 20 vrijkaartjes voor de première van een toneelvoorstelling verdelen over 10 gepensioneerde dames? Dit is een voorbeeld van combinaties met herhaling, want één gepensioneerde dame kan meer, potentieel alle, vrijkaartjes krijgen. We moeten alleen goed beseffen wat n en wat k is. Eigenlijk kiezen we combinaties met herhaling van 20 uit 10 dames, met andere woorden: we maken een rij nullen en enen met lengte 29 die 20 enen en 9 nullen bevat. Dus n = 10, k = 20. We krijgen het resultaat:
Hoofdstukken: Combinatoriek, Variaties, Permutaties, Combinaties, Variaties met herhaling, Combinaties met herhaling, Hoeveel verschillende pincodes zijn er?
