Samenvatting van alle stof die behandeld wordt bij het vak Discrete Wiskunde (INFOB3DW), zowel in het eerste deel als het tweede deel van het vak. Inclusief een groot aantal voorbeelden van dynamisch programmeren.
,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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
√ Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, Bancontact of creditcard voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper Suniht. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €7,98. Je zit daarna nergens aan vast.
