Combinatoriek Cheatsheet

Cheatsheet Content

### Basisprincipes - **Productregel:** Als procedure A op $m$ manieren kan, en procedure B op $n$ manieren, dan kunnen beide procedures op $m \times n$ manieren. - **Somregel:** Als procedure A op $m$ manieren kan, en procedure B op $n$ manieren, en ze elkaar uitsluiten, dan kan één van beide procedures op $m + n$ manieren. #### Voorbeeld Productregel Een restaurant biedt 3 voorgerechten, 5 hoofdgerechten en 2 desserts. Hoeveel verschillende maaltijden (voorgerecht, hoofdgerecht, dessert) zijn er mogelijk? $3 \times 5 \times 2 = 30$ verschillende maaltijden. ### Permutaties Permutaties gaan over het aantal manieren om objecten in een specifieke volgorde te rangschikken. Volgorde is belangrijk. #### Permutaties van $n$ objecten Het aantal manieren om $n$ verschillende objecten te rangschikken is $n!$ (n faculteit). $$n! = n \times (n-1) \times \dots \times 2 \times 1$$ $0! = 1$ #### Voorbeeld Permutaties Hoeveel verschillende manieren zijn er om 4 boeken op een plank te plaatsen? $4! = 4 \times 3 \times 2 \times 1 = 24$ manieren. #### Permutaties van $k$ objecten uit $n$ Het aantal manieren om $k$ objecten te kiezen uit $n$ objecten, waarbij de volgorde telt: $$P(n, k) = \frac{n!}{(n-k)!}$$ #### Voorbeeld Permutaties uit $n$ Een wedstrijd heeft 10 deelnemers. Hoeveel manieren zijn er om de top 3 (goud, zilver, brons) te bepalen? $P(10, 3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720$ manieren. #### Permutaties met herhaling Het aantal unieke permutaties van $n$ objecten waarbij er $n_1$ van type 1 zijn, $n_2$ van type 2, ..., $n_k$ van type $k$: $$\frac{n!}{n_1! n_2! \dots n_k!}$$ #### Voorbeeld Permutaties met herhaling Hoeveel verschillende anagrammen kunnen er gemaakt worden van het woord "MISSISSIPPI"? Er zijn 11 letters in totaal. - M: 1 keer ($n_M=1$) - I: 4 keer ($n_I=4$) - S: 4 keer ($n_S=4$) - P: 2 keer ($n_P=2$) Aantal anagrammen: $\frac{11!}{1! 4! 4! 2!} = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = \frac{39,916,800}{1152} = 34,650$. ### Combinaties Combinaties gaan over het aantal manieren om objecten te kiezen zonder rekening te houden met de volgorde. Volgorde is niet belangrijk. #### Combinaties van $k$ objecten uit $n$ Het aantal manieren om $k$ objecten te kiezen uit $n$ objecten, waarbij de volgorde niet telt: $$\binom{n}{k} = C(n, k) = \frac{n!}{k!(n-k)!}$$ Dit wordt ook wel de binomiale coëfficiënt genoemd. #### Voorbeeld Combinaties uit $n$ Een groep van 15 studenten moet een comité van 3 leden kiezen. Hoeveel verschillende comités zijn er mogelijk? $\binom{15}{3} = \frac{15!}{3!(15-3)!} = \frac{15!}{3!12!} = \frac{15 \times 14 \times 13}{3 \times 2 \times 1} = 5 \times 7 \times 13 = 455$ comités. #### Combinaties met herhaling Het aantal manieren om $k$ objecten te kiezen uit $n$ soorten objecten, waarbij herhaling is toegestaan en de volgorde niet telt: $$\binom{n+k-1}{k}$$ #### Voorbeeld Combinaties met herhaling Je wilt 5 koekjes kopen in een winkel die 3 verschillende soorten koekjes verkoopt (chocolade, havermout, suiker). Hoeveel verschillende combinaties van 5 koekjes kun je kopen? Hier is $n=3$ (soorten koekjes) en $k=5$ (aantal koekjes dat je koopt). $\binom{3+5-1}{5} = \binom{7}{5} = \frac{7!}{5!(7-5)!} = \frac{7!}{5!2!} = \frac{7 \times 6}{2 \times 1} = 21$ combinaties. ### Binomiale Stelling De binomiale stelling beschrijft de algebraïsche expansie van machten van een binomiaal ($x+y$). $$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$$ #### Voorbeeld Binomiale Stelling Breid $(a+b)^3$ uit met de binomiale stelling. $$(a+b)^3 = \binom{3}{0}a^3b^0 + \binom{3}{1}a^2b^1 + \binom{3}{2}a^1b^2 + \binom{3}{3}a^0b^3$$ $$ = 1 \cdot a^3 \cdot 1 + 3 \cdot a^2 \cdot b + 3 \cdot a \cdot b^2 + 1 \cdot 1 \cdot b^3$$ $$ = a^3 + 3a^2b + 3ab^2 + b^3$$ ### Principe van Inclusie en Exclusie (PIE) Voor twee verzamelingen A en B: $$|A \cup B| = |A| + |B| - |A \cap B|$$ Voor drie verzamelingen A, B en C: $$|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$$ #### Voorbeeld PIE In een groep van 100 studenten volgen 40 studenten wiskunde, 30 studenten informatica en 10 studenten volgen beide. Hoeveel studenten volgen minstens één van de twee vakken? Laat W = wiskunde en I = informatica. $|W \cup I| = |W| + |I| - |W \cap I| = 40 + 30 - 10 = 60$ studenten.