Permutaties en Combinaties (1/4) Permutaties Een volgorde van elementen noemen we een permutatie. Hierna gebruiken we als elementen de letters van het alfabet. Op hoeveel manieren zijn de letters van het woord "DOEK" op een rijtje te zetten? Elk rijtje kan beginnen met de letter "D", "O", "E" of "K". We maken vier groepen, die we noemen naar de eerste letter. Dat levert de groepen op: D O E K De volgende letter in groep D kan zijn: "O", "E" of "K". In groep "D" maken we daarom 3 subgroepjes "O", "E" en "K". Op dezelfde manier ontstaan zo in groep "O" de subgroepjes "D", "E" en "K". Na keuze van de eerste twee letters zien we dan: D O E K O D E K E D O K K D O E In groep "D" , subgroep "O" kunnen weer 2 subgroepjes worden gemaakt, want de letters "E" en "K" zijn nog over. Eenzelfde procedure passen we op alle subgroepjes toe. We kiezen overgebleven letters in de volgorde waarin zij in het woord voorkomen. D O E K K E E O K K O K O E E O O D E K K E E D K K D K D E E D E D O K K O O D K K D K D O O D K D O E E O O D E E D E D O O D Door deze sytematische aanpak zien we als eerste woord "DOEK" en als laatste woord precies de omkering "KEOD". De tabel hierboven heeft 24 regels en dat is ook het aantal volgorden waarin we vier verschillende letters op een rij kunnen zetten. Zo'n volgorde heet in de wiskunde een permutatie. In plaats van vier letters hadden we elk ander viertal elementen kunnen nemen. De 24 permutaties kwamen zo tot stand: - 4 groepen, een keuze uit elk element - voor elke groep 3 subgroepen, een voor elk element, dat nog over is - 2 sub/sub groepen per subgroep, omdat er nog uit 2 letters was te kiezen - 1 sub/sub/sub groep, voor de laatste letter was geen keuze meer. Berekening: 4.3.2.1 = 24 permutaties. Algemeen: n verschillende elementen hebben n(n-1)(n-2)(n-3)....(3)(2)(1) permutaties. Omdat deze notatie nogal wat ruimte inneemt en permutaties veel voorkomen, is er een speciale notatie voor bedacht: n! = (n)(n-1)(n-1).....(3)(2)(1) n! wordt uitgesproken als n faculteit. voorbeelden 1. Je wilt 5 familieleden een bezoek brengen. Dat kan je doen in 5! = 5.4.3.2.1 = 120 volgorden. 2. Een geautomatiseerde boormachine moet in een stalen plaat 12 gaten boren. De ontwerper vraagt zich af, hoe dit het snelst kan, dwz. wat de kortste route is tussen die gaten. Om dit te ontdekken moeten er 12! = 479001600 routes worden onderzocht. (interessant: er is geen snellere manier om hier achter te komen) rekenregels (n+1)n! = (n+1)! (n)(n-1)(n-2)....(10) = n! 9! afspraak 0! = 1