Permutaties en Combinaties (2/4)

Permutaties bij gelijke elementen
Drie dezelfde elementen A hebben maar één permutatie, nl. AAA.
Verwisseling van de elementen levert immers niets nieuws op.
Maar stel eens, dat we elk element uniek maken door een kleurtje of een index
toe te voegen, zodat de elementen afzonderlijk herkenbaar zijn als
A1, A2 en A3, dan zijn er 3! = 6 permutaties. Zes keer zoveel.

Nu voegen we een nieuw element B toe.
Bij verschillende elementen A zijn er 4! permutaties.
Een permutatie is bv. A1A2BA3
Bekijk nu eens het volgende groepje permutaties:

A1A2BA3
A1A3BA3
A2A1BA3
A2A3BA1
A3A1BA2
A3A2BA1

Dat zijn er zes als we onderscheid maken tussen de A's. Is dat onderscheid er
niet, dan zijn ze allemaal gelijk en is er maar één permutatie.

De 24 mogelijke permutaties zijn zodoende te verdelen in groepjes van 6 permutaties,
die onderling gelijk zijn als de verschillen tussen de A's niet meetellen.
In de tabel hieronder zetten we alle permutaties op deze manier bij elkaar.

A1A2A3B
A1A3A2B
A2A1A3B
A2A3A1B
A3A1A2B
A3A2A1B
A1A2BA3
A1A3BA2
A2A1BA3
A2A3BA1
A3A1BA2
A3A2BA1
A1BA2A2
A1BA3A3
A2BA1A3
A2BA3A1
A3BA1A2
A3BA2A1
BA1A2A3
BA1A3A3
BA2A1A3
BA2A3A1
BA3A1A2
BA3A2A1

Dat het aantal permutaties met een factor 6 kleiner wordt bij gelijke A's
is geen toeval: er zijn 3 A's, die op 3! = 6 manieren op een rijtje kunnen staan.

Conclusie:

    Als je het aantal permutaties van N elementen moet berekenen en k elementen
    ervan zijn gelijk, dan moet je N! delen door k!
voorbeelden
1.
In hoeveel volgorden kan je de letters van het woord "poolvos" plaatsen?

Bij alle letters ongelijk: 7! = 5040.
Maar er zijn 3 letters "o" gelijk, dus moet worden gedeeld door 3! = 6
zodat 5040 / 6 = 840 het juiste antwoord is.

2.
Voor een instelling voor Hoger Beroepsonderwijs moet uit 10 kandidaten een
Adviseur, Beleidsmedewerker, Coördinator en een Directeur worden gekozen.
Hoeveel keuzes zijn er mogelijk?
We maken 4 stickers, met opschriften "A", "B", "C", "D" en dan nog zes stickers
met het opschrift "X", voor afgewezen sollicitanten.
De sollicitanten worden in een rijtje opgesteld en elk krijgt een sticker opgeplakt.
Het aantal volgorden van de stickers is dan gelijk aan het aantal te maken keuzen.
Oftewel: het aantal permutaties van de elementen ABCDXXXXXX moet worden berekend.
Dat is 10! / 6! = 5040.
Opmerking 1: dit antwoord was ook verkregen door 10.9.8.7 te berekenen.

Opmerking 2: een zelfde berekening is van toepassing op de keuze van een bestuur.
De volgorde van kiezen bepaalt de functie, elke kandidaat is 1 maal verkiesbaar.

Herhaalde toepassing
Op hoeveel manieren kunnen de letters van het woord "lantaarnpaal" op een rijtje
worden gezet?
Alle letters ongelijk: 12! = 479001600 manieren.
Als de a's gelijk: delen door 5! = 120. Dat wordt 12!/5! = 3991680.
Maar er zijn ook twee gelijke letters "l", dus nogmaals delen door 2! = 2.
3991680 / 2 = 1995840 en dan nog twee gelijke letters "n", weer delen door 2!
dat wordt 1995840 / 2 = 997920 volgorden.

voorbeelden
1.
Een internationale trein bestaat uit :
    - 1 locomotief
    - 4 goederenwagons
    - 2 restauratie wagons
    - 4 eerste klas rijtuigen
    - 8 tweede klas rijtuigen
In hoeveel volgorden kan deze trein worden samengesteld, als de locomotief
vooraan moet staan?

Sluit de locomotief uit.
18 wagons kunnen op 18! manieren achter elkaar staan.
4 goederenwagons: delen door 4!
2 restauratiewagens: delen door 2!
4 eersteklas rijtuigen: delen door 4!
8 tweedeklas rijtuigen: delen door 8!
Antwoord:
18!
4!.2!.4!.8!		 = 137837700

2.
Je bent jarig en kiest 8 vrienden uit een groep van 15 om dat te vieren.
Hoeveel keuzes zijn mogelijk?

Maak 15 stickertjes (in gedachten). 8 stickers met Y (Yes, gekozen) en 7 met N
(No, afgewezen).
Het aantal mogelijke keuzen is dan gelijk aan het aantal permutaties van
het 'woord' YYYYYYYYNNNNNNN.
Dat zijn er
15!
7!.8!		 = 6435
3.
Op het bordje hiernaast moet je zonder omwegen van A
linksboven naar B rechtsonder.
Alleen horizontale en vertikale stapjes zijn toegestaan.
In een hokje moet dus de keuze worden gemaakt:
naar hokje rechts of hokje eronder.
Hoeveel routes zijn mogelijk?

Om van linksboven naar rechtonder te komen, moet je
4 keer omlaag en 7 keer naar rechts gaan.
Als we "omlaag" coderen als "B" en "naar rechts" als "R",
dan is een route aan te geven met een volgorde van 4 B's en 7 R's.
Het aantal mogelijke routes is dan gelijk aan het aantal volgordes
van letters in het "woord" BBBBRRRRRRR.
Antwoord:
11!
4!.7!		 = 330