Permutaties en Combinaties (3/4) Welles Nietes In de voorbeelden hiervoor kwam voor, dat elementen wel of niet werden gekozen, waarbij de volgorde van kiezen niet van belang was. Het aantal mogelijke keuzes werd dan bepaald, door het vereiste aantal Yes of NO stickers te maken en die op de elementen te bevestigen. Voor dit soort ja/nee keuzes bestaat een aparte naam: een combinatie. Een keuze van drie corveërs uit een groep van 8 heet een combinatie van 3 uit 8. Er is ook een aparte notatie voor: ( 8 3 ) = 8! 3!.5! spreek uit: 8 boven 3 en let op: geen deelstreep zetten. Algemeen: Bij k keuzen uit N verschillende elementen, waarbij - elk element maar 1 maal kan worden gekozen - de volgorde van kiezen niet van belang is zijn ( N k ) = N! k!.(N-k)! combinaties mogelijk. De Somregel Uit een groep van 10 jongens en 14 meisjes wordt een schoonmaakploeg van 5 personen gekozen. Hoeveel keuzes zijn mogelijk als een ploeg alleen bestaat uit personen van hetzelfde geslacht? er zijn ( 10 5 ) = 10! 5!.5! jongensploegen en ( 14 5 ) = 14! 5!.9! meisjesploegen mogelijk. Totaal: 252 + 2002 = 2254 ploegen zijn mogelijk. Let op: het woordje "OF" werd gebruikt. (jongens of meisjes) De Productregel Een trein wordt samengesteld uit - 4 goederenwagons - 3 eersteklas rijtuigen - 8 tweedeklas rijtuigen Op hoeveel manieren is de trein samen te stellen? volgens eerdere aanpak 15! 4!.3!.8! Het kan ook anders: Het eenmalig te kiezen element is de plaats van elke wagon. Het aantal mogelijkheden om de goederenwagons te plaatsen: ( 15 4 ) Nu zijn er nog 11 plaatsen om te kiezen en we positioneren de eersteklas wagons: ( 11 3 ) Nu is er voor de tweedeklas wagons geen keuze meer, dwz. het aantal mogelijkheden is 1. Totaal aantal opstellingen: ( 15 4 ) ( 11 3 ) = ( 15! 4!.11! ) ( 11! 3!.8! ) = 15! 4!.3!.8! Let op: hier konden we het woordje "EN" gebruiken. Er moest plaats worden gezocht voor de goederenwagons en voor de eersteklas en voor de tweedeklas wagons. Voor het totale aantal keuzes moeten de deelkeuzes met elkaar worden vermenigvuldigd. Je kunt het ook zo zien: - parallel (naast elkaar, OF) = optellen - serie (achter elkaar, EN) = vermenigvuldigen voorbeelden 1. In een lotto moeten 6 getallen worden geraden uit 42. Hoeveel verschillende rijtjes kan je invullen met 4 goede getallen? Eerst 4 goede raden uit 6, dat kan op: ( 6 4 ) manieren. Nu nog twee foute getallen raden uit 36, dat kan op ( 36 2 ) manieren. Antwoord: ( 6 4 ) ( 36 2 ) = ( 6! 4!.2! ) ( 36! 2!.34! ) = 6.5.36.35 2.2 Het aantal mogelijke uitslagen is ( 42 6 ) = 42.41.40.39.38.37 6.5.4.3.2.1 = 5245786 Merk op, dat 42! op de rekenmachine een onnauwkeurig, afgerond, getal oplevert. Als je wilt weten hoeveel rijtjes je minimaal moet invullen om zeker te weten dat er een rijtje met 5 of 6 goede bijzit, dan moet je uitrekenen hoeveel rijtjes er zijn met 0,1,2,3,4 goed. Zoveel verschillende rijtjes + 1 moet je dan invullen. 2. Bij dit voorbeeld is wat kennis van kansrekening en verzamelingen handig. N personen vieren gezamenlijk het Sinterklaasfeest en trekken een lootje om het 'doelwit' van hun surprise te bepalen. We vragen ons af wat de kans is, dat de trekking moet worden overgedaan, omdat een van de deelnemers zijn eigen naam heeft getrokken. We nummeren de personen 1..n. Een trekking is dan te beschouwen als een permutatie van de getallen 1..n. Het aantal mogelijke trekkingen is n! Persoon 1 heeft de keuze uit (n-1) lootjes. Persoon 2 heeft daarna de keuze uit (n-2) lootjes, als tenminste persoon 1 niet persoon 2 had getrokken, want dan is de keuze uit (n-1) lootjes. Deze aanpak is dus niet zo handig. Eerst eens wat notatie invoeren: T(1) noemen we het aantal trekkingen waarbij 1 op zijn plaats blijft liggen dwz. persoon 1 zijn eigen lootje trekt. T(1.2) is het aantal permutaties (trekkingen) waarbij 1 en 2 op hun plaats blijven liggen. T(1+2) is het aantal permutaties waarbij 1 of 2 op hun plaats blijven liggen. Er geldt: T(1+2) = T(1) + T(2) - T(1.2) , dubbeltelling corrigeren. Zo is ook: T(1+2+3) = T(1+2) + T(3) - T((1+2).3), weer correctie ivm. dubbeltelling. Nu is: T((1+2).3) = T(1.3) + T(2.3) - T(1.2.3), corrigeer dubbeltelling. Bedenkende, dat T(1) = T(2) = T(3) en T(1.2) = T(1.3) = T(2.3) is de uitwerking: T(1+2+3) = 3.T(1) - 3.T(1.2) + T(1.2.3) T(1+2+....+n) = k1T(1) - k2T(1.2) + k3T(1.2.3) - .... Nu zijn T(1), T(1.2) en T(1.2.3) niet zo moeilijk te berekenen: T(1) = (n-1)! T(1.2) = (n-2)! T(1.2.3) = (n-3)! Rest, de constanten k1, k2, ... te bepalen. T(1) = T(2) = T(3) = ..... = T(n), zodat k1 = ( n 1 ) T(1.2) = ...T(5.9)..., zodat k2 = ( n 2 ) T(1.2.3) = ...T(5.6.9)..., zodat k3 = ( n 3 ) enzovoorts. T(1+2+3+...+n) = ( n 1 ) (n-1)! - ( n 2 ) (n-2)! + ( n 3 ) (n-3)! - ( n 4 ) (n-4)! ..... = n!(1 - 1 2! + 1 3! - 1 4! + ... 1 n! ) Is P(n) de kans, dat een trekking met n personen over moet worden gedaan, dan is P(n) = T(N) n! = 1 - 1 2! + 1 3! - 1 4! + ... 1 N! P(1) = 1 , wel logisch P(2) = 1 - 0,5 = 0,5 P(3) = 1 - 0,5 + 0,166666 = 0,666666 P(4) = 1 - 0,5 + 0,166666 - 0,0416666 = 0,625 De kans dat een trekking goed gaat is 1 - P(n) Nu is e x = 1 + x +  x 2 2!  +  x 3 3!  + .... zodat voor x = -1 geldt: e −1 =  1 2!  −  1 3!  +  1 4!  − .... Voor zeer hoge waarden van n nadert 1-P(n) tot e-1 = 0,367879441 (met dank aan E.C.Buissant des Amorie) Wanhoop dus niet bij een paar foute uitkomsten, gewoon even volhouden.