Inhoud leereenheid 13
Combinatoriek Introductie Leerkern 13.1 13.2 13.3 13.4 13.5 13.6
23 24
Tellen, maar wat? 24 De ene verzameling is de andere niet, of toch wel? 27 Waar alle tellen mee begint 28 Herhalingsrangschikkingen 31 Rangschikkingen 34 Combinaties 37
Samenvatting Zelftoets
22
46
45
Leereenheid 13
Combinatoriek
INTRODUCTIE
De moderne wiskunde wordt opgebouwd vanuit de verzamelingenleer. Tot in de negentiende eeuw werd de wiskunde omschreven als de wetenschap van tellen en meten. Het meten is verscholen geraakt in allerlei meer of minder abstracte afstandsbegrippen. Zo zijn we in leereenheid 4 ook een ‘afstand’ in grafen tegengekomen. Het tellen is in de discrete wiskunde nog steeds een basisactiviteit. Door de opbouw van deze cursus komen we er nu pas aan toe, maar de meeste inleidingen in de discrete wiskunde beginnen ermee. Ook in het tellen weerspiegelt zich het karakter van de moderne wiskunde: veel telproblemen die we bekijken, hebben betrekking op het tellen van elementen in een geschikte verzameling of op het tellen van deelverzamelingen van een bepaald type. Tellen komt op allerlei plaatsen om de hoek kijken. Zo zouden we willen weten hoeveel verschillende pincodes van vier cijfers er zijn om te kunnen vaststellen of de kans op het goed gokken van een pincode van een gestolen pas wel verwaarloosbaar klein is. Of we willen weten hoe lang we de telefoonnummers moeten maken om zeker te weten dat we heel lang nieuwe telefoonaansluitingen kunnen aanbieden voor we iedereen moeten lastig vallen met veranderende telefoonnummers. Tellen speelt een fundamentele rol in de kansrekening: om bijvoorbeeld de kans te bepalen op een prijs in de lotto, moeten we het totaal aantal mogelijke uitkomsten van een lottotrekking tellen. LEERDOELEN
Na het bestuderen van deze leereenheid wordt verwacht dat u – de somregel en (algemene) productregel voor telproblemen kunt toepassen – eenvoudige telproblemen kunt vertalen in het tellen van k-herhalingsrangschikkingen, k-rangschikkingen of k-combinaties uit een n-verzameling – het aantal k-herhalingsrangschikkingen, het aantal k-rangschikkingen en het aantal k-combinaties uit een n-verzameling kunt bepalen – het aantal permutaties van een verzameling kunt bepalen – het aantal deelverzamelingen van een eindige verzameling kunt bepalen – het binomium van Newton kent en kunt toepassen – eenvoudige telproblemen kunt oplossen.
OUN
23
Discrete wiskunde B
Studeeraanwijzing Suggestie voor het oefenen in het herkennen van de verschillende typen telproblemen en in het tellen zelf: probeer in allerlei dagelijkse situaties te ‘tellen’. In deze leereenheid geven we een aantal voorbeelden van dit ‘huis-tuin-en-keuken’-tellen.
LEERKERN 13.1
Tellen, maar wat?
Een van de eerste vragen die we stellen als we in de discrete wiskunde bepaalde objecten onderzoeken, is hoeveel objecten er zijn van het beschouwde type. In leereenheid 2 kwamen we deelverzamelingen van een verzameling X = {a1, a2, ..., an} tegen. We vragen ons dan af hoeveel deelverzamelingen X heeft. En als we het over relaties op X hebben, dan kunnen we de vraag stellen hoeveel verschillende relaties er op X bestaan. Als we een aantal moeten tellen, dan is het noodzakelijk om ons eerst af te vragen wat we precies moeten tellen. In leereenheid 3 zijn we getallen en hun delers tegengekomen. Als we vragen hoeveel delers 24 heeft, dan moeten we wel weten of we 1 en 24 ook moeten meetellen, of dat we alleen de echte delers van 24, namelijk 2, 3, 4, 6, 8 en 12, moeten tellen. In leereenheid 4 zijn we grafen tegengekomen. Als we de grafen op 4 punten willen tellen, dan moeten we wel weten of we isomorfe grafen nu wel of niet als verschillende grafen moeten tellen. Of nog een ander voorbeeld: Zij A = {a, b, c, ..., z} de verzameling letters van het Nederlandse alfabet. Iemand vraagt ons op hoeveel manieren we vijf letters uit A kunnen kiezen. Zijn het de beginletters van vijf willekeurige namen uit het telefoonboek, dan mogen we een letter meer dan een keer kiezen, bijvoorbeeld b, b, s, s, t (van Barends, Bartels, Smulders, Smelik en Thijssen). Of we de letters in alfabetische volgorde opschrijven of niet doet niet ter zake. Zijn zesentwintig voetballers ‘genummerd’ met de letters van het alfabet en moeten we een zaalvoetbalploeg van vijf spelers samenstellen, dan moeten de vijf te kiezen letters verschillend zijn. Zo zouden i, p, s, t en u wel eens een heel sterke ploeg kunnen vormen.
24
OUN
Leereenheid 13 Combinatoriek
Zijn het letters die in de volgorde waarin ze gekozen zijn een woord of een label moeten vormen, dan mogen letters weer wel vaker voorkomen, maar nu doet het er wel degelijk toe in welke volgorde we de vijf letters kiezen. Zo is het rijtje s, t, u, i, p verschillend van het rijtje p, u, i, s, t, en het rijtje b, b, s, s, t is verschillend van het rijtje b, s, t, s, b. De laatste mogelijkheid is dat we rijtjes van vijf verschillende letters moeten maken: de volgorde doet er toe en een letter mag niet meer dan één keer voorkomen. In elk van de vier beschreven telsituaties is het antwoord op de telvraag anders. We zullen deze aantallen nu niet tellen. Aan het eind van deze leereenheid zijn we zover dat we in drie van de vier gevallen het antwoord zonder echt te tellen meteen kunnen geven. OPGAVE 13.1
Op hoeveel manieren kunnen we twee letters uit de verzameling B = {a, b, c} kiezen (maak bij voorkeur een lijstje van alle mogelijkheden) als a de volgorde er niet toe doet en elke letter meerdere malen mag voorkomen? b de volgorde er niet toe doet en elke letter hooguit eenmaal mag voorkomen? c de volgorde er wel toe doet en elke letter meerdere malen mag voorkomen? d de volgorde er wel toe doet en elke letter hooguit eenmaal mag voorkomen?
OUN
25
Discrete wiskunde B
Samenvattend kunnen we zeggen dat de vraag op hoeveel manieren we vijf letters uit A = {a, b, c, ..., z} kunnen kiezen, in deze vorm nog niet te beantwoorden is: we moeten ook weten of de volgorde er wel of niet toe doet en of we letters vaker mogen kiezen of niet. Tellen bestaat uit twee stappen: vaststellen wat er geteld moet worden, en het tellen zelf.
Kiezen uit een verzameling Kiezen zonder herhaling Kiezen met herhaling
Tellen bestaat dus uit twee stappen: eerst moeten we heel precies vaststellen wat er geteld moet worden, en dan pas gaan we daadwerkelijk tellen. In het vervolg zullen we veel telproblemen formuleren in de vorm van kiezen uit een verzameling. Als we een element hooguit een keer mogen kiezen, spreken we van kiezen zonder herhaling. Als de elementen vaker gekozen mogen worden, dan spreken we van kiezen met herhaling. Als de volgorde van kiezen er wel toe doet, spreken we van rangschikking met of zonder herhaling, of van rij (altijd met herhaling), of van permutatie (altijd zonder herhaling). Als de volgorde er niet toe doet, dan hebben we het over combinatie met of zonder herhaling, of deelverzameling (altijd zonder herhaling). Zo komen we dus bij het tellen van het aantal manieren waarop we k elementen uit een verzameling met n elementen kunnen kiezen tot vier verschillende telproblemen. In figuur 13.1 zijn deze mogelijkheden in een schema weergegeven, met de bijbehorende meest voorkomende termen.
FIGUUR 13.1
De vier telsituaties
OPGAVE 13.2
Met welke telsituatie hebben we te maken als we de volgende aantallen willen bepalen: a het aantal verschillende pincodes van bankpassen b het aantal verschillende vijftallen kaarten dat uit een kaartspel kan worden getrokken c de mogelijke uitslagen van een wielerwedstrijd d het aantal verschillende nummerborden van auto’s e de mogelijke uitslagen van de lotto? Hoe groot de verzameling is waar we uit kiezen, is bepalend voor het aantal dat we tellen. Vandaar dat we de volgende termen hanteren. n-Verzameling k-Deelverzameling
26
DEFINITIE 13.1
Een n-verzameling is een verzameling met n elementen. Een k-deelverzameling is een deelverzameling met k elementen.
OUN
Leereenheid 13 Combinatoriek
Als we k elementen moeten kiezen, dan zullen we op dezelfde manier k als voorvoegsel toevoegen: zo spreken we van een k-rangschikking als we k elementen geordend en zonder herhaling moeten kiezen, en we spreken van een k-combinatie (of k-deelverzameling) als we k elementen zonder herhaling en ongeordend moeten kiezen, enzovoort. We zullen al deze termen hierna in de betrokken paragrafen nog eens netjes definiëren. Herhalingscombinaties zijn minder eenvoudig te tellen. Dat zullen we in deze cursus dan ook niet doen, maar voor de overige aantallen zullen we in de komende paragrafen formules afleiden. We zullen ook samengestelde problemen kunnen oplossen. Een voorbeeld hiervan is het tellen van alle mogelijke postcodes. Een postcode bestaat uit een rij van vier cijfers en daarna twee letters. We moeten dus kiezen uit twee verschillende verzamelingen. De eerste vier elementen van het rijtje worden gekozen uit de cijfers 0, 1, ..., 9, de laatste twee uit een verzameling van twintig letters (bij de invoering is besloten dat de letters F, I, O, Q, U, Y niet mee doen). Maar ook voor de vier cijfers in postcodes geldt dat er uit verschillende verzamelingen gekozen moet worden, want op de eerste plaats mag geen 0 staan in een postcode. Autonummerborden vormen een ander voorbeeld van een samengesteld telprobleem. 13.2
De ene verzameling is de andere niet, of toch wel?
Voor we echt gaan tellen, willen we eerst de vraag bekijken of het uitmaakt voor het telproces uit welke n-verzameling we k elementen moeten kiezen. Een verzameling kan in principe uit van alles bestaan, als maar goed gedefinieerd is wat de elementen van de verzameling zijn. Zo kan een verzameling bestaan uit de auteurs van deze cursus, of uit tropische fruitsoorten. Om te kunnen kiezen, is het handig elk element in de verzameling een naam te geven. Dat doen we meestal door de elementen te nummeren, bijvoorbeeld X = {x1, x2, x3}. Let wel, het lijkt er nu op dat we de elementen van X geordend hebben, maar dat is niet zo, we hangen alleen maar nummers aan de x-jes om ze van elkaar te onderscheiden. Dat we ze in de volgorde x1, x2, x3 opschrijven, komt vanwege onze natuurlijke neiging getallen in volgorde van grootte op te schrijven. Maar goed, we zullen elementen in een verzameling dus vaak namen geven door ze te nummeren. Zo kunnen we de verzameling A bestaande uit de zesentwintig letters van het Nederlandse alfabet, nummeren met de getallen 1 tot en met 26, zeg in alfabetische volgorde. Het rijtje w, o, o, r, d zouden we nu ook kunnen aangeven door alleen de nummers van de betrokken letters op te schrijven. We krijgen dan het rijtje 23, 15, 15, 18, 4. Dit is een rijtje elementen uit de verzameling G = {1, 2, ..., 26}. Natuurlijk is er een groot verschil tussen de twee rijtjes. Het rijtje letters roept bij ons direct de associatie met het woord woord op, terwijl het rijtje getallen ons op het eerste gezicht niets zegt. Dat komt omdat cijfers en letters twee verschillende soorten objecten zijn. Van letters kunnen we rijtjes maken die woorden vormen, maar we kunnen ze niet bij elkaar optellen, om maar wat te noemen, terwijl dat laatste juist weer wel met getallen kan. Maar als het gaat om het aantal elementen in A of G, of het aantal 2-deelverzamelingen van A of G, dan doet het er niet toe welke verzameling we bekijken.
OUN
27
Discrete wiskunde B
Stel, we hebben de verzameling X = {a1, a2, a3, a4} en we willen het aantal 2-deelverzamelingen van X tellen. De 2-deelverzamelingen van X zijn {a1, a2}, {a1, a3}, {a1, a4}, {a2, a3}, {a2 a4}, {a3, a4}. We kunnen deze deelverzamelingen van X ook aangeven door alleen de nummers van de elementen in de deelverzamelingen op te schrijven. Zo krijgen we voor de 2-deelverzamelingen van X de nummerverzamelingen {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}. En dit zijn de 2-deelverzamelingen van de verzameling N = {1, 2, 3, 4}. Het is duidelijk dat er evenveel 2-deelverzamelingen van X zijn als van N. Op dezelfde manier kunnen we het kiezen van element ai uit {a1, a2, ..., an} als het kiezen van nummer i uit de verzameling {1, 2, ..., n} opvatten. Op grond van deze overwegingen zullen we ons in de rest van de leereenheid meestal beperken tot het kiezen uit {1, 2, ..., n}, terwijl we daarmee de overeenkomstige problemen voor elke willekeurige andere verzameling met n elementen ook hebben opgelost. In plaats van kiezen uit {1, 2, ..., n}, kunnen we ook, als dat ons beter uitkomt, kiezen uit {0, 1, ..., n – 1}. OPGAVE 13.3
a Vertaal het gooien met een geldstuk (de munt kan neerkomen met kruis of munt omhoog) in het kiezen uit een verzameling getallen. b Vertaal het trekken van vijf kaarten uit een kaartspel in het kiezen uit een verzameling getallen. OPGAVE 13.4
(Huis-tuin-en-keuken-tellen) Vertaal het samenstellen van een keuzemenu met drie gangen, waarbij er keuze is uit 4 voorgerechten, 5 hoofdgerechten en 13 nagerechten, in het kiezen uit verzamelingen getallen. 13.3
Waar alle tellen mee begint
Het aantal manieren om een element uit een verzameling X te kiezen, is gelijk aan het aantal elementen in X, dat we schrijven als ⏐X⏐. Stel we hebben vier cijfers 1, 2, 3, 4 en drie letters a, b, c. Op hoeveel manieren kunnen we óf een cijfer óf een letter kiezen? Dat kan op 4 + 3 = 7 manieren. Hierbij is 4 het aantal elementen in de verzameling {1, 2, 3, 4}, is 3 gelijk aan het aantal elementen in de verzameling {a, b, c}, en is 7 het aantal elementen in de verzameling {1, 2, 3, 4, a, b, c} = {1, 2, 3, 4} ∪ {a, b, c}. Dit is een voorbeeld van de somregel. Algemeen geldt voor twee eindige verzamelingen A en B dat ⏐A ∪ B⏐ = ⏐A⏐ + ⏐B⏐ – ⏐A ∩ B⏐. Dit kunnen we als volgt beredeneren: bij ⏐A ∪ B⏐ wordt de doorsnede A ∩ B maar één keer meegeteld, terwijl deze doorsnede bij ⏐A⏐ + ⏐B⏐ tweemaal wordt meegeteld, namelijk zowel bij ⏐A⏐ als bij ⏐B⏐ (zie figuur 13.2a).
FIGUUR 13.2
28
De venndiagrammen bij de somregel
OUN
Leereenheid 13 Combinatoriek
In dit voorbeeld van vier cijfers en drie letters zijn de twee betrokken verzamelingen disjunct (dat wil zeggen, ze hebben geen enkel element gemeen, zie figuur 13.2b). Voor die situatie reserveren we de term somregel.
Somregel
Voor twee eindige verzamelingen A en B geldt ⏐A ∪ B⏐ = ⏐A⏐ + ⏐B⏐
als A ∩ B = ∅
OPGAVE 13.5
a Op hoeveel manieren kunnen we een cijfer of een letter kiezen? b Op hoeveel manieren kunnen we een munt of een bankbiljet kiezen? OPGAVE 13.6
a Welke 2-deelverzamelingen van {1, 2, 3, 4} bevatten 4? b Welke 2-deelverzamelingen van {1, 2, 3, 4} bevatten 4 niet? c Hoeveel 2-deelverzamelingen heeft {1, 2, 3, 4}? Waarom kunt u voor het bepalen van dit aantal de antwoorden bij a en b gebruiken? Nu weer terug naar de vier cijfers 1, 2, 3, 4 en drie letters a, b, c. Op hoeveel manieren kunnen we én een cijfer én een letter hieruit kiezen? We zien alle mogelijkheden in figuur 13.3. Hierbij staat het cijfer steeds voorop.
FIGUUR 13.3
Productregel
Cijfers én letters
Dit is een voorbeeld van de productregel: voor twee eindige verzamelingen A en B is het aantal manieren om én een element uit A én een element uit B te kiezen gelijk aan ⏐A⏐·⏐B⏐. Let wel, bij de productregel doet het niet ter zake of de verzamelingen A en B wel of niet een lege doorsnede hebben. De productregel staat ook wel bekend als het keuzeprincipe.
Keuzeprincipe
OPGAVE 13.7
a Op hoeveel manieren kunnen we én een cijfer én een letter kiezen? b Hoeveel verschillende bedragen zijn er mogelijk die opgebouwd zijn uit een bankbiljet en een munt? In feite hebben we in figuur 13.3 rijtjes gemaakt met op de eerste plaats een cijfer, dus een element uit de verzameling {1, 2, 3, 4}, en op de tweede plaats een letter, dus een element uit de verzameling {a, b, c}. Dit is de terminologie die we vaak zullen gebruiken als we de productregel toepassen.
OUN
29
Discrete wiskunde B
Net als bij de somregel, zit er ook bij de productregel een addertje onder het gras. Mochten we de somregel alleen toepassen als de verzamelingen A en B disjunct zijn, in het geval van de productregel moeten we er zeker van zijn dat we bij elke keuze uit A elk element van B mogen kiezen. We zeggen in dat geval dat de keuze uit de twee verzamelingen onafhankelijk is. Om duidelijk te maken wat dit inhoudt, bekijken we een voorbeeld waarin de keuze uit B juist afhankelijk is van die uit A.
Onafhankelijk Afhankelijk VOORBEELD 13.1
Het kenteken van een auto op het nummerbord bestaat in Nederland uit cijfers en letters. Voor sommige auto’s is dat vier letters en twee cijfers, voor andere is dat drie letters en drie cijfers. Nu wil de instantie die de kentekens toewijst, bepaalde lettercombinaties vermijden die een raar of onkies woord vormen.
Om het wat te vereenvoudigen, maken we ‘nummerborden’ die alleen uit twee letters bestaan, en we verbieden tweeletterige woorden. Bij de A als eerste letter mag nu niet meer een F, H, I, L, R, S, T, of U gekozen worden als tweede letter, terwijl bij de X als eerste letter wel elke letter van het alfabet als tweede letter gekozen mag worden. De keuze van de tweede letter is nu niet onafhankelijk van de keuze van de eerste letter. Het totaal aantal tweeletterige ‘nummerborden’ is dus niet 26 · 26 = 262. « OPGAVE 13.8
a Hoeveel rijtjes van twee letters zijn er waarbij de eerste letter een klinker is en de tweede letter een medeklinker (a, e, i, o en u nemen we als klinkers, de overige 21 letters zijn de medeklinkers)? b Hoeveel rijtjes van twee letters zijn er met op de eerste plaats een medeklinker en op de tweede plaats een klinker? c Als er rijtjes van twee letters gemaakt worden waarin hooguit één klinker mag voorkomen, is de keuze van de letters dan afhankelijk of onafhankelijk? De productregel kunnen we ook gebruiken om het aantal mogelijke postcodes te tellen. Nu moeten we rijtjes met lengte 6 maken, waarbij we voor de eerste plaats kunnen kiezen uit {1, 2, ..., 9}, voor de tweede tot en met vierde plaats uit {0, 1, 2, ..., 9}, en voor de laatste twee plaatsen uit de letters van het alfabet, uitgezonderd F, I, O, Q, U, Y. Het totaal aantal mogelijkheden is dan 9 · 10 · 10 · 10 · 20 · 20. Immers, het eerste cijfer kunnen we op 9 manieren kiezen en het tweede op 10 manieren, dus
30
OUN
Leereenheid 13 Combinatoriek
volgens de productregel zijn er 9 · 10 manieren om de eerste twee cijfers te kiezen. We passen nu de productregel opnieuw toe: er zijn 9 · 10 manieren om de eerste twee cijfers te kiezen en 10 manieren om het derde cijfer te kiezen, dus 9 · 10 · 10 manieren om de eerste drie cijfers te kiezen. Net zo volgt dat er 9 · 10 · 10 · 10 manieren zijn om de cijfers uit de postcode te kiezen. Ook geldt dat er 20 · 20 manieren zijn om de twee letters te kiezen. Een laatste toepassing van de productregel leert dat er 9 · 10 · 10 · 10 · 20 · 20 manieren zijn om een postcode samen te stellen. Dit herhaald toepassen van de productregel is nogal omslachtig. We zullen daarom in het vervolg gebruikmaken van een generalisatie van de productregel. Het bewijs van deze algemene productregel stellen we uit tot leereenheid 23. Algemene productregel
STELLING 13.1
Laat A1, A2, ..., An eindige verzamelingen zijn. Het aantal rijtjes a1, a2, ..., an met ai uit Ai, voor i = 1, 2, ..., n, is gelijk aan ⏐A1⏐ · ⏐A2⏐ · ... · ⏐An⏐. Merk op dat we in de algemene productregel wederom onafhankelijkheid van de keuzen uit de verschillende verzamelingen veronderstellen.
OPGAVE 13.9
Bij een aankleedpop zijn er 3 hoeden, 4 blouses, 3 broeken en 2 paar schoenen. a Op hoeveel manieren kan de pop aangekleed worden? b De rode broek kleurt niet bij de roze blouse. Hoeveel manieren blijven er over om de pop aan te kleden? 13.4
Herhalingsrangschikkingen
Het eenvoudigste van de vier telproblemen uit figuur 13.1 is het tellen van herhalingsrangschikkingen. k-Herhalingsrangschikking
DEFINITIE 13.2
Een k-herhalingsrangschikking uit een n-verzameling X is een rij met lengte k met elementen uit X, waarbij elk element vaker mag voorkomen (maar niet meer dan k maal). Een 1-herhalingsrangschikking uit een n-verzameling is eenvoudigweg een element uit de n-verzameling, en dus zijn er n verschillende 1-herhalingsrangschikkingen. De 2-herhalingsrangschikkingen uit de verzameling {1, 2, 3} staan in figuur 13.4. 11 12 13
21 22 23
FIGUUR 13.4
31 32 33
De 2-herhalingsrangschikkingen uit {1, 2, 3}
We zien dat het er 9 zijn (zie ook opgave 13.1c). Maar we kunnen dit aantal ook berekenen op de volgende manier. Een 2-herhalingsrangschikking is een rijtje met op de eerste plaats een element uit {1, 2, 3} en op de tweede plaats ook. Voor beide plaatsen zijn er dus 3 mogelijkheden. Het aantal 2-herhalingsrangschikkingen is op grond van de productregel dus 3 · 3 = 9.
OUN
31
Discrete wiskunde B
n2 verschillende 2-herhalingsrangschikkingen
Bevat de verzameling waaruit we kiezen niet 3 maar n elementen, dan zijn er n · n = n2 verschillende 2-herhalingsrangschikkingen. De 3-herhalingsrangschikkingen uit {1, 2, 3} zien we netjes gegroepeerd in figuur 13.5. 111 112 113
211 212 213
311 312 313
121 122 123
221 222 223
321 322 323
131 132 133
231 232 233
331 332 333
FIGUUR 13.5
De 3-herhalingsrangschikkingen uit {1, 2, 3}
Het zijn er 27. Dit aantal kunnen we ook als volgt tellen: we maken rijtjes met lengte twee, op de eerste plaats zetten we een element uit {1, 2, 3} en op de tweede plaats zetten we een 2-herhalingsrangschikking uit {1, 2, 3}. Het resultaat is een 3-herhalingsrangschikking. Hoeveel 3-herhalingsrangschikkingen zijn er dus? Wel, volgens de productregel is dat het aantal elementen in {1, 2, 3} maal het aantal 2-herhalingsrangschikking uit {1, 2, 3}, dus 3 · 9 = 27. Een nog andere manier is de volgende: we moeten rijtjes van lengte 3 maken, voor de eerste plaats hebben we de keuze uit 3 elementen, voor de tweede plaats ook, en voor de derde plaats ook. Omdat de keuzemogelijkheden voor de verschillende plaatsen onafhankelijk zijn, is het aantal 3 · 3 · 3 = 33 = 27. Als we kiezen uit een n-verzameling, dan is het aantal 3-herhalingsrangschikkingen gelijk aan n · n · n = n3. U ziet hoe we nu verder kunnen gaan en de 4-herhalingsrangschikkingen uit {1, 2, 3} kunnen tellen, en de 5-herhalingsrangschikkingen, enzovoort. We hebben hiermee de algemene productregel voor een concreet geval nog eens afgeleid. OPGAVE 13.10
a Hoeveel 4-herhalingsrangschikkingen uit {1, 2, 3} zijn er? b Hoeveel 2-herhalingsrangschikkingen uit {1, 2, 3, 4} zijn er? c Hoeveel 3-herhalingsrangschikkingen uit {1, 2, 3, 4} zijn er? We zullen nu een formule afleiden voor het aantal k-herhalingsrangschikkingen uit {1, 2, ..., n}. STELLING 13.2
Het aantal k-herhalingsrangschikkingen uit een n-verzameling is nk. Bewijs Een k-herhalingsrangschikking uit een n-verzameling is een rijtje met lengte k, waarbij voor elke plaats gekozen mag worden uit de verzameling {1, 2, ..., n}. Volgens de algemene productregel is het aantal k-herhalingsrangschikkingen uit {1, 2, ..., n} gelijk aan nk. □
32
OUN
Leereenheid 13 Combinatoriek
OPGAVE 13.11 (Aanw)
We gooien met een dobbelsteen en schrijven na elke worp de uitkomst op. Telkens als we zeven keer gegooid hebben, schrijven we verder op een nieuwe regel. Op elke bladzijde staan 24 regels. Hoeveel bladzijden hebben we ten minste nodig als we net zolang doorgaan met gooien en schrijven tot we alle mogelijke manieren om een regel te vullen in ieder geval eenmaal zijn tegengekomen? OPGAVE 13.12
(Huis-tuin-en-keuken-tellen) Een plantenbak, die aan de balkonleuning hangt, moet gevuld worden met viooltjes. Er passen 5 plantjes in op een rij en er zijn 5 verschillende kleuren viooltjes (rood, geel, blauw, wit en paars). Op hoeveel verschillende manieren kan de bak gevuld worden als elke kleur vaker mag voorkomen.
Via een één-op-ééncorrespondentie bewijzen we dat er evenveel objecten van de ene soort als van de andere soort zijn.
0,1-Rijtje
Een belangrijke methode om telproblemen op te lossen, is het probleem te herleiden tot een telprobleem dat we al opgelost hebben. Zo hebben we met een formule voor één telprobleem meteen een formule voor een hele klasse van telproblemen. Een voorbeeld van dat herleiden zien we hierna bij het tellen van deelverzamelingen. We wijzen op een belangrijk aspect van het hierna volgende bewijs. We zullen bewijzen dat het aantal deelverzamelingen gelijk is aan een aantal rijtjes. Dat doen we door uit elke deelverzameling een uniek rijtje te maken, en omgekeerd uit elk rijtje een unieke deelverzameling te maken. Daarmee maken we een één-op-één-correspondentie tussen het ene soort objecten (de deelverzamelingen) en het andere soort objecten (de rijtjes). En vanwege deze één-op-één-correspondentie mogen we concluderen dat er evenveel objecten van de ene soort zijn als van de andere soort. Om het op een andere manier te zeggen: als we zouden volstaan om bij elke deelverzameling een uniek rijtje te maken, dan hebben we alleen bewezen dat er ten minste zoveel rijtjes zijn als er deelverzamelingen zijn. Door het beide kanten op te doen, krijgen we dan een gelijkheid. Een 0,1-rijtje is een rijtje bestaande uit nullen en enen.
OPGAVE 13.13 (Aanw)
Toon aan dat het aantal 0,1-rijtjes met lengte n gelijk is aan 2n. Met het resultaat dat we aantoonden in opgave 13.13 kunnen we het aantal deelverzamelingen van een n-verzameling tellen. Het bewijs bestaat uit het construeren van een één-op-één-correspondentie, namelijk tussen de deelverzamelingen en de 0,1-rijtjes. STELLING 13.3
Een n-verzameling heeft 2n verschillende deelverzamelingen. Bewijs Op grond van de overwegingen in paragraaf 13.2 mogen we de deelverzamelingen van {1, 2, ..., n} tellen. Met elke deelverzameling A van {1, 2, ..., n} associëren we op de volgende manier precies één 0,1-rijtje: als i in A zit, dan zetten we op de i-de plaats in onze rij een 1, en als i niet in A zit, dan zetten we op de i-de plaats een 0. Zo geeft de deelverzameling {1, 2} een rij met een 1 op de eerste twee plaatsen en een 0 op de overige plaatsen.
OUN
33
Discrete wiskunde B
Omgekeerd kunnen we met elk 0,1-rijtje van lengte n precies één deelverzameling van {1, 2, ..., n} maken: als op de i-de plaats een 1 staat, dan stoppen we i in de deelverzameling, en als op de i-de plaats een 0 staat, dan stoppen we i niet in de deelverzameling. Zo geeft het rijtje met alleen maar nullen de lege deelverzameling en het rijtje met alleen maar enen heel {1, 2, ..., n}. Er zijn dus precies evenveel deelverzamelingen van {1, 2, ..., n} als er 0,1-rijtjes zijn met lengte n. Met de algemene productregel hebben we in opgave 13.13 vastgesteld dat het aantal 0,1-rijtjes met lengte n gelijk is aan 2n. □ Merk op dat het aantal deelverzamelingen van een n-verzameling ook al geteld is in leereenheid 6. Dat we het hier ook doen, komt omdat de methode van tellen in deze leereenheid uitgebreid behandeld wordt. OPGAVE 13.14
Als u het bewijs van stelling 13.3 niet helemaal hebt kunnen volgen, probeer dan het aantal deelverzamelingen van {1, 2, 3} te tellen door eerst de deelverzamelingen van {1} systematisch op te schrijven, dan met behulp daarvan die van {1, 2}, en ten slotte die van {1, 2, 3}. OPGAVE 13.15
a Hoeveel 8-herhalingsrangschikkingen uit {0, 1, 2, ..., 9} zijn er? b Hoeveel mogelijke telefoonnummers van tien cijfers zijn er die beginnen met een 0 maar niet met 00 of 06? 13.5
Rangschikkingen
We zullen nu rangschikkingen zonder herhaling tellen. We doen dat in twee stappen. Eerst tellen we het aantal manieren waarop we alle elementen van een verzameling kunnen rangschikken, en daarna op hoeveel manieren we k elementen geordend uit een verzameling kunnen kiezen. Rangschikking Permutatie
DEFINITIE 13.3
Een rangschikking of een permutatie van een n-verzameling is een rij met lengte n waar elk element van de verzameling in voorkomt.
1 permutatie van 1 element 2 permutaties van 2 elementen
Het is duidelijk dat in een permutatie elk element van de verzameling precies eenmaal voorkomt. We bekijken eerst weer de kleine permutaties. De enige permutatie van {1} is de rij die alleen uit 1 bestaat. De verzameling {1, 2} heeft twee permutaties: 12 en 21. De permutaties van {1, 2, 3} zijn: 123 132
6 permutaties van 3 elementen
34
213 231
312 321
We zien dat we deze permutaties als volgt kunnen verkrijgen: we zetten een 1 op de eerste plaats en zetten daar dan de permutaties van {2, 3} achter, na een 2 op de eerste plaats zetten we de permutaties van {1, 3} en na een 3 op de eerste plaats zetten we de permutaties van {1, 2}. Het aantal permutaties van {2, 3} is twee, net als dat van {1, 3} en dat van {1, 2}. Omdat er drie mogelijkheden zijn om de eerste plaats op te vullen is dus het aantal permutaties van {1, 2, 3} gelijk aan 3 · 2 = 6.
OUN
Leereenheid 13 Combinatoriek
Op dezelfde manier kunnen we de permutaties van {1, 2, 3, 4} verkrijgen: we zetten een element op de eerste plaats en zetten dan alle permutaties van de overige elementen erachter: 1234 1243 1324 1342 1423 1432 24 permutaties van 4 elementen
2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421
4123 4132 4213 4231 4312 4321
Zo zijn er dus 4 · 6 = 24 permutaties van {1, 2, 3, 4}. We kunnen het aantal permutaties ook als volgt tellen: We kiezen eerst een element op de eerste plaats, daarvoor hebben we vier mogelijkheden; als we de eerste plaats ingevuld hebben, dan blijven er nog drie elementen over waaruit we kunnen kiezen voor de tweede plaats; daarna houden we nog twee elementen over waaruit we kunnen kiezen voor de derde plaats; ten slotte houden we een element over dat we op de laatste plaats moeten zetten. Zo is het aantal permutaties volgens de algemene productregel 4 · 3 · 2 · 1 = 24. Deze methode kunnen we natuurlijk voor grotere verzamelingen toepassen.
OPGAVE 13.16
Hoeveel permutaties zijn er van {1, 2, 3, 4, 5}? En van {1, 2, 3, 4, 5, 6}? Voor elk natuurlijk getal n is n! = n · (n – 1) · (n – 2) · ... · 3 · 2 · 1. Het symbool n! noemen we n faculteit (deze notatie is ook in leereenheid 8 ingevoerd). We definiëren verder 0! = 1 (dit blijkt in toepassingen handig te zijn).
n Faculteit
STELLING 13.4
Het aantal permutaties van een n-verzameling is n!. Bewijs We moeten rijtjes maken waar elk element van {1, 2, ..., n} precies eenmaal in voorkomt. Voor de eerste plaats hebben we n mogelijkheden. Als we de eerste plaats hebben opgevuld, dan hebben we voor de tweede plaats de keus uit de n – 1 overgebleven elementen. Zodra we de eerste twee plaatsen hebben ingevuld, hebben we voor de derde plaats de keus uit de n – 2 overgebleven elementen, enzovoort. Volgens de productregel is dus het aantal permutaties van {1, 2, ..., n} gelijk aan n · (n – 1) · (n – 2) · ... · 3 · 2 · 1 = n!. □ Merk op dat n! zelfs voor betrekkelijk kleine waarden van n al heel groot is.
OPGAVE 13.17
Bereken n! voor n = 7, 8, 9 en 10. OPGAVE 13.18
(Huis-tuin-en-keuken-tellen) a Op een cd staan 13 nummers. De cd-speler biedt de mogelijkheid de nummers in willekeurige volgorde af te spelen. Op hoeveel verschillende manieren kunt u de cd afspelen? b Op hoeveel manieren kunt u de potjes en flesjes op de planchette onder uw badkamerspiegel in een rij opstellen?
OUN
35
Discrete wiskunde B
Een permutatie kan opgevat worden als een functie. Het begrip functie is ingevoerd in leereenheid 7. Wat we er hier van moeten weten, is dat een functie f van een verzameling A naar een verzameling B aan elk element a uit A een element B toevoegt. Het element b dat we aan a toevoegen, noteren we met f(a) = b. Neem een permutatie van {1, 2, ..., n}, dat wil zeggen een rij a1, a2, ..., an, waarin elk element uit {1, 2, ..., n} precies eenmaal voorkomt. We maken nu de functie f van {1, 2, ..., n} naar {1, 2, ..., n} gedefinieerd als volgt: f(i) = ai, voor i = 1, 2, ..., n. VOORBEELD 13.2
De permutatie 31254 van {1, 2, 3, 4, 5} levert via voorgaande constructie de afbeelding f : {1, 2, 3, 4, 5} → {1, 2, 3, 4, 5} op met f(1) = 3, f(2) = 1, f(3) = 2, f(4) = 5 en f(5) = 4. In figuur 13.6 is deze functie op grafische wijze weergegeven.
FIGUUR 13.6
De grafische weergave van een permutatie
U ziet dat twee pijlen nooit hetzelfde eindpunt hebben. Anders gezegd, de functie is injectief, dat wil zeggen dat aan elke i een uniek element uit {1, 2, 3, 4, 5} wordt toegevoegd. Ook is het zo dat in elk element op de onderste rij een pijl aankomt; anders gezegd: de afbeelding is surjectief, dat wil zeggen dat aan elk element van {1, 2, 3, 4, 5} via f een element van {1, 2, 3, 4, 5} wordt toegevoegd. Een functie die tegelijkertijd injectief en surjectief is, heet bijectief. Voor verdere uitleg over de begrippen injectief, surjectief en bijectief wordt verwezen naar leereenheid 7. « OPGAVE 13.19
Controleer voor de verzameling {1, 2, 3, 4} dat een permutatie ervan een bijectieve functie is van {1, 2, 3, 4} op zichzelf. Bijectie
Een permutatie van een verzameling A is zo een bijectie van A op zichzelf. Daarmee is de volgende stelling een direct gevolg van stelling 13.4. STELLING 13.5
Het aantal bijecties van een n-verzameling op zichzelf is gelijk aan n!. Nu tellen we het aantal manieren om slechts k elementen geordend en zonder herhaling uit een n-verzameling te kiezen met k ≤ n. Dat kan op dezelfde manier als in het bewijs van stelling 13.4.
k-Rangschikking
DEFINITIE 13.4
Zij k ≤ n. Een k-rangschikking uit een n-verzameling X is een rij van k verschillende elementen uit X.
STELLING 13.6
Voor 1 ≤ k ≤ n is het aantal k-rangschikkingen uit een n-verzameling gelijk aan n(n – 1)(n – 2)...(n – k + 2)(n – k + 1)
36
OUN
Leereenheid 13 Combinatoriek
Bewijs We maken rijtjes met lengte k met elementen uit {1, 2, ..., n}. Voor de eerste plaats hebben we de vrije keus, er zijn dus n mogelijkheden. Als we de eerste plaats hebben ingevuld, dan kunnen we de tweede plaats invullen met een element uit de n – 1 overgebleven elementen. Nu hebben we voor de derde plaats nog de keus uit de overgebleven n – 2 elementen, enzovoort. Als we tenslotte de eerste k – 1 plaatsen van onze rij hebben ingevuld, dan kunnen we uit de overgebleven n – k + 1 elementen nog een element kiezen voor de laatste, k-de plaats van onze rij. Volgens de algemene productregel is het aantal k-rangschikkingen uit een n-verzameling gelijk aan n(n – 1)(n – 2)...(n – k + 2)(n – k + 1). □ OPGAVE 13.20
Hoeveel 3-rangschikkingen uit {1, 2, 3, 4} zijn er? Ziet u een verband met dit aantal en het aantal permutaties van {1, 2, 3, 4}? Zo ja, welk verband is er? Soms schrijven we wel (n)k voor n(n – 1)(n – 2)...(n – k + 2)(n – k + 1). We kunnen het natuurlijk ook schrijven als een quotiënt van faculteiten:
OPGAVE 13.21
Mastermind is een spelletje waarbij de ene speler een geheime code maakt die is opgebouwd uit een rijtje van vier gekleurde dopjes, terwijl de andere speler moet proberen de code met de kleuren op de juiste plaats te raden.
Als er zes kleuren zijn, hoeveel verschillende codes zijn er dan als elke kleur ten hoogste eenmaal mag voorkomen? En hoeveel verschillende codes zijn er als kleuren vaker mogen voorkomen? 13.6
Combinaties
We gaan nu over naar het ongeordend kiezen zonder herhaling. DEFINITIE 13.5
k-Combinatie
Een k-combinatie uit een n-verzameling X is een keuze van k elementen uit X zonder op de volgorde te letten. Kortom, een k-combinatie uit X is een k-deelverzameling van X. Op grond van onze overwegingen in paragraaf 13.2, kunnen we volstaan met het tellen van de k-deelverzamelingen van {1, 2, ..., n}. Omdat dit aantal zo’n belangrijke rol speelt op allerlei plaatsen in de wiskunde, voeren we er een apart symbool voor in.
DEFINITIE 13.6
Voor natuurlijke getallen n en k met n ≥ 0 is melingen van een n-verzameling.
OUN
⎛n⎞ ⎜k ⎟ ⎝ ⎠
het aantal k-deelverza
37
Discrete wiskunde B
n-kies-k n-boven-k
We spreken het symbool
⎛n⎞ ⎜k ⎟ ⎝ ⎠
uit als ‘n kies k’ of ‘n boven k’.
OPGAVE 13.22
Bereken door het aantal deelverzamelingen te tellen Kiesgetal Binomiaalcoëfficiëntgetal ⎛n⎞ ⎜k ⎟ ⎝ ⎠
= 0 voor k > n
⎛n⎞ ⎜n⎟ ⎝ ⎠
= 1 voor n ≥ 0
⎛n⎞ ⎜0⎟ ⎝ ⎠
= 1 voor n ≥ 0
⎛ 4⎞ ⎜ 2⎟ ⎝ ⎠
en
⎛5⎞ ⎜1⎟ ⎝ ⎠
.
We noemen deze getallen kiesgetallen of binomiaalcoëfficiënten. De oorsprong van de laatste term zullen we hierna nog tegenkomen. In de definitie hebben we geen beperkingen opgelegd aan k. Dat hoeft ook niet, want we kunnen geen deelverzameling vinden in {1, 2, ..., n} die meer dan n elementen bevat, zodat voor k > n geldt dat ⎛⎜⎝ kn ⎞⎟⎠ = 0. Een n-verzameling heeft maar één n-deelverzameling, namelijk zichzelf, dus geldt voor elke n ≥ 1 dat ⎛⎜⎝ nn ⎞⎟⎠ = 1. De lege verzameling kunnen we de 0-verzameling noemen. Deze verzameling heeft maar één deelverzameling, namelijk de lege deelverzameling, ofwel de 0-deelverzameling. Dus geldt volgens de definitie ⎛⎜⎝ 00 ⎞⎟⎠ = 1. We kunnen dit ook op de volgende, misschien wat gezochte manier motiveren. Op hoeveel manieren kunnen we niks uit niks kiezen? Wel, op precies één manier, door namelijk niks te kiezen. Merk op dat elke n-verzameling precies één 0-deelverzameling heeft, namelijk de lege deelverzameling. Dus volgt uit de definitie dat ⎛n⎞ ⎜ 0 ⎟ = 1. ⎝ ⎠ Blijft over: ⎛⎜⎝ kn ⎞⎟⎠ te bepalen voor 0 < k < n, met n ≥ 1. Om het bewijs van de volgende stelling voor te bereiden, kunt u eerst opgave 13.23 maken (u kunt de opgave ook overslaan en eventueel, als het bewijs van de stelling nog niet geheel duidelijk is, de opgave alsnog maken).
OPGAVE 13.23
Maak een lijst van alle 2-deelverzamelingen van {1, 2, 3, 4} door ze onder elkaar op te schrijven. Schrijf nu achter elke deelverzameling {i, j} alle rangschikkingen van de deelverzameling. Ziet u een verband tussen ⎛⎜⎝ 42 ⎞⎟⎠ , het aantal rangschikkingen van een 2verzameling en het aantal 2-rangschikkingen van {1, 2, 3, 4}? STELLING 13.7
Voor natuurlijke getallen k en n met 0 ≤ k ≤ n geldt
( kn ) = k !( nn–! k )!
(13.1)
Bewijs We weten al dat ⎛⎜⎝ n0 ⎞⎟⎠ = = 1. Dit klopt met de formule, want 0! = 1 (hier blijkt hoe handig deze afspraak is). Stel daarom nu dat 0 < k < n. Neem een k-deelverzameling A van {1, 2, ..., n}. Door de elementen van A op een rij te zetten, krijgen we een rangschikking van A. Volgens stelling 13.4 is het aantal rangschikkingen van de k-verzameling A gelijk aan k!. Elke rangschikking van A is vanzelfsprekend een k-rangschikking uit {1, 2, ..., n}. Zo horen bij elke k-deelverzameling van {1, 2, ..., n} precies k! zulke k-rangschikkingen uit {1, 2, ..., n}. Elke k-rangschikking uit {1, 2, ..., n} is op precies één manier te verkrijgen door de elementen van een k-deelverzameling van {1, 2, ..., n} op een rij te zetten. Dus het aantal k-deelverzamelingen van {1, 2, ..., n} maal k! is gelijk aan het aantal k-rangschikkingen uit {1, 2, ..., n}. Met stelling 13.6 geeft dit in formule
38
OUN
Leereenheid 13 Combinatoriek
( kn ) ⋅ k ! = ( n –n!k )! □
waaruit de gevraagde formule volgt. VOORBEELD 13.3
Als we met behulp van formule 13.1 een binomiaalcoëfficiënt uitrekenen, dan kunnen we ons veel rekenwerk besparen door, voor we teller en noemer gaan berekenen, eerst zoveel mogelijk factoren uit teller en noemer tegen elkaar weg te strepen, zie de volgende berekening:
(104) = 4!10!⋅ 6! = 1/1⋅⋅2/2⋅⋅3/3⋅⋅4/4⋅⋅5/1/ ⋅⋅6/2/ ⋅⋅73/ ⋅⋅84/ ⋅⋅95/ ⋅⋅106/ =
«
7 ⋅ 8 ⋅ 9 ⋅ 10 = 7 ⋅ 3 ⋅10 = 210 1⋅ 2 ⋅ 3 ⋅ 4
OPGAVE 13.24 (Aanw)
a Bereken met formule 13.1 de kiesgetallen ⎛⎜⎝ 42 ⎞⎟⎠ en ⎛⎜⎝ 63 ⎞⎟⎠ . b Bereken ⎛⎜⎝ 16 ⎞⎟⎠ en ⎛⎜⎝ 65 ⎞⎟⎠ ; bereken ⎛⎜⎝ 52 ⎞⎟⎠ en ⎛⎜⎝ 53 ⎞⎟⎠ . Wat valt u op aan deze uitkomsten? Heeft u hier een verklaring voor? OPGAVE 13.25 (Aanw)
(Huis-tuin-en-keuken-tellen) Een schouwburg biedt u de mogelijkheid om zelf een abonnement bestaande uit 6 voorstellingen samen te stellen uit een aanbod van 30 voorstellingen. a Uit hoeveel verschillende abonnementen kunt u kiezen? b Als de helft van het aanbod uit toneelvoorstellingen bestaat en de andere helft uit cabaretvoorstellingen en u wilt een abonnement samenstellen met 4 toneelvoorstellingen en 2 cabaretvoorstellingen, uit hoeveel abonnementen kunt u dan kiezen? In stelling 13.3 hadden we het aantal deelverzamelingen van een n-verzameling geteld, het zijn er 2n. Daarmee hebben we onmiddellijk de volgende stelling. STELLING 13.8
Voor elk natuurlijk getal n geldt n ∑ ⎝⎛ k ⎞⎠ = 2n 0 ≤ k ≤n
Bewijs Voor elke k telt ⎛⎜⎝ kn ⎞⎟⎠ het aantal k-deelverzamelingen van {1, 2, ..., n}. Dus volgens de somregel telt het linkerlid alle deelverzamelingen van {1, 2, ..., n}. Met stelling 13.3 volgt nu de formule. □ We zagen hiervoor al eens de strategie om een probleem te vertalen in een al opgelost probleem. Hierna volgt nog een voorbeeld van deze strategie. STELLING 13.9
Het aantal 0,1-rijtjes met lengte n met precies k enen is gelijk aan
OUN
⎛n⎞ ⎜k ⎟ ⎝ ⎠
.
39
Discrete wiskunde B
Bewijs Hoe kunnen we een 0,1-rijtje met precies k enen maken? Door in de rij de k plaatsen aan te wijzen waar we een 1 zullen zetten, waarna we de overige plaatsen opvullen met nullen. Op hoeveel manieren kunnen we onder de n plaatsen de k plaatsen aanwijzen voor de enen? Dat is het aantal manieren om k plaatsnummers te kiezen uit {1, 2, ..., n}, dus ⎛⎜⎝ kn ⎞⎟⎠ . □ Merk op dat we in dit bewijs ook in plaats van de k plaatsen voor de enen aan te wijzen, de n – k plaatsen voor de nullen hadden kunnen aanwijzen. Hieruit volgt dat ⎛⎜⎝ kn ⎞⎟⎠ = ⎛⎜⎝ n –n k ⎞⎟⎠ . In opgave 13.24b hebben we al kennis gemaakt met dit fenomeen in enkele concrete gevallen. We formuleren het als stelling en geven een alternatief bewijs. STELLING 13.10
Voor natuurlijke getallen n en k geldt ⎛n⎞ = ⎛ n ⎞ ⎝ k⎠ ⎝ n − k⎠
Bewijs Met behulp van stelling 13.7 volgt
( kn ) = k !( nn−! k )! = ( n −nk!)! k ! = ( n − k )! ( nn−! ( n − k ))! = ( n –n k ) Formulemanipulatie Combinatorisch bewijs
□
Dit bewijs van stelling 13.10 noemen we om voor de hand liggende redenen een bewijs met formulemanipulatie. Het bewijs met behulp van het kiezen van k plaatsen voor de enen of n – k plaatsen voor de nullen in een 0,1-rij met lengte n noemen we een combinatorisch bewijs: in plaats van met formules te manipuleren, proberen we daarbij de gelijkheid van de twee kiesgetallen aan te tonen via een redenering met het kiezen van elementen of het maken van combinaties. Het voordeel van een combinatorisch bewijs is dat we ‘begrijpen’ waarom de formule in de stelling geldt, terwijl formulemanipulatie alleen oplevert dat de formule juist is. Daartegenover staat dat formulemanipulatie, mits goed toegepast, meestal veel sneller gaat dan een combinatorisch bewijs.
Overigens moet hier worden opgemerkt dat er verschillende ‘stijlen’ of ‘smaken’ in de wiskunde bestaan. Aan de ene kant zijn er mensen die heel goed zijn in formulemanipuleren en zo heel snel allerlei problemen kunnen oplossen, aan de andere kant zijn er mensen die zich meer thuis voelen bij combinatorische bewijzen en daar heel spectaculaire dingen mee kunnen doen. Aanleg voor wiskunde is dus niet iets wat eenduidig bepaald is. Het is natuurlijk wel goed om ervaring op te doen met beide typen bewijs, en we zullen hierna zowel bewijzen met formulemanipulatie als combinatorische bewijzen zien. Een ander belangrijk hulpmiddel in de combinatoriek is om aantallen te herleiden tot kleinere aantallen. Een voorbeeld hiervan zien we in de volgende stelling.
40
OUN
Leereenheid 13 Combinatoriek
STELLING 13.11
Voor natuurlijke getallen n en k geldt ⎛ n + 1⎞ ⎛ n ⎞ ⎛ n ⎞ ⎜ k ⎟ = ⎜ k ⎟ + ⎜ k – 1⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
We geven twee bewijzen voor deze stelling; eerst een combinatorisch bewijs. Bewijs 1 De k-deelverzamelingen van {1, 2, ..., n, n + 1} kunnen we verdelen in twee soorten: ten eerste de k-deelverzamelingen die het element n + 1 niet bevatten, en ten tweede die welke het element n + 1 wel bevatten. De k-deelverzamelingen van de eerste soort zijn de k-deelverzamelingen van {1, 2, ..., n}. Daarvan zijn er ⎛⎜⎝ kn ⎞⎟⎠ . De k-deelverzamelingen van de tweede soort bestaan uit een (k – 1)-deelverzameling van {1, 2, ..., n} waar het element n + 1 nog aan is toegevoegd. Van dit type zijn er dus evenveel als er (k – 1)-deelverzamelingen zijn van {1, 2, ..., n}, dat wil zeggen ⎛⎜⎝ k n–1⎞⎟⎠ . Hieruit volgt onmiddellijk wat we moesten bewijzen. □ We geven nu een bewijs met formulemanipulatie. Bewijs 2 We passen stelling 13.7 aan het begin en aan het eind een keer toe.
( n k+ 1) = k ! ⋅ ((nn ++ 11)–! k )! = k !(⋅ n( n++11) ⋅–n!k )! = ( nk +! ⋅1( n– +k 1+–kk) )⋅!n! =
( n + 1 – k ) ⋅ n! k ⋅ n! + k ! ⋅ ( n + 1 – k )! k ! ⋅ ( n + 1 – k )!
=
n! n! + = n + n k –1 k ! ⋅ ( n – k ) ! ( k – 1) ! ⋅ ( n + 1 – k ) ! k
() ( )
□
Met behulp van stelling 13.11 kunnen we de binomiaalgetallen in een mooi schema onderbrengen dat bekend staat als de Driehoek van Pascal, zie figuur 13.7, die we al in leereenheid 1 tegenkwamen.
FIGUUR 13.7
De Driehoek van Pascal
OUN
41
Discrete wiskunde B
We nummeren de rijen in de driehoek van boven naar beneden met 0, 1, 2, ..., n, ... In de ‘nulde’ rij staat dus de 1 helemaal bovenin de driehoek, enzovoort. De n-de rij krijgen we nu door van links naar rechts de getallen ⎛⎜⎝ n0 ⎞⎟⎠ , ⎛⎜⎝ 1n ⎞⎟⎠ , ⎛⎜⎝ n2 ⎞⎟⎠ , ..., ⎛⎜⎝ kn ⎞⎟⎠ , ..., ⎛⎜⎝ n n–2 ⎞⎟⎠ , ⎛⎜⎝ nn–1⎞⎟⎠ , ⎛⎜⎝ nn ⎞⎟⎠ . Zo komt schuin links boven ⎛⎜⎝ k n−1⎞⎟⎠ precies ⎛⎜⎝ k n−1⎞⎟⎠ te staan en schuin rechts erboven ⎛⎜⎝ kn ⎞⎟⎠ . Volgens stelling 13.11 is zo elk getal in de Driehoek van Pascal de som van de twee direct erboven staande getallen. Als we beginnen met de randen van de driehoek vol te schrijven met enen, dan kunnen we daarna de driehoek verder opvullen met behulp van deze optelregel. In de driehoek ziet u ook fraai stelling 13.10 weerspiegeld. OPGAVE 13.26
Waarom moeten we op de randen van de Driehoek van Pascal enen invullen? OPGAVE 13.27
Bereken (x + y)2 en (x + y)3 en vergelijk de coëfficënten met de tweede en derde rij van de Driehoek van Pascal. OPGAVE 13.28
a Merk op dat (x + y)1 = x + y. Vergelijk de coëfficiënten hiervan met de eerste rij van de Driehoek van Pascal. b Merk op dat (x + y)0 = 1. Met welke 1 in de Driehoek van Pascal komt dit resultaat overeen? Opgave 13.27 en 13.28 suggereren dat we de coëfficiënten van (x + y)n kunnen vinden in de n-de rij van de Driehoek van Pascal. Het klopt in ieder geval voor n = 0, 1, 2, 3, en als we de moeite nemen (x + y)4 uit te rekenen, dan blijkt het nog steeds op te gaan. Maar in plaats van dat te doen, bewijzen we het meteen voor alle n. Binomium van Newton
STELLING 13.12
Voor elk natuurlijk getal n geldt ⎛ n ⎞ n −1 ⎛ n ⎞ n−2 2 ⎛ n ⎞ n −1 n ⎟x y + ⎜ ⎟ x y + ... + ⎜ ⎟ xy + y n – 1 n – 2 1 ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
( x + y )n = x n + ⎜
⎛n⎞ = ∑ ⎜ ⎟ xk y n−k 0 ≤ k ≤ n⎝ k ⎠
(13.2)
Bewijs Voor n = 0 is het linkerlid (x + y)0 = 1, en het rechterlid bestaat uit één term, namelijk die met 0 = k = n, dus ⎛⎜⎝ 00 ⎞⎟⎠ x0y0 = 1. Dus geldt de formule voor n = 0. Neem nu n ≥ 1. We schrijven (x + y)n als (x + y)(x + y)...(x + y). We hebben zo n factoren op een rij. Als we dit product uitwerken, dan krijgen we een som van allemaal termen met machten van x en y. De vraag is nu: hoe vaak komt zo’n term voor? Ofwel, hoe maken we bij het uitwerken van het product een term xkyn–k? Dat doen we door uit k factoren (x + y) de x te nemen en uit de overige factoren de y. Op hoeveel manieren kunnen we dus de term xkyn–k maken? Wel, op evenveel manieren als we k factoren onder de n factoren in (x + y)(x + y)...(x + y) kunnen aanwijzen, waar we dan de x uit nemen (terwijl we uit de
42
OUN
Leereenheid 13 Combinatoriek
overige de y nemen). Op hoeveel manieren kunnen we k elementen uit een n-verzameling kiezen? Dat weten we inmiddels uit ons hoofd, namelijk op ⎛⎜⎝ kn ⎞⎟⎠ manieren. Als we nu alle termen xkyn–k bij elkaar nemen, dan krijgen we ⎛⎜⎝ kn ⎞⎟⎠ x k y n – k . Doen we dit voor elke k tussen 0 en n, dan krijgen we formule 13.2. □ Het binomium van Newton werd al lang toegepast voordat Newton het zelf gebruikte als één van de hoekstenen voor de ontwikkeling van de differentiaalrekening. De Engelse wisen natuurkundige Isaac Newton (1642-1727) is een van de belangrijkste figuren uit de geschiedenis van de wetenschap. Hij is een van de ontdekkers van de differentiaal- en integraalrekening. Hij heeft de gravitatietheorie ontwikkeld, die de basis vormt voor wat inmiddels al de klassieke mechanica heet. Onderdeel van die gravitatietheorie is de wet van de zwaartekracht. In het binomium van Newton komt de tweeterm x + y voor. Het Latijnse woord voor tweeterm is binomium, wat het gebruik in dit verband verklaart. Dat het Latijnse woord binomium werd gebruikt, komt omdat tot het midden van de negentiende eeuw het Latijn internationaal dé taal van de wetenschap was, zoals dat sinds het midden van de twintigste eeuw het Engels is.
In stelling 13.12 hebben we geen veronderstellingen gedaan over de grootte van x en y. De formule is dus ook juist als we voor x en y bepaalde waarden invullen. Als we bijvoorbeeld x = y = 1 invullen, dan krijgen we stelling 13.8. Hier volgt nog een ander leuk voorbeeld van invullen. STELLING 13.13
Voor elk natuurlijk getal n geldt
()
k n ∑ ( − 1) k = 0
0≤ k ≤ n
Bewijs Vul bij het binomium van Newton in: x = –1 en y = 1.
□
Uit deze stelling kunnen we heel eenvoudig het volgende resultaat afleiden. STELLING 13.14
Een eindige verzameling heeft evenveel deelverzamelingen met een even aantal elementen als deelverzamelingen met een oneven aantal elementen. Bewijs In de formule van stelling 13.13 krijgen we – ⎛⎜⎝ kn ⎞⎟⎠ voor oneven en + ⎛⎜⎝ kn ⎞⎟⎠ voor even k. Brengen we de termen – ⎛⎜⎝ kn ⎞⎟⎠ voor oneven k naar rechts, dan krijgen we
∑
k = even
( nk ) =
∑
k = oneven
( nk )
Nu staat in het linkerlid het aantal deelverzamelingen met een even aantal elementen en in het rechterlid het aantal deelverzamelingen met een oneven aantal elementen. □
OUN
43
Discrete wiskunde B
We sluiten deze paragraaf af met telproblemen die wat complexer zijn. We formuleren de telproblemen in de vorm van trekken van kaarten uit een kaartspel. Trekken van kaarten gebeurt in een bepaalde volgorde. Als we alleen in het resultaat van de trekking geïnteresseerd zijn, dus welke kaarten we getrokken hebben, en niet in de volgorde waarin ze getrokken zijn, dan zeggen we dat we een greep hebben gedaan. Het kaartspel bestaat uit 52 kaarten verdeeld in vier kleuren van dertien kaarten. Er zijn twee rode kleuren, ruiten en harten, en twee zwarte kleuren, klaveren en schoppen. Elke kleur bestaat uit vier plaatjes, boer, vrouw, heer en aas, en negen niet-plaatjes, met de cijfers 2, 3, ..., 10. OPGAVE 13.29 (Aanw)
a Hoeveel verschillende grepen van 5 kaarten uit een kaartspel zijn er? b Hoeveel verschillende grepen zijn er van 13 kaarten? c Bij het bridgespel krijgt elk van de vier spelers, Noord, Oost, Zuid en West geheten, een greep van 13 kaarten. Hoeveel verschillende verdelingen zijn er in het bridgespel? In veel spelsituaties is ook de verdeling van de kleuren in een greep van belang. De telvragen worden dan wat complexer. VOORBEELD 13.4
Hoeveel verschillende grepen van 5 kaarten zijn er met 3 rode en 2 zwarte kaarten? We kiezen nu 3 kaarten uit de 26 rode kaarten en onafhankelijk daarvan 2 uit de 26 zwarte kaarten. Volgens de productregel is dus het gevraagde aantal ( kn ) .
«
OPGAVE 13.30 (Aanw)
a Hoeveel grepen van 8 kaarten zijn er met 3 schoppen? b Hoeveel grepen van 8 kaarten zijn er met 3 plaatjes? c Hoeveel grepen van 8 kaarten zijn er met 2 schoppen en 3 rode kaarten? d Hoeveel grepen van 8 kaarten zijn er zonder azen of harten? e Hoeveel grepen van 8 kaarten zijn er met 1 aas en 3 harten? De driehoek van ..., oosterse bronnen van de wiskunde In India toonde men al in een vroeg stadium belangstelling voor combinatorische problemen. In de zesde eeuw v.Chr. beweerde Sushrata in een boek over geneeskunde dat er 63 combinaties uit zes verschillende smaken kunnen worden gemaakt, namelijk door één smaak tegelijk te nemen, twee smaken enzovoorts. Dit is eenvoudig te controleren: of een enkele smaak er wel of niet inzit, geeft 2 mogelijkheden; of zes smaken er wel of niet inzitten, geeft 26 mogelijkheden, maar daarbij zit ook die ene mogelijkheid dat ze er alle 6 niet inzitten: 26 – 1 geeft inderdaad 63 combinaties. In zijn boek Chandasutra uit de derde eeuw v.Chr. bepaalt Pingala op hoeveel manieren het metrum in een poëtische compositie gevarieerd kan worden. In een metrum dat uit drie lettergrepen bestaat, kunnen volgens Pingala de volgende combinaties worden gemaakt: drie lettergrepen geeft één mogelijkheid, twee lange en een korte drie mogelijkheden, evenals een lange en twee korte, drie korte lettergrepen kan weer op één manier. Later zou algemeen gebruik van deze werkwijze worden gemaakt om de kwaliteit van verschillende versmaten te testen.
44
OUN
Leereenheid 13 Combinatoriek
Aan het einde van de tiende eeuw n.Chr. schreef Halayudha een commentaar op het boek van Pingala waarin hij de verschillende combinaties visueel weergaf in de vorm van een piramide. We herkennen hierin de eerste vijf rijen (nulde tot en met vierde rij) van de driehoek die bij ons bekend staat als de driehoek van Pascal (1623-1662). Er is overigens geen aanwijzing dat de driehoek van Pascal in India ook voor andere doeleinden dan het bepalen van het aantal combinaties werd gebruikt. Er is zelfs niets dat erop wijst dat Indiase wiskundigen zich met de driehoek hebben beziggehouden, hoewel men in India al zeer vroeg (circa 300 v.Chr.) een methode had om niet alleen het aantal combinaties, maar ook het aantal permutaties te bepalen. De eerste keer dat de driehoek van Pascal in China werd afgebeeld, is in ‘De kostbare spiegel van de vier elementen’ uit 1303 van Zhu Shijie. In China werd de driehoek aanvankelijk vooral gebruikt om wortels van tweedegraads maar ook derde- en vierdegraads vergelijkingen te benaderen. Dat ging als volgt (voor het gemak geven we de vergelijking en de oplossing in moderne notatie weer). Om bijvoorbeeld x2 + 252x – 5292 = 0 op te lossen, probeert Zhu Shijie eerst geheeltallige wortels en vindt dat de oplossing ligt tussen x = 19 en x = 20. Vervolgens stelt hij x gelijk aan 19 + y (met 0 < y < 1), zodat de vergelijking wordt: (19 + y)2 + 252(19 + y) – 5292 = 0. Onder andere met behulp van de binomiaalcoëfficiënten (driehoek van Pascal!) wordt dit y2 + 290y – 143 = 0. De volgende stap is verrassend. De vergelijking wordt herleid tot y(y + 290) = 143, en dus y = 143/(y + 290). Omdat de waarde van y tussen 0 en 1 ligt, neemt Zhu Shijie nu een ‘willekeurige’ waarde voor de y in het rechterlid, namelijk 1. Dan volgt y ≈ 143/291, en dus is de benadering voor deze wortel van de oorspronkelijke vergelijking: x = 19 143 219 Kennelijk vond men deze benadering goed genoeg. Deze methode draag bij ons de naam van de Engelsman Horner die haar in 1819 (een half millennium later!) opnieuw heeft ontdekt. Tegenwoordig maken we natuurlijk gebruik van de computer. Met de methode van Horner, die eenvoudig te programmeren is, kunnen we hogeregraads vergelijkingen oplossen. Door de procedure herhaald uit te voeren (neem telkens de nieuw gevonden benadering als beginschatting voor een nieuwe berekening totdat het verschil tussen twee opeenvolgende waarden klein genoeg is), kunnen we de oplossing in de gewenste nauwkeurigheid krijgen.
SAMENVATTING
Tellen is één van de basisactiviteiten in de discrete wiskunde. Telproblemen kunnen handig geformuleerd worden als het kiezen van elementen uit een verzameling. Door de elementen van de verzameling waaruit gekozen moet worden, te nummeren, kunnen we veel telproblemen reduceren tot kiezen uit de (nummer)verzameling {1, 2, ..., n}. De basisregels voor het tellen zijn de somregel en de productregel. Door te onderscheiden tussen kiezen met of zonder herhaling en tussen geordend en ongeordend kiezen, krijgen we vier telsituaties. Voor drie ervan zijn formules afgeleid: 1 het aantal k-herhalingsrangschikkingen uit een n-verzameling is nk 2 het aantal k-rangschikkingen uit een n-verzameling is n!/(n – k)! 3 het aantal k-deelverzamelingen van een n-verzameling is ⎛⎜⎝ kn ⎞⎟⎠
OUN
45
Discrete wiskunde B
Met behulp van deze formules kunnen samengestelde telproblemen worden opgelost. Een belangrijke methode om telproblemen op te lossen, is het vertalen ervan in een al opgelost telprobleem. Een n-rangschikking van een n-verzameling heet een permutatie. Een permutatie kan opgevat worden als een bijectie van een verzameling op zichzelf. Een belangrijke formule met binomiaalgetallen is het binomium van Newton, dat efficiënt ingezet kan worden voor het verkrijgen van allerlei telformules. De overige stellingen in deze leereenheid kunnen beschouwd worden als voorbeelden van evenzovele telproblemen.
ZELFTOETS
1
Hoeveel verschillende rijtjes met lengte k zijn er te maken met de symbolen 0, 1 en 2?
2
Bewijs dat ⎛n + 2⎞ ⎛n⎞ ⎛ n ⎞ ⎛ n ⎞ ⎜⎝ k ⎟⎠ = ⎜⎝ k ⎟⎠ + 2⎜⎝ k – 1⎟⎠ + ⎜⎝ k – 2⎟⎠
voor 2 ≤ k ≤ n.
46
3
Op hoeveel verschillende manieren kunnen 6 personen op 11 stoelen plaatsnemen als die stoelen op een rij staan?
4
Bij het klaverjasspel worden 32 kaarten gelijkelijk verdeeld over 4 spelers, Noord, Oost, Zuid en West geheten. Hoeveel verschillende verdelingen zijn er?
OUN
Aanwijzingen
AANWIJZINGEN LEEREENHEID 13
13.11
Het aantal verschillende rijtjes van 7 uitkomsten van dobbelsteenworpen is het aantal 7-herhalingsrangschikkingen uit {1, 2, ..., 6}.
13.13
Een 0,1-rijtje met lengte n kan opgevat worden als een n-herhalingsrangschikking uit de 2-verzameling {0, 1}.
13.24
b Merk op dat 1 + 5 = 6 en
13.25
Bedenk dat de keuze uit de 15 toneelvoorstellingen onafhankelijk is van de keuze uit de 15 cabaretvoorstellingen.
13.29
c We vatten het delen op als eerst 13 kaarten aan Noord geven, dan 13 kaarten aan Oost, dan 13 kaarten aan Zuid en ten slotte de overblijvende 13 kaarten aan West. Op hoeveel manieren kunnen we 13 kaarten aan Noord geven? Als we een dertiental kaarten aan Noord hebben gegeven, op hoeveel manieren kunnen we dan uit de overige kaarten 13 kaarten aan Oost geven? Waarom mogen we deze twee aantallen vermenigvuldigen om zo het aantal manieren te berekenen om eerst 13 kaarten aan Noord te geven en daarna 13 kaarten aan Oost?
13.30
e Bedenk dat, als we de hartenaas kiezen, we nog maar 2 harten mogen kiezen. En als we een andere aas kiezen, dan moeten we uit de 12 harten die geen aas zijn, er nog 3 kiezen. Onderscheid deze twee gevallen (die tot twee disjuncte verzamelingen van grepen aanleiding geven).
OUN
⎛6⎞ ⎜ 1⎟ ⎝ ⎠
=
⎛6⎞ ⎜ 5⎟ ⎝ ⎠
en dat 2 + 3 = 5 en
⎛ 5⎞ ⎜2⎟ ⎝ ⎠
=
⎛5⎞ ⎜3⎟ ⎝ ⎠
.
113
Terugkoppelingen
TERUGKOPPELING LEEREENHEID 13 1
Uitwerking van de opgaven
13.1
a We schrijven de twee letters op in alfabetische volgorde: aa, ab, ac, bb, bc, cc. b We schrijven de letters op in alfabetische volgorde: ab, ac, bc. c De rijtjes zijn: aa, ab, ac, ba, bb, bc, ca, cb, cc. d De rijtjes zijn: ab, ac, ba, bc, ca, cb.
13.2
a Pincodes zijn herhalingsrangschikkingen. b De vijf kaarten in onze hand vormen een deelverzameling van het kaartspel. c De uitslag van een wielerwedstrijd kan gegeven worden in de vorm van een rangschikking van de rugnummers. d De nummerborden van auto’s vormen een samengesteld probleem. Een nummerbord is een rij met herhalingen, maar de eerste twee en de laatste twee elementen komen uit het alfabet en de middelste twee elementen uit de verzameling {0, 1, 2, ..., 9}. e De uitslag van de lotto bestaat uit een deelverzameling van de getallen 1 t/m 56.
13.3
a Als we kruis met een 0 voorstellen en munt met een 1, dan is gooien met een geldstuk te interpreteren als het kiezen van een element uit {0, 1}. b Een kaartspel (zonder jokers) bestaat uit 52 kaarten. We nummeren de kaarten met de getallen 1 t/m 52. We kunnen nu het trekken van vijf kaarten uit het kaartspel interpreteren als het kiezen van vijf elementen van de verzameling {1, 2, ..., 52}.
13.4
Nummer de vier voorgerechten met 1 t/m 4, de vijf hoofdgerechten met 5 t/m 9 en de dertien nagerechten met 10 t/m 22. Het samenstellen van een driegangenmenu komt nu neer op het kiezen van een element uit de verzameling {1, 2, 3, 4}, een element uit de verzameling {5, 6, 7, 8, 9} en een element uit de verzameling {10, 11, ..., 22}.
13.5
a Het aantal cijfers is 10 en het aantal letters is 26, dus volgens de somregel kunnen we op 10 + 26 = 36 manieren een cijfer of een letter kiezen. b Er bestaan euromunten in 8 verschillende waarden en bankbiljetten in 7 verschillende waarden, dus we kunnen volgens de somregel 8 + 7 = 15 verschillende bedragen bestaande uit een munt of een bankbiljet vormen.
13.6
a De 2-deelverzamelingen {1, 4}, {2, 4} en {3, 4}. b De 2-deelverzamelingen {1, 2}, {1, 3} en {2, 3}. c Volgens de somregel is het aantal 2-deelverzamelingen gelijk aan het aantal 2-deelverzamelingen die 4 bevatten, plus het aantal 2-deelverzamelingen die 4 niet bevatten, dus gelijk aan 3 + 3 = 6.
13.7
a Volgens de productregel op ⏐{0, 1, 2, ..., 9}⏐ · ⏐{a, b, c, ..., z}⏐ = 10 · 26 = 260 manieren. b Volgens de productregel in Europese valuta 7 · 8 = 56 verschillende bedragen.
OUN
121
Discrete wiskunde B
122
13.8
a Er zijn vijf klinkers, namelijk a, e, i, o en u, en dus eenentwintig medeklinkers. Volgens de productregel is het gevraagde aantal 5 · 21 = 105. b Volgens de productregel 21 · 5 = 105. c Afhankelijk, want als op de eerste plaats een klinker staat, mag er op de tweede plaats alleen een medeklinker staan (waarvan er 21 zijn), en als op de eerste plaats een medeklinker staat, mag elke letter op de tweede plaats staan.
13.9
a Volgens de algemene productregel zijn er 3 · 4 · 3 · 2 = 72 mogelijkheden. b We bepalen eerst hoeveel mogelijkheden afvallen: na keuze voor een rode broek en roze blouse kunnen nog op 3 · 2 manieren de hoed en schoenen gekozen worden. Er zijn dus 72 – 6 = 66 mogelijkheden over.
13.10
a 34. b 42. c 43.
13.11
Op elke regel komt een 7-herhalingsrangschikking uit {1, 2, ..., 6} te staan. Er zijn 67 = 279 936 verschillende 7-herhalingsrangschikkingen. Dus we hebben ten minste zoveel regels nodig. Met 24 regels per bladzijde hebben we ten minste 279 936/24 = 11 664 bladzijden nodig, dus zeker meer dan één schrift.
13.12
Het vullen van de bak komt neer op het maken van een 5-herhalingsrangschikking met de vijf kleuren. Er zijn er 55 van.
13.13
Een 0,1-rijtje met lengte n is een n-herhalingsrangschikking uit de verzameling {0, 1}, dus uit een 2-verzameling. Met stelling 13.2 volgt het gevraagde (bedenk hierbij dat de n uit de stelling hier 2 is en de k uit de stelling hier n is).
13.14
De deelverzamelingen van {1} zijn: ∅, {1}. De deelverzamelingen van {1, 2} zijn: ∅, {1}, {2}, {1, 2}. De deelverzamelingen van {1, 2, 3} zijn: ∅, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}.
13.15
a 108. b Voor de eerste plaats hebben we maar één keuze, voor de tweede plaats hebben we de keuze uit 1, 2, 3, 4, 5, 7, 8, en 9. Voor de overige acht plaatsen mogen we vrij kiezen uit de tien cijfers. Volgens de algemene productregel is het aantal 1 · 8 · 108.
13.16
Er zijn 24 · 5 = 120 permutaties van {1, 2, 3, 4, 5} en 120 · 6 = 720 permutaties van {1, 2, 3, 4, 5, 6}.
13.17
7! = 5040, 8! = 40 320, 9! = 362 880, 10! = 3 628 800.
13.18
a 13! b Als u k verschillende potjes en flesjes op uw planchette hebt staan, dan kunt u ze op k! verschillende manieren op een rij zetten.
OUN
Terugkoppelingen
13.19
Neem bijvoorbeeld de permutatie 4132. Dit is de bijectieve functie f gedefinieerd door f(1) = 4, f(2) = 1, f(3) = 3 en f(4) = 2.
13.20
4 · 3 · 2 = 24. Ja, dit is het aantal permutaties van {1, 2, 3, 4}. Immers, bij een 3-rangschikking doet één element uit {1, 2, 3, 4} niet mee. Als we dit achter de 3-rangschikking plaatsen, krijgen we een unieke permutatie van {1, 2, 3, 4}. Omgekeerd kunnen we uit elke permutatie door het laatste element weg te laten een unieke 3-rangschikking uit {1, 2, 3, 4} maken. Er zijn dus evenveel 3-rangschikkingen uit een 4-verzameling als er permutaties zijn van deze verzameling.
13.21
Er zijn 6 · 5 · 4 · 3 codes waarin alle kleuren verschillend zijn en 64 waarin kleuren vaker mogen voorkomen.
13.22
⎛4⎞ ⎜2⎟ ⎝ ⎠
13.23
= 6 en
⎛ 5⎞ ⎜ 1⎟ ⎝ ⎠
= 5.
2-deelverzameling
permutaties ervan
{1, 2} {1, 3} {1, 4} ... {3, 4}
12 en 21 13 en 31 14 en 41 ... 34 en 43
Het aantal 2-deelverzamelingen van {1, 2, 3, 4} is ⎛⎜⎝ 42 ⎞⎟⎠ , het aantal permutaties van een 2-deelverzameling is 2! en het aantal 2-rangschikkingen van {1, 2, 3, 4} is ⎛⎜⎝ 42 ⎞⎟⎠ · 2! = 4 · 3 = (4)2. a
⎛4⎞ ⎜2⎟ ⎝ ⎠
13.24
= 4!/(2! · 2!) = (3 · 4)/(1 · 2) = 6. = 6!/(3! · 3!) = (4 · 5 · 6)/(1 · 2 · 3) = 20. b ⎛⎜⎝ 61 ⎞⎟⎠ = 6 = ⎛⎜⎝ 65 ⎞⎟⎠ en ⎛⎜⎝ 52 ⎞⎟⎠ = 10 = ⎛⎜⎝ 53 ⎞⎟⎠ . Wat opvalt, is dat als de twee getallen onder sommeren tot het bovenste getal (dus 1 + 5 = 6 en 2 + 3 = 5), dan de kiesgetallen gelijk zijn. In het geval ⎛⎜⎝ 61 ⎞⎟⎠ moeten we één element uit {1, 2, 3, 4, 5, 6} kiezen. Dat kunnen we ook doen door de vijf overige elementen aan te wijzen die we juist niet kiezen. Dit aanwijzen kan op ⎛⎜⎝ 65 ⎞⎟⎠ manieren.
13.25
a ⎛⎜⎝ 306 ⎞⎟⎠ . b De keuze van de toneelvoorstellingen is onafhankelijk van de keuze van de cabaretvoorstellingen, dus volgens de productregel is het aantal ⎛ 15 ⎞ ⎛ 15 ⎞ ⎜ 4 ⎟⎜ 2 ⎟ . ⎝ ⎠⎝ ⎠
13.26
Op de linkerrand van de Driehoek van Pascal staan de getallen de rechterrand staan de getallen ⎛⎜⎝ nn ⎞⎟⎠ .
13.27
(x + y)2 = x2 + 2xy + y2, dus de coëfficiënten zijn van links naar rechts precies de getallen in rij 2 van de Driehoek van Pascal. (x + y)3 = x3 + 3x2y + 3xy2 + y3, dus de coëfficiënten zijn van links naar rechts de getallen in rij 3 van de Driehoek van Pascal.
13.28
a De coëfficiënten zijn precies de getallen in rij 1 van de Driehoek van Pascal. b Deze 1 komt overeen met de 1 bovenin de Driehoek van Pascal, dus met rij 0.
⎛6⎞ ⎜ 3⎟ ⎝ ⎠
OUN
⎛ n⎞ ⎜0⎟ ⎝ ⎠
en op
123
Discrete wiskunde B
13.29
a Vijf kaarten: ⎛⎜⎝ 525 ⎞⎟⎠ . 52 ⎞ b Dertien kaarten: ⎛⎜⎝ 13 ⎟. ⎠ 52 ⎞ c We kiezen eerst de 13 kaarten voor Noord op ⎛⎜⎝ 13 ⎟ manieren. ⎠ Bij elke van deze manieren moeten we uit de overige 39 kaarten er 13 ⎛ 52 ⎞ ⎛ 39 ⎞ 39 ⎞ kiezen voor Oost. Dit laatste kan op ⎛⎜⎝ 13 ⎟ manieren. Dus er zijn ⎜ 13 ⎟ ⎜ 13 ⎟ ⎠ ⎝ ⎠⎝ ⎠ manieren om eerst 13 kaarten voor Noord te kiezen en dan 13 kaarten voor Oost. Bij elk van deze manieren moeten we uit de overige 26 26 ⎞ kaarten er 13 kiezen voor Zuid. Dit laatste kan op ⎛⎜⎝ 13 ⎟ manieren. Er zijn ⎠ ⎛ 52 ⎞ ⎛ 39 ⎞ ⎛ 26 ⎞ dus ⎜⎝ 13 ⎟⎠ ⎜⎝ 13 ⎟⎠ ⎜⎝ 13 ⎟⎠ manieren om eerst 13 kaarten voor Noord te kiezen, dan 13 voor Oost en tenslotte 13 voor Zuid. De overblijvende 13 kaarten geven we aan West. Dit kan maar op één manier. Dus het totaal aantal 52 ⎞ ⎛ 39 ⎞ ⎛ 26 ⎞ kaartverdeling bij bridge is ⎛⎜⎝ 13 ⎟ ⎜ 13 ⎟ ⎜ 13 ⎟ . ⎠⎝ ⎠⎝ ⎠
13.30
a Kies, onafhankelijk van elkaar, 3 schoppen uit de 13 schoppen en 5 kaarten uit de overige 39 kaarten: ⎛⎜⎝ 133 ⎞⎟⎠ ⎛⎜⎝ 395 ⎞⎟⎠ . b Kies, onafhankelijk van elkaar, 3 plaatjes uit de 16 plaatjes en 5 nietplaatjes uit de 36 niet-plaatjes: . c Kies, onafhankelijk van elkaar, 2 schoppen uit de 13 schoppen, 3 rode kaarten uit de 26 rode kaarten en 3 kaarten uit de 13 overige kaarten (namelijk de klaveren): ⎛⎜⎝ 132 ⎞⎟⎠ ⎛⎜⎝ 263 ⎞⎟⎠ ⎛⎜⎝ 133 ⎞⎟⎠ . d We moeten nu kiezen uit 36 kaarten: ⎛⎜⎝ 368 ⎞⎟⎠ . e Nu moeten we opletten. We onderscheiden twee gevallen: 1 de aas is hartenaas, dat wil zeggen dat we nog 2 harten moeten kiezen uit de overige 12 harten en 5 kaarten uit de 36 kaarten die noch aas noch harten zijn: ⎛⎜⎝ 122 ⎞⎟⎠ ⎛⎜⎝ 365 ⎞⎟⎠ 2 de aas is niet hartenaas, dat wil zeggen dat we 1 aas kiezen uit de 3 overige azen, dan 3 harten kiezen uit de 12 harten die geen aas zijn, en tenslotte 4 kaarten uit de 36 kaarten die noch aas noch harten zijn: ⎛ 3 ⎞ ⎛ 12 ⎞ ⎛ 36 ⎞ ⎜ 1⎟ ⎜ 3 ⎟ ⎜ 4 ⎟ . ⎝ ⎠⎝ ⎠⎝ ⎠ Omdat deze gevallen elkaar niet overlappen, concluderen we met de somregel dat het gevraagde aantal ⎛⎜⎝ 122 ⎞⎟⎠ ⎛⎜⎝ 365 ⎞⎟⎠ + ⎛⎜⎝ 13 ⎞⎟⎠ ⎛⎜⎝ 123 ⎞⎟⎠ ⎛⎜⎝ 364 ⎞⎟⎠ is. 2
Uitwerking van de zelftoets
1
Zo’n rijtje is een k-herhalingsrangschikking uit een 3-verzameling, dus volgens stelling 13.2 is het aantal 3k.
2
– Bewijs met formulemanipulatie We passen stelling 13.11 enkele malen toe: ⎛ n + 2 ⎞ ⎛ n + 1⎞ ⎛ n + 1⎞ ⎛ n ⎞ ⎛ n ⎞ ⎛ n ⎞ ⎛ n ⎞ ⎜⎝ k ⎟⎠ = ⎜⎝ k ⎟⎠ + ⎜⎝ k – 1⎟⎠ = ⎜⎝ k ⎟⎠ + ⎜⎝ k – 1⎟⎠ + ⎜⎝ k – 1⎟⎠ + ⎜⎝ k – 2⎠⎟
– Combinatorisch bewijs We verdelen de k-deelverzamelingen van {1, 2, ..., n, n + 1, n + 2} in vier groepjes: 1 de k-deelverzamelingen van {1, 2, ..., n, n + 1, n + 2} die het element n + 1 en het element n + 2 niet bevatten, dit zijn dus k-deelverzamelingen van {1, 2, ..., n}: totaal ⎛⎜⎝ nk ⎞⎟⎠ stuks 2 de k-deelverzamelingen van {1, 2, ..., n, n + 1, n + 2} die het element n + 1 wel bevatten en het element n + 2 niet bevatten; zo’n deelverzameling krijgen we door een (k – 1)-deelverzameling van {1, 2, ..., n} te kiezen en daar het element n + 1 aan toe te voegen: totaal ⎛⎜⎝ k n–1⎞⎟⎠ stuks
124
OUN
Terugkoppelingen
3 de k-deelverzamelingen van {1, 2, ..., n, n + 1, n + 2} die het element n + 1 niet bevatten en het element n + 2 wel bevatten; zo’n deelverzameling krijgen we door een (k – 1)-deelverzameling van {1, 2, ..., n} te kiezen en daar het element n + 2 aan toe te voegen: totaal ⎛⎜⎝ k n–1⎞⎟⎠ stuks 4 de k-deelverzamelingen van {1, 2, ..., n, n + 1, n + 2} die het element n + 1 en het element n + 2 wel bevatten; zo’n deelverzameling krijgen we door een (k – 2)-deelverzameling van {1, 2, ..., n} te kiezen en daar de elementen n + 1 én n + 2 aan toe te voegen: totaal ⎛⎜⎝ k n– 2 ⎞⎟⎠ stuks. Aangezien deze vier groepjes twee aan twee disjunct zijn, volgt met de somregel de formule. 3
We zetten de 11 stoelen van links naar rechts op een rij. Nu kiezen we 6 stoelen uit de 11 stoelen. Dit kan op ⎛⎜⎝ 116⎞⎟⎠ manieren. Hebben we 6 stoelen gekozen, dan zetten we de 6 personen op een rij van links naar rechts en laten ze, van links naar rechts, op de 6 uitgekozen stoelen plaatsnemen. Op hoeveel manieren kunnen we 6 personen op een rij zetten? Dat is het aantal rangschikkingen van {1, 2, ..., 6}, dus dat is 6!. Zo hebben we bij elke keuze van 6 stoelen 6! manieren om de 6 personen erop te laten plaatsnemen. Het totaal aantal manieren om de persoon te laten plaatsnemen is dus het aantal manieren om 6 stoelen te kiezen maal het aantal manieren om 6 personen op een rij te zetten. Dat is dus 11! ⎛ 11 ⎞ = (11)6 . ⎜ 6 ⎟ ⋅ 6! = ⎝ ⎠ 5!
4
Kies eerst 8 kaarten uit de 32 kaarten voor Noord, dan 8 kaarten uit de overige 24 voor Oost, dan 8 kaarten uit de overblijvende 16 kaarten voor Zuid en geef ten slotte de laatste 8 kaarten aan West: aantal manieren is ⎛ 32 ⎞ ⎛ 24 ⎞ ⎛ 16 ⎞ ⎜ 8 ⎟ ⎜ 8 ⎟ ⎜ 8 ⎟ , zie eventueel de uitwerking van opgave 13.29c voor een ⎝ ⎠⎝ ⎠⎝ ⎠ vergelijkbaar probleem.
OUN
125
