15.1  Combinatoriek >

In hoofdstuk 3 in Vwo4 Combinatoriek heb je geleerd mogelijkheden te tellen. Hieronder volgen enkele 'telmethoden'. Bij veel telproblemen moet je verschillende telmethoden combineren om tot een oplossing te komen.

Geordende greep zonder herhaling

Aan een wedstrijd doen vier deelnemers mee (zeg: A, B, C en D). De deelnemers kunnen in verschillende volgorden de finish passeren. Eén mogelijke einduitslag is BCAD. Zo’n rijtje-van-vier waarbij de volgorde van belang is, noem je een permutatie (ook wel geordende greep zonder herhaling genoemd). Het aantal mogelijke einduitslagen (permutaties) kun je op verschillende manieren vinden.

  • Door de mogelijkheden systematisch uit te schrijven.

  • Door een boomdiagram te tekenen.


Vier deelnemers (maar ook: letters, cijfers, kleuren, ...) kun je op 4 3 2 1 = 24  manieren in volgorde zetten.
Voor het product 4 3 2 1 bestaat een afkorting: 4 ! .
Dit spreek je uit als 4  faculteit.
Er geldt: 4 ! = 4 3 2 1 = 24 .

4 ! kun je ook met de optie x ! op je rekenmachine berekenen.


We bekijken ook nog een wedstrijd waar 7 deelnemers aan meedoen (zeg: A, B, C, D, E, F en G). Het aantal mogelijke erepodia (zoals BCA, ACB, FAD en FGE) is:
7 6 5 = 7 ! 4 ! = 210 .
Anders gezegd: Het aantal permutaties van 3 uit 7 (of geordende grepen van 3 uit 7 zonder herhaling) is 7 6 5 .
Het aantal permutaties van 3 uit 7 kun je berekenen met de optie n P r op je rekenmachine.


Geordende greep met herhaling

Een meerkeuzetoets bestaat uit 5  vragen. Bij iedere vraag staan drie antwoorden, waarvan er één moet worden aangekruist. Er is altijd maar één antwoord goed. We vragen ons af op hoeveel manieren je de toets kunt maken.

Dit telprobleem kun je oplossen door een wegendiagram te tekenen.

Het aantal mogelijkheden (of geordende grepen met herhaling) is 3 5 = 243 .


Ongeordende greep zonder herhaling

We bekijken drie telproblemen:

  • alle rijtjes van lengte 7 met 3  enen en 4  nullen;

  • alle kortste routes van ( 0,0 ) naar ( 4,3 ) ;

  • alle selecties (of combinaties) van 3  dingen uit 7 verschillende dingen. (Bij een combinatie letten we niet op de volgorde.)

Hiernaast zie je van elk van de drie telproblemen een mogelijke uitkomst.

Er zijn evenveel rijtjes als routes als selecties. Immers, je kunt bij alle drie de telproblemen een rijtje maken, bijvoorbeeld:

  • 0100011

  • RBRRRBB

  • - B - - - F G

Deze rijtjes komen op hetzelfde neer.
Het aantal routes van ( 0,0 ) naar ( 4,3 ) noteren we met het combinatiegetal ( 7 3 ) .
Dus ( 7 3 ) = ...

  • ... het aantal 0 - 1 -rijtjes van lengte 7 met 3  enen,

  • ... het aantal routes van lengte 7 met 3  stappen naar boven,

  • ... het aantal combinaties van 3   elementen uit 7 .

Onderstaande 'telmethode' is interessant, maar behoort niet tot de examenstof. Die kan je dus eventueel overslaan.

Ongeordende greep met herhaling

Joe, Jack, William en Averell hebben tijdens een overval zeven goudstaven buit gemaakt. We vragen ons af - net als Lucky Luke - op hoeveel manieren de Daltons de goudstaven onderling kunnen verdelen.
Bij dit telprobleem is alleen het aantal goudstaven per Dalton van belang (en dus niet de volgorde). Omdat elke Dalton meerdere goudstaven kan bezitten is er sprake van herhaling. Elke mogelijke verdeling kunnen we weergeven als route in nevenstaand rooster. De gekleurde route hoort bij de verdeling: Joe drie goudstaven, Jack en William twee, en Averell nul. Het aantal mogelijkheden (het aantal herhalingscombinaties) is ( 10 7 ) = ( 10 3 ) = 120 .

1

In de Verenigde Staten kun je op veel plaatsen het kansspel Keno spelen. De spelregels en de te winnen prijzen zijn niet overal precies hetzelfde. We kijken in deze opgave naar één bepaalde vorm waarin het spel gespeeld kan worden.
Op het lot staan de getallen 1 tot en met 80. Om mee te spelen moet je 10 van deze 80 getallen aankruisen. Dat kan op verschillende manieren. Hiernaast zie je een voorbeeld.

a

Bereken hoeveel mogelijkheden er zijn om 10 verschillende getallen op het lot te kiezen.

Bij de trekking worden door een trekkingsmachine willekeurig 22 getallen gekozen uit de getallen 1 tot en met 80. Nu gaat het erom, hoeveel van de 10 aangekruiste getallen goed zijn. Dat wil zeggen, hoeveel er bij de 22 getallen uit de trekkingsmachine zitten. Dit aantal bepaalt de prijs die je wint.
Bij de variant die wij bekijken, win je bij 0 goed een prijs en bij 2 of 3 goed niet. Blijkbaar zijn er meer mogelijkheden om 2 getallen goed te hebben, dan 0 .

b

Bereken beide aantallen mogelijkheden.

2

Intelligentie bij ratten
Bij onderzoek naar intelligentie van ratten wordt soms gebruik gemaakt van een gangenstelsel, een zogenaamd T-labyrint. Hiernaast zie je een plattegrond van zo'n T-labyrint.
In elk van de verticaal getekende gangen zit een klapdeurtje, dat slechts in één richting kan worden gepasseerd. Dat verhindert dat een rat terug naar 'beneden' kan lopen. Een rat kan langs een groot aantal 'routes' van ingang naar uitgang lopen. Hiernaast is een voorbeeld van een route getekend. Twee routes van ingang naar uitgang worden als gelijk beschouwd als dezelfde serie klapdeurtjes wordt gepasseerd.

a

Hoeveel verschillende routes zijn er van ingang naar uitgang?

Bij P, Q en R worden de deurtjes vergrendeld waardoor drie doodlopende gangen ontstaan. Loopt de rat een doodlopende gang in, dan wordt dat als een fout geregistreerd. Neem aan dat de rat op willekeurige wijze zijn weg door het T-labyrint kiest en nooit tweemaal dezelfde doodlopende gang ingaat.

b

Toon aan dat het aantal routes zonder fouten precies de helft van het aantal routes uit vraag a is.

3

Jaap heeft een bedrag van 20 eurocent in zijn portemonnee.

Op hoeveel manieren kan dat bedrag zijn samengesteld?

4

We vormen rijtjes van lengte 10 met de cijfers 0, 1 en 2.

a

Hoeveel rijtjes kun je maken waarin de 0 niet voorkomt?

b

Hoeveel rijtjes kun je maken waarin de 1 minstens één keer voorkomt?

c

Hoeveel rijtjes kun je maken waarin de 2 precies drie keer voorkomt.

d

Hoeveel rijtjes kun je maken met twee keer 0, drie keer 1 en de rest 2?

5

De lift
In een flat met zeven verdiepingen stappen op de begane grond (B) drie bewoners in die naar hun eigen appartement willen. Ze drukken het knopje van hun verdieping in. Als een knopje eenmaal is ingedrukt gaat het bijbehorende lampje van de verdieping 1,2,3,4,5,6 of 7 branden.
Op hoeveel manieren kunnen de lampjes in de lift gaan branden in de volgende gevallen.

a

De bewoners wonen op dezelfde verdieping.

b

De bewoners wonen op verschillende verdiepingen.

c

Eén van de bewoners woont op de zevende verdieping.

d

Geen van de bewoners woont op de eerste verdieping.

6

Op een eiland staan acht huizen A tot en met H . Op een ander eiland staan zeven huizen 1 tot en met 7 . Elk huis op de twee eilanden wordt met elk ander huis verbonden. In de figuur zijn drie voorbeelden getekend.

a

Hoeveel verbindingen zijn mogelijk?

b

Hoeveel van die verbindingen verbinden huizen van het ene eiland met elkaar? En hoeveel verbinden huizen van het andere eiland met elkaar?

Je kunt op twee manieren het aantal verbindingen van huizen op het ene eiland met huizen op het andere eiland berekenen.

c

Doe dat.

7

m en n zijn positieve gehele getallen.
Er geldt: ( m 2 ) + ( n 2 ) + m n = ( m + n 2 ) .
Dit heb je in een speciaal geval in opgave 6 gezien.

a

Toon de gelijkheid aan zoals in de voorgaande opgave.

( n 2 ) is van de vorm: a n 2 + b n , voor zekere getallen a en b .

b

Laat dat zien en bepaal de getallen a en b .

(hint)
Laat zien dat ( n 2 ) = 1 2 n ( n 1 ) .
c

Toon met algebra aan: ( m 2 ) + ( n 2 ) + m n = ( m + n 2 ) .

8

In de figuur kun je op veel manieren COMBINATORIEK lezen. Een van de manieren is in de figuur aangegeven. Van boven naar beneden gaand mag je alleen naar de letter er direct links of rechts onder.

Hoeveel manieren zijn er? Schrijf je berekening op.

9

In de studiezaal zijn de plaatsen genummerd 1 tot en met 50. 25 leerlingen nemen plaats in de zaal. We letten alleen op de bezetting van de stoelen.

a

Hoeveel mogelijkheden zijn er waarbij de plaatsen met nummers lager dan 10 onbezet blijven?

b

Hoeveel mogelijkheden zijn er waarbij de nummers 1, 2 en 3 wel bezet worden en de nummers 4, 5, 6 en 7 niet?

c

Hoeveel mogelijkheden zijn er waarbij de nummers 1, 2 en 3 wel bezet worden en één van de nummers 4, 5, 6 en 7 niet?