Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Combinatoriek W. Oele
27 januari 2014
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Deze les
Inleiding combinatoriek: de faculteit permutaties combinaties variaties de binomiaalco¨effici¨ent
W. Oele Combinatoriek
Binomiaalco¨ effici¨ ent
Variaties
Permutaties
Combinaties
De faculteit
Eenvoudige recursieve definitie: 0! = 1 n! = n(n − 1)! Voorbeelden: 5! = 5.4.3.2.1 = 120 100! = 100.99.98.97...3.2.1
W. Oele Combinatoriek
Binomiaalco¨ effici¨ ent
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
De faculteit
Faculteiten van grote getallen worden doorgaans benaderd met de fomule van Stirling(1692-1770): √ n! ≈ nn · e −n · 2πn
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Combinatoriek: permutaties
Op hoeveel verschillende manieren kunnen de letters a, b, c worden gerangschikt? eens proberen: abc acb bac bca cab cba
totaal: 6 mogelijke rangschikkingen of permutaties
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Combinatoriek: permutaties Denkwijze: Men neme een kast met 3 lades:
A
B
Eerste letter: 3 mogelijkheden 3
W. Oele Combinatoriek
C
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Combinatoriek: permutaties Denkwijze: Men neme een kast met 3 lades:
B
C
Tweede letter: 2 mogelijkheden 3·2
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Combinatoriek: permutaties Denkwijze: Men neme een kast met 3 lades:
C Derde letter: 1 mogelijkheid 3·2·1
W. Oele Combinatoriek
Binomiaalco¨ effici¨ ent
Variaties
Permutaties
Combinaties
Combinatoriek: permutaties
Denkwijze: Men neme een kast met 3 lades:
Totaal: 3 · 2 · 1 = 3! = 6
W. Oele Combinatoriek
Binomiaalco¨ effici¨ ent
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Variaties
Combinatoriek: permutaties
Algemeen: n letters kunnen in n lades worden geplaats op n! verschillende manieren. 8 auto’ s voor het stoplicht? 8! = 40320 manieren
W. Oele Combinatoriek
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Permutaties
Stel dat het aantal lades kleiner is dan het aantal letters, bijvoorbeeld: 8 letters 5 lades Indien het aantal lades even groot was geweest als het aantal letters, waren we snel klaar: 8! = 40320
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Permutaties
A B C D E F G H 8 letters in 8 kasten: 8! echter: We hebben slechts 5 lades! Oplossing: formule corrigeren: n! (n − k)!
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Permutaties
Algemeen: Men kan n letters op k posities plaatsen op n! (n − k)! verschillende manieren
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Permutaties
8 letters op 5 posities? antwoord: 8! n! = = 6720 (n − k)! (8 − 5)! Opmerking: de mogelijkheid abcde is ´e´en van de 6720 mogelijkheden. De mogelijkheid abced is eveneens ´e´en van de 6720 mogelijkheden.
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Volgorde
De mogelijkheid abcde is ´e´en van de 6720 mogelijkheden. De mogelijkheid abced is eveneens ´e´en van de 6720 mogelijkheden. Bovenstaande rangschikkingen worden blijkbaar als 2 verschillende gezien. De volgorde, waarin de letters in de kast geplaatst worden is dus van belang. abcde 6= abced 6= abdce 6= acbde 6= . . .
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Variaties
Combinaties
Stel dat we de volgorde, waarin letters in een kast geplaatst worden niet belangrijk vinden. Anders gezegd: abcde = abced = abdce = acbde = . . . Opnieuw moet nu de formule gecorrigeerd worden, deze keer voor het aantal permutaties van k letters: n! k!(n − k)!
W. Oele Combinatoriek
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
De binomiaalco¨effic¨ıent
n n! = k k!(n − k)! Voorbeeld: Op hoeveel verschillende manieren kunnen 8 letters in 5 lades geplaatst worden, ongeacht hun volgorde? Antwoord: 8 8! = 56 = 5 5!(8 − 5)!
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Voorbeeld
Voor een vliegreis hebben zich 12 personen ingeschreven. In het vliegtuig is slechts plaats voor 8 personen. Op hoeveel verschillende manieren kunnen we uit deze 12 personen er 8 kiezen?
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Voorbeeld
12 personen levert 12! permutaties Er slechts zijn 8 plaatsen beschikbaar dus delen we weg door (12 − 8)! De vraag wordt nu of de volgorde, waarin de personen in het vliegtuig plaats nemen er toe doet. . .
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Voorbeeld
Met volgorde: 12! = 19558400 (12 − 8)! Zonder volgorde: 12! = 495 8!(12 − 8)!
W. Oele Combinatoriek
Binomiaalco¨ effici¨ ent
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Teruglegging
In alle voorgaande gevallen werd iedere letter precies ´e´en keer in de kast geplaatst. Men noemt dat vraagstukken zonder teruglegging. Stel dat we een letter meerdere malen in verschillende lades mogen plaatsen, bijv: abcdd, aabce, enz. Dit wordt een vraagstuk met teruglegging genoemd. Algemene formule: nk
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Voorbeeld
5 letters in 5 lades: nk = 55 = 3125 manieren Pincode: 10 cijfers op 4 posities: 104 = 10.000
W. Oele Combinatoriek
Binomiaalco¨ effici¨ ent
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Variaties
Onvolledig overzicht
met volgorde zonder volgorde zonder teruglegging met teruglegging
W. Oele Combinatoriek
n! (n−k)! k
n
n! k!(n−k)!
??
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Variaties
Bij vraagstukken met teruglegging zonder volgorde geldt de volgende formule: (n − 1 + k)! n−1+k (n − 1 + k)! = = k!(n − 1 + k − k)! k!(n − 1)! k
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Voorbeeld:
Een snoepwinkel verkoopt 10 verschillende soorten snoep Een kind mag 3 snoepjes uitkiezen Op hoeveel manieren kan dat? Antwoord: n−1+k 12 12! = = = 220 k 3 3!9!
W. Oele Combinatoriek
Variaties
Permutaties
Combinaties
Binomiaalco¨ effici¨ ent
Overzicht combinatoriek
met volgorde zonder teruglegging met teruglegging
W. Oele Combinatoriek
n! (n−k)! k
n
zonder volgorde n n! = k!(n−k)! k (n−1+k)! n−1+k = k!(n−1)! k
Variaties
