KU Leuven
Kansrekenen [B-KUL-G0W66A] Notities
Tom Sydney Kerckhove
Gestart 8 februari 2015 Gecompileerd 9 februari 2015
Docent: Prof. Tim Verdonck
Inhoudsopgave 1 Combinatoriek 1.1 Variaties . . . . . . . . . . . . . . . . 1.2 Permutaties . . . . . . . . . . . . . . 1.3 Combinaties . . . . . . . . . . . . . . 1.3.1 Binomium van Newton . . . . 1.3.2 Multinomiale ontwikkeling . 1.3.3 Het aantal deelverzamelingen
. . . . . .
2 2 2 3 4 4 4
2 Voorbeelden 2.1 Combinatoriek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 5
. . . . . .
. . . . . .
1
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Hoofdstuk 1 Combinatoriek TODO: definieer een n-tal? en een combinatie met eigen eerst zonder de context van combinatoriek?
1.1
Variaties
Definitie 1.1. Een variatie van p ∈ N verschillende elementen uit n ∈ N elementen (met p ≤ n) is een geordend p-tal van verschillende elementen gekozen uit een gegeven verzameling van n elementen. p
Stelling 1.2. Het aantal variaties van p elementen uit n is gelijk aan Vv . Vpn
=
p−1 Y
(n − p)
i=0
Bewijs. We moeten een rij van lengte p vormen met n elementen. Voor de eerste plaats is er vrije keuze, dus n elementen. Voor de tweede plaats is er keuze uit de overgebleven n − 1 elementen. Voor Qp−1 de i-de plaats is er dan keuze uit de overgebleven n − 1 elementen. er zijn dus i=0 (n −p) mogelijke manieren om p elementen te kiezen uit n zonder herhalingen. Eigenschap 1.3. Vn0 = 1
en Vnn = n!
EXTRA: bewijs
Definitie 1.4. Een herhalingsvariatie van p ∈ N elementen uit n ∈ N elementen is een geordend p-tal van verschillende elementen gekozen uit een gegeven verzameling van n elementen. p
Stelling 1.5. Het aantal herhalingsvariaties van p elementen uit n is gelijk aan V v . n
V p = np Bewijs. Voor elk element van het p-tal is er keuze uit n elementen. Er zijn dus np mogelijke herhalingsvariaties van p elementen uit n.
1.2
Permutaties 2
3
HOOFDSTUK 1. COMBINATORIEK
Definitie 1.6. Een permutatie van n ∈ N elementen is een variatie van n uit n elementen. Opmerking 1.7. Soms wordt een permutatie ook beschreven als een bijectie van een eindige verzameling naar zichzelf. Deze noties komen overeen in de zin dat de variatie beschreven in bovenstaande definitie een beschrijving geeft van de bijectie in de andere definitie.
Definitie 1.8. Een herhalingspermutatie van n ∈ N elementen waarvan pi elementen telkens P tot soort i behoren (met ri=1 pi = n) is een geordend n-tal van elementen waarvan de i-de pi elementen telkens tot soort i behoren. p1 ,p2 ,...,pr
Stelling 1.9. Het aantal herhalingspermutaties van p elementen uit n is gelijk aan P n ! n n! p1 ,p2 ,...,pr = Pn = Qr p1 p2 · · · pr i=1 pi
.
EXTRA: bewijs
1.3
Combinaties
Definitie 1.10. Een combinatie van p elementen uit n is een deelverzameling van die n elementen. Opmerking 1.11. Bij een combinatie speelt de volgorde van de elementen dus geen rol. p
Stelling 1.12. Het aantal combinaties van p elementen uit n is Cn . ! n n! p Cn = = p p!(n − p)! p
Bewijs. Het aantal variaties Vn van p elemenen uit n, (waar de volgorde wel een rol speelt) is teveel. Het is zelfs precies Pp keer teveel want we kunnen de elementen in het n tal nog permuteren. p Cn
p
n! V = n = Pp p!(n − p)!
Opmerking 1.13. Eigenschap 1.14.
n p
lezen we als “n kies p”. Cnn = Cn0 = 1
EXTRA: bewijs
Eigenschap 1.15.
p
n−p
Cn = Cn EXTRA: bewijs
4
HOOFDSTUK 1. COMBINATORIEK Eigenschap 1.16. De formule van Pascal. p+1
p
Cn + Cn
p+1
= Cn+1
EXTRA: bewijs
Definitie 1.17. Een herhalingscombinatie van p elementen uit n is een ongeordend p-tal van elementen waarbij herhaling mogelijk is. Opmerking 1.18. De notie van een “ongeordend p-tal” is ietwat vaag. In feite hebben we nood aan een structuur die geen orde oplegt en herhaling van elementen toelaat. Noch een geordend p-tal, noch een verzameling is hiervoor dus bruikbaar. p
Stelling 1.19. Het aantal herhalingscombinaties van p elementen uit n is C n . ! n +p −1 p p C n = Cn+p−1 = p
1.3.1
Binomium van Newton
Stelling 1.20. Het binomium van Newton. n
(a + b) =
n X i=0
! n n−i i = a b i
EXTRA: bewijs
Definitie 1.21. De co¨efficienten
1.3.2
n i
worden daarom ook de binomiaalco¨efficienten genoemd.
Multinomiale ontwikkeling
Stelling 1.22. De multinomiale ontwikkeling. k X
n
!Y k X n * + = * xini + Pk , i=1 , n 1 n 2 · · · nk i=1 i=1 n i =n
Definitie 1.23. De co¨efficienten genoemd.
1.3.3
n n 1 n 2 ··· nk
worden daarom ook de multinomiaalco¨efficienten
Het aantal deelverzamelingen
Stelling 1.24. Het aantal deelverzamelingen |P (V )| van een verzameling V is 2|V | . Bewijs. Het aantal deelverzamelingen van i elementen van V is C i|V | . Het totaal aantal deelverzaP|V | i melingen is dan i=0 C |V | . Gebruik nu het binomium van newton met a = b = 1 om het gezochte resultaat te bekomen. ! X ! |V | |V | |V | X X |V | |V | (|V |−i) i i C |V | = = 1 1 = (1 + 1) |V | = 2|V | i i i=0 i=0 i=0
Hoofdstuk 2 Voorbeelden 2.1
Combinatoriek
Variaties Voorbeeld 2.1. Het aantal manieren om 4 studenten uit 10 aan te duiden om 4 verschillende oefeningen te maken is V104 .
Herhalingsvariaties 2
Voorbeeld 2.2. Het aantal verschillende bytes is V 8 .
Permutaties Voorbeeld 2.3. Het aantal manieren om 5 personen aan een ronde tafel te zetten is P 5 .
Herhalingspermutaties EXTRA: voorbeeld
Combinaties 4 . Voorbeeld 2.4. Het aantal manieren om een groepje van 4 studenten uit 10 aan te duiden is C 10
Voorbeeld 2.5. Het aantal manieren om twee teams van 6 uit 12 spelers te kiezen is C126 /2. Voorbeeld 2.6. Het aantal manieren om 5 keer hetzelfde aantal ogen te gooien met 5 dobbelstenen is C 61 . Voorbeeld 2.7. Het aantal manieren om 4 keer hetzelfde aantal ogen te gooien met 5 dobbelstenen is C 61 · C 51 .
Herhalingscombinaties EXTRA: voorbeeld
5
Bibliografie
6
Todo list TODO: definieer een n-tal? en een combinatie met eigen eerst zonder de context van combinatoriek? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EXTRA: bewijs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EXTRA: bewijs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EXTRA: bewijs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EXTRA: bewijs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EXTRA: bewijs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EXTRA: bewijs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EXTRA: voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EXTRA: voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2 2 3 3 3 4 4 5 5
