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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Suniht. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.55. You're not tied to anything after your purchase.
