Combinatoriek
Nota’s in samenwerking met Anja Struyf en Sabine Verboven (Universiteit Antwerpen) In het dagelijkse leven worden we vaak geconfronteerd met vraagstukken waarvan de oplossing het tellen van het aantal elementen uit een verzameling inhoudt. Denk maar aan de vraag van een kredietkaartenbedrijf dat wil weten hoeveel verschillende pincodes van 4 cijfers er zijn. Met behulp van kansrekening kan het bedrijf dan de kans op het goed gokken van een pincode van een gestolen kaart bepalen. En die is liefst verwaarloosbaar klein... Of het telefoonbedrijf dat wil weten hoe lang ze hun telefoonnummers moeten maken om zeker te zijn dat ze nog heel lang kunnen doorgaan met nieuwe abonnees aan te maken voor ze mensen terug moeten lastig vallen met verandering van telefoonnummer. En als je graag wil weten hoeveel kans je maakt om de lotto te winnen zal je het totaal aantal mogelijke uitkomsten van een lottotrekking moeten berekenen. Kortom, tellen speelt een fundamentele rol in de kansrekening.
1 Variaties Voorbeelden. (1) Wedden op de hondenrennen. Aan een wedren nemen 14 honden deel, genummerd a, b, c, . . . , n. Bij de tierc´e moeten gokkers voorspellen welke honden op de eerste drie plaatsen (in volgorde) zullen eindigen. Enkele verschillende pogingen zijn (a, b, c), (a, b, n), (b, c, l), .... Deze pogingen noemen we variaties van 3 elementen uit de verzameling van de 14 honden. (2) Nummerplaten. Sommige Belgische autonummerplaten worden gevormd met 3 letters en 3 cijfers. FGH 875
ABK 334
UZA 919
...
Zowel in het cijfer- als het lettergedeelte speelt de volgorde een rol dus spreken we van variaties. Maar in tegenstelling tot voorbeeld 1 kunnen 1
1 Variaties
2
meerdere elementen meermaals voorkomen. Het letterdeel noemen we een herhalingsvariatie van 3 uit 24 (letters O en I worden geweerd vanwege hun overeenkomst met de cijfers 0 en 1) en het cijferdeel is een herhalingsvariatie van 3 uit 10. Def. Een variatie van p ∈ N elementen uit n ∈ N elementen (p ≤ n) is een geordend p-tal van p verschillende elementen gekozen uit een gegeven verzameling van n elementen. Twee variaties verschillen van elkaar als: • de volgorde van de elementen verschillen: (a, b, c) en (a, c, b) • de opgenomen elementen verschillen: (a, b, c) en (a, d, c) Stelling. Voor 1 ≤ p ≤ n is het aantal variaties van p elementen uit n gelijk aan Vnp := n(n − 1)(n − 2) . . . (n − p + 1) Bewijs. We nemen een rij van lengte p met de elementen {1, 2, . . . , n}. Voor de eerste plaats hebben ze de vrije keuze, er zijn dus n mogelijkheden. Eens de eerste plaats is ingevuld kan de tweede plaats ingevuld worden met een element uit de overgebleven n − 1 elementen. Er zijn dus reeds n(n − 1) geordende tweetallen. Voor de derde plaats is er de keuze uit de overgebleven (n − 2) elementen, enz. Als ze de eerste p − 1 plaatsen van de rij hebben ingevuld kan op de p-de plaats in de rij nog gekozen worden uit n − p + 1 elementen. Er zijn dus n(n − 1)(n − 2) . . . (n − p + 1) mogelijke geordende p-tallen. Een andere schrijfwijze voor het aantal variaties van p uit n getallen kan met behulp van de bewerking faculteit, gedefineerd als n! = n(n − 1)(n − 2) . . . 2 · 1. Vnp =
n! = n(n − 1)(n − 2) . . . (n − p + 1) (n − p)!
Voorbeelden. (1) Het aantal variaties van 3 elementen uit 4: V43 =
4! (4−3)!
=
4! 1!
= 4·3·2·1 = 24
(2) Hondenrennen: aantal mogelijke geordende drietallen uit 14: V143 = 2184 Eig. Vn0 = 1
Vnn = n!
14! 11!
=
2 Permutaties
3
Def. Een herhalingsvariatie van p ∈ N elementen uit n ∈ N elementen is een geordend p-tal van p elementen gekozen uit een gegeven verzameling van n elementen. Merk op dat hier p groter mag zijn dan n. Stelling. Het aantal herhalingsvariaties van p elementen uit n gelijk aan p
V n = n · n . . . · n = np
0
Voor de volledigheid stellen we V n = 1.
2 Permutaties Voorbeelden. (1) Anagram. In een kruiswoordraadsel vraagt men soms een anagram (letterwisseling) van een woord. Zo kan je van het woord ‘tak’ de woorden : tak, tka, atk, kta, akt en kat maken. (2) Taxi’s Een taximaatschappij moet 10 taxi’s toewijzen aan 3 luchthavens, luchthaven A heeft 5 taxi’s nodig, voor luchthaven B zijn er 4 nodig en luchthaven C vraagt er 1. Op hoeveel manieren kunnen de 10 taxi’s toegewezen worden?
Def. Een permutatie (Latijn voor “wisseling”) van n ∈ N elementen is een variatie van n uit n elementen. Een permutatie is dus een geordend n-tal uit n elementen. Aangezien een permutatie van n uit n elementen een variatie is geldt dat het aantal permutaties van n elementen, genoteerd door Pn , gelijk is aan n!. Pn = Vnn = n!.
3 Combinaties
4
Def. Zij n, p, q, r ∈ N met p + q + . . . + r = n dan is een herhalingspermutatie van n elementen waarvan p elementen van een eerste soort, q elementen van een tweede soort, ..., r elementen van een laatste soort, een geordend n-tal gevormd met deze p elementen van een eerste soort, deze q elementen van een tweede soort, ... en deze r elementen van een laatste soort. Twee herhalingspermutaties van eenzelfde type kunnen alleen van elkaar verschillen door de volgorde van de niet-gelijke elementen. Stelling. Het aantal herhalingspermutaties van n elementen waarvan p elementen van een eerste soort, q elementen van een tweede soort, ..., r elementen van een laatste soort, is µ ¶ n! p,q,...,r n Pn = =: p q ... r p!q! . . . r!
5,4,1
Vb. Taxi’s: aantal mogelijk manieren om de 10 taxi’s toe te wijzen: P 10 10! = 1260 5!4!1!
=
3 Combinaties Voorbeelden. (1) Lotto. Bij het LOTTO-spel moet je 6 verschillende getallen raden uit 1 to 42. Hoeveel mogelijkheden zijn er? Is dit een (herhalings)variatie van 6 uit 42? Waarom (niet)? (2) Domino. Op een dominosteen stelt het aantal ogen op iedere helft van een steen een getal voor. De getallen kunnen 0,1,2,3,4,5 of 6 zijn. Alle mogelijke verschillende stenen komen in het spel voor. Hoeveel verschillende dominostenen zijn er? Def. Een combinatie van p elementen uit n elementen (p ≤ n) is een deelverzameling van p elementen gekozen uit een gegeven verzameling van n elementen. De volgorde heeft geen belang. Een combinatie is dus een niet-geordend p-tal uit n elementen. Twee combinaties verschillen enkel van elkaar door de opgenomen elementen.
3 Combinaties
5
Stelling. Het aantal combinaties van p elementen uit n is µ ¶ n! n p =: Cn = p p!(n − p)!
Bewijs. We hebben reeds het aantal variaties van p uit n elementen is Vnp waarbij de p-tallen geordend zijn. Bij een combinatie speelt de volgorde geen rol dus zijn er teveel combinaties. Indien de opgenomen elementen dezelfde zijn, zijn er Pp = p! p-tallen die dezelfde combinatie geven. Dus, Vnp = Cnp · Pp of nog p n! Cnp = VPnp = p!(n−p)! Vb. In het eerste voorbeeld over het aantal mogelijkheden bij de LOTTO wordt 42! 6 dit C42 = 6!·36! = 5245786. Eig. (1) Cnn = Cn0 = 1 (2) Cnp = Cnn−p p+1 (3) De formule van Pascal Cnp + Cnp+1 = Cn+1
Bewijs. Ga dit na. Net zoals in de vorige gevallen is ook hier een herhalingscombinatie mogelijk; d.i. als je p elementen kiest uit n waarbij identieke elementen mogen worden gekozen en de volgorde geen rol speelt. Het aantal mogelijkheden om de p elementen over n plaatsen te verdelen is een p-combinatie van n elementen met p herhaling: C n . (Dit wordt ook wel pigeon hole principle genoemd: op hoeveel manieren kunnen we p duiven verdelen over n hokken) Merk op dat p hier ook groter kan zijn dan n. p
p Stelling. C n = Cn+p−1 =
¡n+p−1¢ p
.
Bewijs. Ga na. 2
2 = Vb. Domino: C 7 = C7+2−1
¡7+2−1¢ 2
=
¡8¢ 2
= 28
3 Combinaties
6
Driehoek van Pascal Met de formule van Pascal kunnen we de combinatiegep tallen Cn+1 afleiden uit de getallen Cnp . Dit levert ons het volgend schema op. n Cn0 Cn1 Cn2 Cn3 Cn4 Cn5 Cn6 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 Meestal staan deze getallen gerangschikt in een driehoeksvorm die men kan verderzetten zover nodig is. Elke rij begint en eindigt met een 1 aangezien Cn0 = Cnn = 1. Merk op dat de getallen in elke rij de co¨effici¨enten vormen van de merkwaardige producten, bv. in de tweede rij (a + b)2 = 1a2 + 2ab + 1b2 . Deze trend werd bewezen door de binomiumformule van Newton (binomium = tweeterm). Binomium van Newton
Stelling. ∀n ∈ N0 : ¶ µ ¶ µ µ ¶ µ ¶ n 0 n n n n−1 n n 0 n−1 n ab ab + a b + ... + a b + (a + b) = n n−1 1 0 n µ ¶ X n n−i i = a b i i=0
Bewijs. Bewijs dit door volledige inductie. ¡ ¢ De co¨effici¨enten ni worden daarom ook binomiaalco¨effici¨enten genoemd. Multinomiale ontwikkeling Dit is een veralgemineng van het binomium van Newton naar sommen met meer dan twee termen. Stelling. ∀n ∈ N0 : n
(x1 + x2 + . . . + xk )
=
Xµ
¶ n xn1 1 xn2 2 . . . xnk k n1 n2 . . . nk
waar de som loopt over alle (n1 , n2 , . . . , nk ) waarvoor de som n1 + n2 + . . . + nk = n.
3 Combinaties
De co¨effici¨enten noemd.
¡
n n1 n2 ... nk
¢
7
worden daarom ook multinomiaalco¨effici¨enten ge-
Aantal deelverzamelingen van een verzameling Zij A = {a, b, c, d, e}. Elke deelverzameling van A is een combinatie van elementen uit A. Het aantal deelverzamelingen met 0 elementen : C50 = 1 1 element : C51 = 5 2 elementen : C52 = 10 3 elementen : C53 = 10 4 elementen : C54 = 5 5 elementen : C55 = 1 Totaal aantal deelverzamelingen: 32 = 25 . Algemeen, Eig. Het aantal deelverzamelingen van een verzameling A (notatie #D(A)) met n ∈ N0 elementen is 2n . Bewijs. Er geldt voor #A = n dat #D(A) = de som van ¡n¢ de¡aantallen ¢ ¡n¢ deelverza¡ ¢ n melingen met 0, 1, 2, . . . , n elementen. Dus #D(A) = 0 + 1 + 2 + . . . + nn . Dit is vanwege de binomiumformule met a = b = 1 gelijk aan (1 + 1)n = 2n
4 Oefeningen
8
4 Oefeningen Eenvoudige oefeningen (1) Men vormt permutaties met vijf elementen a,b,c,d,e • Hoeveel permutaties beginnen met a? • Hoeveel permutaties beginnen met cd? • Hoeveel permutaties eindigen op abc? • Hoeveel permutaties beginnen niet met a? • Hoeveel permutaties bevatten de elementen b en c onmiddellijk na elkaar en in de volgorde bc? • Hoeveel permutaties bevatten de elementen a,b,c onmiddellijk na elkaar en in een willekeurige volgorde? • In hoeveel permutaties staat d een of meer plaatsen voor c? (2) Jan weet dat hij bij het boogschieten zeven van de tien keer de roos raakt. Hij gaat vier keer schieten. Hoeveel volgordes zijn er mogelijk bij twee keer raak en twee keer mis? (3) Hoeveel getallen van 5 cijfers, bestaande uit 2, 3, 4, 5, 6 en 7, kan je maken die groter zijn dan 54000? Je mag elk cijfer meer dan een keer gebruiken. (4) Een vlag moet gekleurd worden in 3 verschillende kleuren. Op hoeveel manieren kan je dit doen als je de beschikking hebt over 7 kleuren? (5) Tien vrienden spelen een tennistornooi. Hoeveel verschillende wedstrijden kunnen er worden gespeeld bij enkelspel? En bij dubbelspel? (6) Voor een schaakcompetitie moet elke school een ploeg van 3 spelers en een kapitein afvaardigen. Onze school heeft 10 geschikte kandidaten waarvan er 3 in aanmerking komen om kapitein te zijn. Op hoeveel manieren kan men een ploeg samenstellen rekening houdend met het feit dat de 3 kandidaat-kapiteins ook spelers kunnen zijn? (7) Een planoloog wil graag weten op grond van welke eigenschappen de bewoners van de straten van hun wijk beoordelen. Als onderdeel van zijn onderzoek legt hij een aantal proefpersonen groepjes van drie straten voor. Hij vraagt bij elk groepje aan te wijzen welke twee van de drie straten het meest op elkaar lijken. Het onderzoek heeft betrekking op 10 straten, voor het gemak A B C D E F G H K L genoemd. Hieruit worden alle mogelijke groepjes van drie gevormd en elk groepje wordt in alfabetische volgorde op een kaartje geschreven. Hieronder zie je drie voorbeelden: D D A F H C Hoeveel kaartjes zijn er nodig? G K D
4 Oefeningen
9
(8) Zeven werknemers van een groot bedrijf dat tien verdiepingen telt, stappen op de gelijkvloers de lift in. Onderstel dat ze onafhankelijk van elkaar beslissen op welke verdieping ze gaan uitstappen. Op hoeveel manieren zal de lift juist zevenmaal moeten stoppen vooraleer iedereen op zijn gekozen verdieping is uitgestapt? Op hoeveel manieren moet de lift juist 6 keer stoppen? (9) In de showroom van een garage staan 20 wagens, genummerd van 1 tot en met 20 naargelang de netto-kostprijs van de wagen. Nummer 1 staat hierbij voor de goedkoopste auto en nummer 19 bijvoorbeeld voor de op een na duurste. De garagist bewaart de autosleutels in een grote doos in zijn bureau. Onderstel dat de zoon van de garagist op zijn achttiende verjaardag geblinddoekt drie sleutels mag trekken uit de doos. Uit deze drie sleutels mag hij vervolgens een auto kiezen als verjaardagscadeau. Op hoeveel manieren is het mogelijk dat alle drie de autosleutels een nummer dragen dat groter dan of gelijk is aan 17? En dat minstens een van de drie autosleutels zo’n nummer draagt? (10) Bij een kaartspel 21 is het de bedoeling om 21 zo dicht mogelijk te benaderen, maar niet te overschrijden. Een aas staat hierbij voor een 1 of een 11. Een boer, dame en heer heeft de waarde 10. Veronderstel dat bij het begin van een spel lukraak twee kaarten aan jou worden aangeboden uit een goed geschud kaartspel. Op hoeveel manieren kan je onmiddellijk 21 vormen? En 19 of meer? Iets moeilijkere oefeningen (1) Op het jaarlijks bal van de gepensioneerdenbond worden honderd lotjes verkocht met de kans op vier verschillende hoofdprijzen en tien verschillende troostprijzen. Op hoeveel verschillende manieren is het mogelijk om uit 5 gekochte lotjes • juist 2 prijzen te winnen? • juist 1 hoofdprijs en 1 troostprijs te winnen? • enkel 2 troostprijzen te winnen? (2) Op de zolder van een oorlogsveteraan uit de tweede wereldoorlog staat een bak waarin 18 even grote stukken stof liggen : 6 rode, 6 zwarte en 6 gele. Op hoeveel manieren is het mogelijk om de Belgische driekleur te maken als je willekeurig 5 stukken stof uit de bak trekt? (3) Een programmertaal aanvaardt variabelen van ten hoogste 6 karakters. Het eerste karakter moet een klinker zijn, terwijl elk ander eventueel karakter ofwel een klinker ofwel een oneven cijfer moet zijn. Hoeveel variabelen kunnen er in deze programmeertaal gemaakt worden? Volgende letters worden als klinkers beschouwd : a, e, i, o, u.
4 Oefeningen
10
(4) Hoeveel woorden (zonder betekenis) van 26 letters kan men vormen als elke letter uit het alfabet tot 26 keer gebruikt mag worden? En als een letter uit het alfabet hoogstens 25 keer mag voorkomen, hoeveel woorden met 26 letters kunnen er dan gevormd worden? (5) Bij het pokerspel krijgt iedere speler bij de aanvang van het spel 5 kaarten. Er wordt gespeeld met 52 kaarten en er zijn 13 soorten kaarten, namelijk de nummers 1 tot en met 10, boer, dame en heer, en binnen elke soort zijn er 4 kaarten, namelijk harten, klaveren, ruiten en schoppen. (a) Op hoeveel mogelijke manieren kunnen 5 kaarten gedeeld worden? (b) Op hoeveel manieren kan een speler elk van de volgende combinaties toebedeeld krijgen bij de aanvang van het spel? i. Four of a kind : vier van eenzelfde soort + een vijfde van een andere soort. ii. Full house : drie van eenzelfde soort + twee van eenzelfde soort verschillend van de eerste soort. iii. Three of a kind : drie van eenzelfde soort + vierde van een andere soort + vijfde van nog een andere soort iv. Two pair : twee van eenzelfde soort + twee van eenzelfde soort, maar anders dan de eerste soort + vijfde van nog een andere soort. v. One pair : slechts twee van eenzelfde soort, alle andere van verschillende soort niet gelijk aan de eerste soort. Oplossingen : Eenvoudige oefeningen (1) 24, 6, 2, 96, 24, 36, 60 (2) 6 (3) 3456 (4) 210 (5) 45, 630 (6) 252 (7) 120 (8) 604800, 3175200 (9) 4, 580 (10) 64, 280
4 Oefeningen
Iets moeilijkere oefeningen (1) 9312940, 4093600, 4605300 (2) 6210 (3) 555555 (4) 2626 , 2626 − 26 (5) (a) 2598960 (b) 624, 3744, 54912, 123552, 1098240
11
