Discrete Wiskunde
Basis 2
Genererende functies 3
Recurrente betrekkingen 6
Inclusie-Exclusie 9
Pólya theorie 12
Dynamisch programmeren 16
Algoritmen 20
,Basis
Productregel |Z| = |X| * |Y|
- Als gebeurtenis Z bestaat uit combinatie van delen X en Y en iedere mogelijkheid van X
kan worden gecombineerd met iedere mogelijkheid uit Y
- Bijvoorbeeld, het aantal verschillende pizza’s als je de keuze hebt uit 9 ingrediënten,
waarvan je er minstens 2 wilt is 29 - 10 (eerste ingrediënt 2 mogelijkheden, tweede
ingrediënt weer 2 mogelijkheden, etc.)
- OR
Somregel |Z| = |X| + |Y|
- Als Z kan worden opgesplitst in disjunce X en Y
- Bijvoorbeeld, het aantal pizza’s als je kunt kiezen uit 9 ingrediënten, maar je niet zowel
broccoli als ansjovis en niet zowel paprika als ansjovis kan nemen en er geldt dat je
sowieso ham neemt als je ook paprika neemt
- Splits oplossingsruimte op in deelverzamelingen, dus een deel pizza’s met
ansjovis en een deel zonder ansjovis
- Bij het deel met ansjovis heb je nog keuze uit 6 ingrediënten (ansjovis is al
gebruikt, broccoli en paprika kunnen niet), dus 26
- Bij deel zonder ansjovis splits je weer op in twee subsets wel en niet paprika
- In totaal geeft dit 4 * 26 = 256 mogelijkheden
- AND
Permutaties Beeldt ieder element af op willekeurig ander element, waarbij elk element precies
één keer wordt gebruikt
- Aantal mogelijke permutaties van n elementen = n!
- Overigens, n! = (n-1)! * n
- Of als een graaf: voor alle i, maak een edge van dit punt naar
punt 𝜋(i)
- Het aantal verschillende cykels in deze graaf is (n - 1)!, omdat je elk element met
(n - 1) elementen kan koppelen
- Stel je wilt het aantal mogelijkheden voor drietallen van letters voor initialen, dan kunnen
er ook rijtjes voorkomen met meerdere keren dezelfde letter, dus dan wordt het 263
P(succes) = aant succes / aant mogelijkheden
- Maar geldt alleen als iedere mogelijkheid dezelfde kans heeft!
P(n,r) = n!/(n-r)! -> volgorde, geen duplicates
Combinaties Aantal mogelijkheden om r elementen te kiezen uit een verzameling van n
elementen, waarbij de volgorde niet uitmaakt: C(n,r) = (n r) = n! / (n-r)! * r! = (n n-r)
- Bijvoorbeeld, voor een pizza waar je kan kiezen uit n ingrediënten en je k ingrediënten
op de pizza wilt, is het aantal mogelijkheden C(n,k) (ervan uitgaande dat volgorde niet
uitmaakt)
Standaardproblemen
- Chocolaatjes (trekken met teruglegging): je wilt een doos vullen met r chocolaatjes,
waarbij je kunt kiezen uit m smaken
- Er zijn C(n+m-1,m-1) mogelijkheden om de doos te vullen
- Ballen en dozen herkenbaar, dozen mogen leeg zijn: n ballen in k dozen, kn
mogelijkheden
, - Ballen onherkenbaar, dozen herkenbaar, dozen mogen leeg: chocolaatjes, dus
C(n+k-1,k-1)
- Ballen onherkenbaar, dozen herkenbaar, dozen mogen niet leeg: als boven, maar eerst
chocolaatje in elke doos stoppen, dus k minder opties voor de streepjes, C(n-1,k-1)
- Ballen herkenbaar, dozen onherkenbaar, dozen mogen niet leeg: Stirling getal van de
𝑘
1 𝑖 𝑛
tweede soort, 𝑆(𝑛, 𝑘) = 𝑘!
∑ (− 1) 𝐶(𝑘, 𝑖)(𝑘 − 𝑖)
𝑖=0
- Ballen herkenbaar, dozen onherkenbaar, dozen mogen leeg: splits probleem op basis
van aantal niet-lege dozen l, dan moet je de ballen verdelen over de l dozen, dus S(n,l),
wat in totaal geeft S(n,1) + S(n,2) + … + S(n,k)
- Ballen herkenbaar, dozen herkenbaar, dozen mogen niet leeg: voor elke oplossing
hierboven zijn er k! verschillende manieren om de dozen te nummeren van 1 tot k, dus
𝑘
𝑖 𝑛
𝑘! 𝑆(𝑛, 𝑘) = ∑ (− 1) 𝐶(𝑘, 𝑖)(𝑘 − 1)
𝑖=0
- Herkenbaar verschillende permutaties: een verzameling van n voorwerpen, verdeeld in
k groepen van identieke voorwerpen, dus van type j heb je nj stuks (j=1, …,k)
- Op hoeveel manieren kun je de n voorwerpen op een rij leggen zodat je een
herkenbaar verschillende rij krijgt?
- In totaal zijn er n! manieren om de hele verzameling te permuteren, maar voor
elke groep identieke voorwerpen zijn er nj! manieren om ze te permuteren
zonder het verschil te zien, dus daar moeten we de n! door delen en dat doen we
𝑛!
voor elke groep: 𝑛1! · 𝑛2! · ... · 𝑛𝑗!
- Als nu alle voorwerpen in groep 1 identiek worden zijn er voor elke
eerdere mogelijkheid n1! verschillende nieuwe mogelijkheden, dus
𝑛! 𝑛!
𝑛1! · 𝑛1! · 𝑛2! · ... · 𝑛𝑗!
= 𝑛2! · ... · 𝑛𝑗!
- Dit is een multinomiaal coëfficiënt ↙
- Bijvoorbeeld, bij een full house met drie 1’en en twee 2’en heb je twee groepen
van identieke dobbelstenen, dus C(5,2) mogelijkheden om zo’n full house te
gooien en er zijn 6 * 5 = 30 combinaties van x and y om een full house te gooien
met drie x’en en twee y’en, dus 30 * C(5,2) = 300 mogelijkheden om full house te
gooien met 5 dobbelstenen
Multinomiaal coëfficiënten
Genererende functies
Belangrijke machtreeksen
