boomdiagrammen


Boomdiagrammen.	© h.hofstede (h.hofstede@hogeland.nl)

We zijn thuis wat lui en hebben geen zin om te koken. Dus bestellen we maar Chinees.
De Chinees in onze wijk is niet zo groot en heeft nog niet zoveel gerechten. Hiernaast staat de kaart. Voor het voorgerecht hebben we 3 keuzes, voor het hoofdgerecht 4, en voor het bijgerecht 2.
Als we van alle drie eentje willen kiezen, hoeveel keuzes hebben we dan?

Laten we beginnen met het voorgerecht. Dan zijn daarvoor 3 mogelijkheden:

1. Pisang Goreng
2. Saté Babi
3. Loempia speciaal

Oké, stel dat we een keuze gemaakt hebben. Dan moeten we daarna het hoofdgerecht kiezen. Dat geeft bij elk mogelijk voorgerecht vier nieuwe mogelijkheden.
Voor het kiezen van de voorgerecht plus hoofdgerecht zijn er dan in totaal 12 mogelijkheden:

1.1. Pisang Goreng + Babi Pangang.
1.2. Pisang Goreng + Tjap Tjoy.
1.3. Pisang Goreng + Miefang met garnalen.
1.4. Pisang Goreng + Foe yong hai met kipfilet.
2.1. Saté Babi + Babi Pangang.
2.2. Saté Babi + Tjap Tjoy.
2.3. Saté Babi + Miefang met garnalen.
2.4. Saté Babi + Foe yong hai met kipfilet.
3.1. Loempia speciaal + Babi Pangang.
3.2. Loempia speciaal + Tjap Tjoy.
3.3. Loempia speciaal + Miefang met garnalen.
3.4. Loempia speciaal + Foe yong hai met kipfilet.

Let erop dat die 12 eigenlijk komt van 3 × 4. Immers bij elk van de drie voorgerechten zijn vier hoofdgerechten te kiezen.
Dat is in de figuur rechtsboven schematisch aangegeven.
Let erop dat elk uiteinde hoort bij een mogelijkheid. Zo is mogelijkheid 7 bijvoorbeeld de combinatie saté babi + miefang.

Voor de keuze van het bijgerecht komt dus bij elk van deze 12 mogelijkheden twee nieuwe keuzes, namelijk gemengde salade of atjar. De nieuwe lijst bestaat daarom uit 12 × 2 = 24 mogelijke keuzes.

1.1.1. Pisang Goreng + Babi Pangang + salade.
1.1.2. Pisang Goreng + Babi Pangang + Atjar.
1.2.1. Pisang Goreng + Tjap Tjoy + salade.
1.2.2. Pisang Goreng + Tjap Tjoy + Atjar.
1.3.1. Pisang Goreng + Miefang met garnalen + salade.
1.3.2. Pisang Goreng + Miefang met garnalen + Atjar.
1.4.1. Pisang Goreng + Foe yong hai + salade.
1.4.2. Pisang Goreng + Foe yong hai + Atjar.
2.1.1. Saté Babi + Babi Pangang + salade.
2.1.2. Saté Babi + Babi Pangang + Atjar.
2.2.1. Saté Babi + Tjap Tjoy + salade.
2.2.2. Saté Babi + Tjap Tjoy + Atjar.
2.3.1. Saté Babi + Miefang met garnalen + salade.
2.3.2. Saté Babi + Miefang met garnalen + Atjar.
2.4.1. Saté Babi + Foe yong hai + salade.
2.4.2. Saté Babi + Foe yong hai + Atjar.
3.1.1. Loempia speciaal + Babi Pangang + salade.
3.1.2. Loempia speciaal + Babi Pangang + Atjar.
3.2.1. Loempia speciaal + Tjap Tjoy + salade.
3.2.2. Loempia speciaal + Tjap Tjoy + Atjar.
3.3.1. Loempia speciaal + Miefang met garnalen + salade.
3.3.2. Loempia speciaal + Miefang met garnalen + Atjar.
3.4.1. Loempia speciaal + Foe yong hai + salade.
3.4.2. Loempia speciaal + Foe yong hai + Atjar.

De uiteindelijke figuur rechts heeft dus 24 uiteinden, waarbij elke uiteinde staat voor een mogelijke keuze. Dat getal 24 is afkomstig van 3 × 4 × 2 omdat er achtereenvolgens 3 en 4 en 2 keuzemogelijkheden waren.
Zo'n schematische figuur heet een BOOMDIAGRAM.

Het aantal takken van een boomdiagram bereken je door
de aantallen afzonderlijke keuzes met elkaar te vermenigvuldigen.

VERMENIGVULDIGINGSREGEL.

Dat met elkaar vermenigvuldigen dat nomen we ook wel de "vermenigvuldigingsregel".
Bedenk goed dat elk uiteinde van een tak van een boomdiagram een mogelijkheid weergeeft, en dat bij die mogelijkheid alle keuzes die je bij elke splitsing maakte tegelijk moeten plaatsvinden. Zo'n tak is eigenlijk één grote samengestelde gebeurtenis.

Als meerdere dingen allemaal tegelijk moeten gebeuren,
Dan moet je de aantallen daarvan met elkaar vermenigvuldigen om het totaal aantal mogelijkheden te krijgen.

Maar wacht even, dat kan efficiënter geformuleerd worden.....
Als dingen tegelijk moeten gebeuren, dan betekent dat dat het ene moet gebeuren EN het tweede EN het derde EN...EN....
Bij elk van die ENNEN splitst het boomdiagram in weer meer takken, dus moet je na afloop al die ENNEN met elkaar vermenigvuldigen. Kortom vanaf nu onthouden we dat:

"EN" betekent "×"

Een nummerbord bestaat uit twee letters- twee cijfers - twee letters.
Als alle letters en cijfers en combinaties ervan toegestaan zijn, hoeveel verschillende nummerborden zijn er dan?

45697600

Hoeveel mogelijke menu's zijn er samen te stellen als je in bovenstaand voorbeeld ook mag besluiten om geen voorgerecht of geen nagerecht of zelfs beiden niet te nemen?

(examenvraagstuk, deels)
Als je in Budapest met de metro wilt reizen moet je eerst een kaartje kopen. Zo'n kaartje is voorzien van 9 vakjes met daarin de cijfers 1 tm 9. Zodra je bent ingestapt moet je je kaartje in een ponsapparaat steken (volgens de pijlrichting en met de bedrukte zijde boven). Eén of meer cijfers worden dan in één keer weggeponst. Daardoor is aan het kaartje te zien in welke trein je reis begonnen is. Hiernaast zie je de afbeelding van een kaartje waaruit de nummers 1, 6 en 9 zijn weggeponst.

In een kaartje worden 2 gaatjes geponst die niet in dezelfde rij of kolom zitten.
Op hoeveel manieren kan dat?

Een koffiehuis verkoopt maar liefst 8 verschillende soorten koffie. Verder kan ik bij elk kopje dat ik bestel kiezen uit vier formaten (medium, small, large en extra-large). Ik moet ook nog beslissen of ik met of zonder suiker wil, en of ik met of zonder melk wil. Ze hebben trouwens drie soorten melk (room, mager en vol).
Hoeveel verschillende koppen koffie kan ik zo bestellen?

256

Op een enquêteformulier moet ik bij vraag 5, 6, 7 en 8 allerlei gegevens over mezelf invoeren:

Op hoeveel verschillende manieren kan iemand deze 4 vragen invullen?

180

Op een schaakbord moet ik een toren en een loper op willekeurige plaatsen neerzetten. Op hoeveel verschillende manieren kan ik dat doen als:

De toren de loper niet kan slaan?

3136

De toren en de loper elkaar niet kunnen slaan?

2576

Een datum bestaat meestal uit drie getallen: dag - maand - jaar.
Zo staat de datum 14 - 5 - 12 voor 14 mei 2012.
We bekijken alle dagen in de jaren 2010 tot en met 2019.
Hoeveel van deze dagen hebben een datum waarbij alle drie de getallen even zijn?

450

Hoeveel verschillende even getallen van 4 verschillende cijfers kun je maken als je mag kiezen uit de cijfers 1, 3, 4, 5, 6, en 9?

120

Examenvraagstuk HAVO Wiskunde B, 2004

Vier jongens en vijf meisjes gaan samen een avondje uit. Eerst gaan ze naar een musical en daarna naar een discotheek.

In de theaterzaal is voor hen een rij met 9 stoelen gereserveerd. Elke jongen gaat tussen twee meisjes zitten.

Bereken op hoeveel verschillende manieren de groep op deze 9 stoelen kan plaatsnemen.

2880

10.

Examenvraagstuk VWO, Wiskunde A, 2019-I

Tussen mei 2008 en februari 2013 werd voor personenauto’s de kentekenserie gebruikt die door de Rijksdienst voor het Wegverkeer sidecode 7 genoemd wordt.
Op de foto staat een van de eerste kentekens uit deze serie.

De kentekens bestaan uit twee cijfers, gevolgd door drie letters en tenslotte nog één cijfer.

Als we ervan uitgaan dat er geen beperkingen zijn aan de te gebruiken cijfers en letters, dan zijn er bijna 18 miljoen verschillende kentekens te maken met sidecode 7.

Bereken het aantal verschillende kentekens met sidecode 7. Geef je antwoord in gehele honderdduizendtallen.

In deze opgave gaan we echter van de volgende beperkingen uit:

Een kenteken mag niet met 00 beginnen

De eerste letter is G, H, J, K, L, N, P, R, S, T, X of Z

Klinkers (A, E, I, O, U, Y) worden niet gebruikt

De letters C en Q worden niet gebruikt

Bepaalde drielettercombinaties (zoals NSB) kunnen als aanstootgevend worden gezien en als gevolg daarvan zijn 82 drielettercombinaties uitgesloten

Een verslaggever van een autotijdschrift schrijft in een artikel dat door al deze beperkingen minder dan 20% van alle mogelijke kentekens uiteindelijk op een personenauto terecht zal komen.

Ga met een berekening na of de verslaggever gelijk heeft.

TWEE SPECIALE BOOMDIAGRAMMEN

Er zijn twee soorten boomdiagrammen die erg regelmatig zijn en bovendien in erg veel telproblemen voorkomen.

1. De Machtsboom.

De machtsboom is het meest regelmatige boomdiagram dat je je maar kunt voorstellen, en zoals we zullen zien is het aantal takken daarvan dan ook zeer makkelijk te tellen. De machtsboom herkennen we door:

Het aantal splitsingen is steeds gelijk

voorbeeld:
Je moet een multiple-choice proefwerk maken van 10 vragen met elke keer de keuzes a, b, c of d. Als je elke keer moet gokken, hoeveel mogelijkheden zijn er dan om deze vragen te beantwoorden?

Voor de eerste vraag zijn er 4 mogelijkheden. Maar voor de tweede wéér 4, en voor de derde en elke volgende vraag wéér 4 mogelijkheden. Een begin van het boomdiagram ziet er zó uit:

Dit is uiteraard nog maar een beginnetje: er zijn nog maar drie splitsingen (dus de antwoorden op 3 vragen) getekend. Het hele diagram zou 10 splitsingen geven. Dat valt dus niet meer te tekenen.
Maar toch kunnen we uitrekenen hoeveel takken dat enorme diagram zou krijgen. Immers er zijn elke keer 4 mogelijke keuzes, dus het aantal takken wordt elke keer met 4 vermenigvuldigd.
Dat geeft na 10 splitsingen 4 • 4 • 4 • 4 • 4 • 4 • 4 • 4 • 4 • 4 = 1048576 takken.
Je kunt dit aantal natuurlijk snel uitrekenen: het is 4¹⁰ . Vanwege dat tot-de-macht-nemen heeft zo'n volledig regelmatige boom de naam machtsboom heeft gekregen.

2. De Faculteitsboom.

Een faculteitsboom kenmerkt zich door het feit dat het aantal splitsingen steeds eentje minder wordt. Dat gebeurt vooral bij problemen waarbij er iets gekozen moet worden, dat niet wordt teruggelegd, zodat bij de volgende keuze het aantal mogelijkheden één minder is geworden. Een faculteitsboom herken je dus door:

Het aantal splitsingen wordt steeds één minder

voorbeeld:

Ik heb een landkaart voor mij liggen met 4 landen. Die wil ik graag gaan kleuren, en ik heb ook 4 verschillende kleurpotloden. Op hoeveel manieren kan ik deze kaart inkleuren als elk land een verschillende kleur moet krijgen?

Voor het eerste land kan ik kiezen uit 4 kleuren. Daarna voor het tweede land nog uit drie kleuren (de eerste kleur is afgevallen want die is al gebruikt) daarna voor het volgende land nog twee kleuren, en tenslotte voor het laatste land nog uit één kleur. Het boomdiagram ziet er zó uit:

Zoals je ziet telkens één splitsing minder.
Het totaal aantal takken is 4 × 3 × 2 × 1 = 24.
4 × 3 × 2 × 1 schrijven wiskundigen als 4 met een uitroepteken erachter: 4! en ze spreken het uit als "4 faculteit"

n! = n • (n - 1) • (n - 2) • ... • 1

Op je TI-83 vind je de knop bij MATH - PRB - 4: !

11.

Gooi 50 keer met een muntstuk en noteer elke keer of er KOP of MUNT uitkomt. Hoeveel mogelijke antwoorden zijn er?

2⁵⁰

12.

Een kandidaat in een televisiequiz heeft van de quizmaster 6 verschillende prijskaartjes gekregen en moet die leggen bij 6 verschillende artikelen. Op hoeveel manieren kan hij dat doen?

720

13.

Een gezin bestaat uit 5 kinderen. Als je kijkt naar de samenstelling van het gezin en alleen erop let of een kind een JONGEN of een MEISJE is, hoeveel mogelijke gezinssamenstellingen zijn er dan?

14.

Er worden in de eredivisie voetbal in een speelronde 13 wedstrijden gespeeld. Als je met een totoformulier meespeelt om de uitslagen te voorspellen, dan moet je voor elke wedstrijd voor het thuisspelende team invullen of het winst/verlies/gelijkspel wordt.
Op hoeveel manieren kun je zo'n formulier invullen?

1594323

15.

Tien automobilisten moeten hun auto gaan parkeren op 10 mogelijke parkeerplaatsen. Op hoeveel verschillende manieren kan dat gebeuren?

3628800

16.

Een beginnende popgroep heeft een repertoire van 16 nummers, die ze bij een optreden allemaal gaan spelen.
Hoeveel mogelijke "speelprogramma's" zijn er met deze 16 nummers?

2,09 • 10¹³

17.

Op een piano zitten 83 toetsen. Ik ga een melodietje spelen door 6 willekeurige toetsen na elkaar in te drukken
Hoeveel mogelijke melodietjes kan ik op die manier maken?

2,7 • 10¹¹

18.

We zijn met een groep van 8 mensen en gaan lootjes trekken voor de komende Sinterklaasviering. Op hoeveel verschillende manieren kunnen de lootjes worden getrokken, als iemand ook zichzelf kan krijgen?

40320

19.

Een palindroom is een woord dat hetzelfde is of je het nou gewoon leest of achterstevoren.
Voorbeelden zijn "parterretrap" en "koortsmeetsysteemstrook" en "lepel"
Als we elke combinatie van letters een woord noemen (het hoeft dus geen bestaand woord te zijn) hoeveel palindromen van 8 letters zijn er dan?

456976