herhalingscombinaties


Eieren Verven.	© h.hofstede (h.hofstede@hogeland.nl)

Het basisprobleem is het volgende:

Je hebt n dingen en daar moet je er k uit kiezen

Tot nu toe waren er bij al die telproblemen steeds twee dingen waar je op moest letten:

1. Is het met of zonder terugleggen?
2. Is de volgorde van belang?

Omdat elk van deze twee vragen met JA en NEE beantwoord kan worden, zijn er dus in totaal VIER mogelijkheden. Kijk maar, de volgende tabel (roosterdiagram als je dat liever hoort) vat ze samen:

	ZONDER terugleggen	MET terugleggen
volgorde NIET van belang	?¹	?
volgorde WEL van belang	?²	?³

Van die vier vraagtekens hebben we er in de middelbare schoolstof al drie opgelost:

Vraagteken 1: volgorde niet van belang, zonder terugleggen.

Dat was de meest voorkomende : Kies n elementen uit een verzameling van k, waarbij de volgorde niet van belang is. Dat kon op (n nCr k) manieren: het aantal combinaties.

voorbeeld: kies een commissie van 3 uit een groep van 10.
dat kan op 10 nCr 3 = 120 manieren

Vraagteken 2: volgorde wel van belang, zonder terugleggen.

Eigenlijk nóg elementairder dan de vorige: die vonden we direct uit een boomdiagram,
en dat gaf n • (n -1) • (n - 2) • ...
Dat was het aantal permutaties: (n nPr k)

voorbeeld: Loot willekeurig een winnaar, een tweede plaats en een derde plaats uit een groep van 10 mensen
dat kan op 10 • 9 • 8 = 720 manieren (ofwel 10 nPr 3).

Vraagteken 3: volgorde wel van belang, met terugleggen.

Ook deze kun je makkelijk met een boomdiagram vinden: n • n • n • ......
Het aantal mogelijkheden is dus (n^k)

voorbeeld: noem een getal van 3 cijfers (0 mag ook)
dat kan op 10 • 10 • 10 = 1000 manieren

Voorlopig ziet ons telsysteem er dan zó uit:

	ZONDER terugleggen	MET terugleggen
volgorde NIET van belang	n nCr k	?????
volgorde WEL van belang	n nPr k	*n^k*

De enige overgebleven telmethode werd op jouw middelbare school waarschijnlijk angstvallig verzwegen......
Misschien is het nu eens tijd om ook daar aandacht aan te gaan besteden.......

Dan kom je terecht bij de zogenaamde Herhalingscombinaties.

Herhalingscombinaties.

Nog even voor alle duidelijk het soort probleem waarom het hier gaat:

• Je hebt k dezelfde "dingen"
• Die moet je verdelen over n kamers
• In elke kamer mogen best meerdere/geen dingen komen

Op hoeveel manieren kan dat?

Omdat die k dingen hetzelfde zijn doet de volgorde er niet toe. Elke kamer mag best vaker worden gekozen om een "ding" in achter te laten, dus het is zonder terugleggen.

Laten we als voorbeeld het allereenvoudigste geval van 5 dezelfde knikkers die je willekeurig over 8 schaaltjes moet verdelen....

De oplossing.....

Er is een erg mooie elegante oplossing, die gebruikt maakt van een techniek die we al kennen! Kijk naar het rooster hieronder:

Let goed op:

•
•

op de horizontale as staan de dingen die gekozen kunnen worden, en daar staan de getallen bij de roosterlijnen.
op de verticale as staan de dingen die gekozen moeten worden en daar staan de getallen bij de hokjes.

Ik beweer nu doodleuk het volgende: Elke route in dit rooster van S naar F komt overeen met een verdeling van de knikkers over de schaaltjes!!!! Kijk maar; hier zie je er een paar:

Maar als elke route hoort bij een knikkerverdeling, dan zijn er evenveel verdelingen als routes, en dat aantal routes dat kennen we al. We hebben een rooster van 7 bij 5 dus er zijn (12 nCr 5) = 792 verschillende routes/verdelingen.

Het algemene geval: Er staan n kamers horizontaal en k dingen verticaal, dan heb je een rooster van (n - 1) bij k hokjes. In zo'n rooster zijn er (n - 1 + k) nCr (k) routes.

Zo. Dan is de tabel nu eindelijk af:

	ZONDER terugleggen	MET terugleggen
volgorde NIET van belang	n nCr k
volgorde WEL van belang	n nPr k	n^k

Het eierverf-probleem.
- een andere aanpak-

Je hebt n eieren en moet die voor Pasen gaan verven.
Je hebt k kleuren verf.
Op hoeveel verschillende manieren kun je dat uitvoeren?

•

Het is zonder terugleggen want je kunt elke kleur verf vaker gebruiken (we gaan ervan uit dat er van elke kleur genoeg verf is).

•

De volgorde is niet van belang, want na afloop liggen al die eieren samen in een schaal en weet je echt niet meer welke je eerder en welke je later hebt geverfd.

Neem bijvoorbeeld 6 eieren en 3 kleuren verf, en onze eerste oplossing zou er uit zien zoals hiernaast.
We weten het aantal manieren al: 8 nCr 2 = 28.

Een alternatieve oplossing......

Laten we het getallenvoorbeeld van hierboven volgen, met 3 kleuren verf (k) en 6 eieren (n).
Stel dat we rode, blauwe en groene verf hebben.

Dan kiezen we nu de volgorde rood - blauw - groen.

We leggen vervolgens de zes eieren op een rij naast elkaar:

En dan zetten we er twee schotten tussen waardoor de eieren in drie groepjes worden verdeeld: van links naar rechts verven we die groepjes rood - blauw - groen.
Bijvoorbeeld:

Als je de twee zwarte schotten op deze manier plaatst krijg je 2 rode eieren, 3 blauwe eieren en 1 groen ei.

Maar het kan ook zó

Dit staat voor 2 rode, 0 blauwe en 4 groene eieren.
Zo kun je door elke manier van plaatsen van de twee schotten een verschillende eierverf-manier krijgen.
Kortom, we hebben onze vraag teruggebracht tot de volgende:

Op hoeveel manieren kun je 2 schotten bij 6 eieren plaatsen?

Nou, als je nou een schot als een 1 noteert en een ei als een 0 dan heb je dus te maken met een serie van 6 nullen en 2 enen.
De eerste indeling hierboven (2 rode, 3 blauwe, 1 groene) zou er dan uitzien als 00100010
De tweede indeling hierboven (2 rode , 4 groene) zou er uitzien als 00110000

Het wordt altijd een rij van 8 cijfers met 2 enen en 6 nullen !!

Dat kan op 8 nCr 2 = 28 manieren. Gelukkig..... Hetzelfde antwoord als bij de routes in een rooster

Schotten plaatsen

Dat "schotten plaatsen" lijkt een omslachtiger manier dan die routes in een rooster, en dat is hier misschien ook wel zo. Maar er zijn meer problemen die je kunt oplossen door op een handige manier schotten te plaatsen.
Hier zijn een paar voorbeelden van het plaatsen van schotten:

Voorbeeld 1. Uit hoeveel optelsommen met positieve gehele getallen komt het antwoord 20?
(2 + 13 + 5 is iets uiteraard anders dan 5 + 2 + 13)

Leg 20 enen naast elkaar. Dan moet je bij elke tussenruimte beslissen of een een "PLUS" komt te staan of niet.
19 keer WEL of NIET beslissen geeft 2¹⁹ mogelijkheden. Dan zijn er 524288 (we tellen het getal 20 ook mee als som, anders zijn het er 524287)., Hier staat bijvoorbeeld 5 + 2 + 9 + 4 = 20:

Voorbeeld 2. Een tuinder gaat 3 eiken, 4 wilgen en 5 berken op een lange rij planten.
De bomen zijn allemaal verschillend. Hij wil ze graag zo plaatsen dat er geen twee berken naast elkaar staan.
Op hoeveel manieren kan hij dat doen?

Plant eerst de 7 eiken en wilgen. Dat kan op 7! = 5040 manieren.
Nu heeft hij 8 tussenruimtes waarvan hij er 5 uit moet kiezen om een berk te planten. Dat kan op 8 nCr 5 = 56 manieren.
Tenslotte moet hij bij die 5 tussenruimtes nog beslissen wélke berk hij er gaat plaatsen.
Dat kan op 5! = 120 manieren.
In totaal 5040 • 56 • 120 • 33868800 manieren.

Voorbeeld 3. Een dierentuininkoper gaat op zoek naar Antilopes, Beren, Chimpansees en Dromedarissen om te kopen.
In totaal gaat hij 30 beesten kopen, minstens één van elke soort. Hoeveel verschillende aankopen zijn er mogelijk?

Zet de beesten op volgorde A, B, C, D naast elkaar. Dat geeft een rij van 30 letters. Kies uit de 29 tussenruimtes er 3 om een schot neer te zetten, dan heb je elke mogelijke dierenverdeling gemaakt.
3 kiezen uit de 29 kan op 29 nCr 3 = 3654 manieren.

OPGAVEN

Bij een verkiezing zijn er 6 kandidaten en 120 stemmen. Hoeveel mogelijke uitslagen zijn er?

234531275

Gooi 10 dobbelstenen.
Hoeveel mogelijke uitslagen zijn er voor welke ogen gegooid worden?

3003

Ik vraag jou om een optelsom van drie positieve gehele getallen te noemen waar 12 uitkomt.
Hoeveel verschillende opties heb je? (een verschillende volgorde is uiteraard een verschillende som).

Ik heb een enquête gehouden onder 12 mensen en daarbij moesten ze allemaal één multiple-choice-vraag beantwoorden, die 5 mogelijke antwoorden had (a, b, c, d, e)
Hoeveel mogelijke enquête-resultaten zijn er?

1820

Ik wil graag 12 repen chocola verdelen over vier personen, waarbij iedereen minstens één reep moet krijgen.
Op hoeveel manieren kan dat?

165

Een ijssalon heeft 12 verschillende smaken ijs.
Voor €3,- mag je 4 bolletjes willekeurig uitzoeken.
Op hoeveel manieren kan dat?

1365

Kleine Tim gaat in de snoepwinkel 12 snoepjes kopen. Hij wil van elk soort snoep minstens één snoepje.
De snoepwinkel heeft 4 verschillende soorten snoepjes in voorraad.
Op hoeveel verschillende manieren kan Tim snoepjes gaan kopen?

165