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
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur Suniht. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €7,98. Vous n'êtes lié à rien après votre achat.
