Wiskunde bovenbouw · Grades 10–12

27Combinatoriek en tellen

Combinatoriek is de kunst van tellen zonder opsommen. Haar twee elementaire principes — tel de groottes van disjuncte alternatieven op, vermenigvuldig de aantallen onafhankelijke keuzes — volstaan om de rijen, permutaties en deelverzamelingen van een eindige verzameling te tellen, en culmineren in de binomiaalstelling.

27.1 De twee telprincipes

We schrijven $\abs{E}$ voor het aantal elementen (de kardinaliteit) van een eindige verzameling $E$ .

Propositie 27.1 (Optelprincipe)

Als een eindige verzameling $E$ is opgedeeld in deelverzamelingen $A_1, \dots, A_k$ (paarsgewijs disjunct, met vereniging $E$ ), dan

\abs{E} = \abs{A_1} + \abs{A_2} + \dots + \abs{A_k}.

Propositie 27.2 (Vermenigvuldigingsprincipe)

Als een object wordt opgebouwd door een opeenvolging van $k$ keuzes, met $n_1$ opties voor de eerste keuze en, ongeacht de vorige keuzes, $n_i$ opties voor de $i$ -de, dan is het aantal opgebouwde objecten $n_1 \times n_2 \times \dots \times n_k$ .

Bewijs. Beide uitspraken worden bewezen door inductie op $k$ ; het geval $k = 2$ van de tweede komt neer op het tellen van een rechthoekig rooster per rij. ∎

Voorbeeld 27.3

Een restaurant biedt $4$ voorgerechten, $6$ hoofdgerechten, $3$ desserts: $4 \times 6 \times 3 = 72$ verschillende driemenu’s.

27.2 Tuples, permutaties, factorialen

Definitie 27.4 ( $k$ -tupels)

Een $k$ -tupel van een verzameling $E$ is een geordende lijst $(x_1, \dots, x_k)$ van elementen van $E$ , herhalingen toegestaan. Een $k$ -tupel van verschillende elementen is een arrangement van $k$ elementen van $E$ .

Propositie 27.5

Laat $\abs E = n$ . Het aantal $k$ -tupels van $E$ is $n^k$ . Het aantal arrangementen van $k$ elementen van $E$ ( $0 \leq k \leq n$ ) is

n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!},

waar $n! = 1 \times 2 \times \dots \times n$ (en $0! = 1$ ) de faculteit van $n$ is.

Bewijs. Vermenigvuldigingsprincipe: voor een $k$ -tupel zijn er $n$ opties bij elk van de $k$ stappen; voor een arrangement, $n$ opties voor $x_1$ , daarna $n - 1$ voor $x_2$ (één element is gebruikt), …, $n - k + 1$ voor $x_k$ . ∎

Definitie 27.6 (Permutatie)

Een permutatie van $E$ is een arrangement van alle $n$ elementen van $E$ : een ordening van $E$ . Volgens Propositie 27.5 (geval $k = n$ ) is het aantal permutaties van een $n$ -elementenverzameling $n!$ .

Voorbeeld 27.7

Vijf hardlopers kunnen een race in $5! = 120$ verschillende volgordes finishen. Het aantal mogelijke podia (eerste drie plaatsen) is $5 \times 4 \times 3 = 60$ .

27.3 Combinaties en binomiaalcoëfficiënten

Definitie 27.8 (Combinaties)

Een combinatie van $k$ elementen van $E$ is een deelverzameling van $E$ met $k$ elementen (geen volgorde, geen herhaling). Hun aantal wordt geschreven $\dbinom{n}{k}$ , gelezen “ $n$ over $k$ ” of “ $n$ kies $k$ ”.

Stelling 27.9

Voor $0 \leq k \leq n$ :

\binom{n}{k} = \frac{n!}{k!\,(n-k)!} .

Bewijs. Tel de arrangementen van $k$ elementen van $E$ op twee manieren. Direct: $\frac{n!}{(n-k)!}$ . Alternatief: kies eerst de onderliggende deelverzameling ( $\binom nk$ manieren), orden haar daarna ( $k!$ manieren); het vermenigvuldigingsprincipe geeft $\binom{n}{k}\,k!$ . Gelijkstellen: $\binom nk = \frac{n!}{k!(n-k)!}$ . ∎

Propositie 27.10 (Basisidentiteiten)

Voor $0 \leq k \leq n$ :

\binom{n}{0} = \binom{n}{n} = 1, \qquad \binom{n}{1} = n, \qquad \binom{n}{k} = \binom{n}{n-k},

en de regel van Pascal: voor $1 \leq k \leq n-1$ ,

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.

Bewijs. De symmetrie $\binom nk = \binom{n}{n-k}$ geldt omdat complementen $k$ -elementen-deelverzamelingen één-op-één matchen met $(n-k)$ -elementen-deelverzamelingen. Voor de regel van Pascal: fixeer een element $a \in E$ en sorteer de $k$ -elementen-deelverzamelingen in die die $a$ bevatten — verkregen door $a$ toe te voegen aan een $(k-1)$ -elementen-deelverzameling van $E \setminus \{a\}$ , waarvan er $\binom{n-1}{k-1}$ zijn — en die die $a$ vermijden, die de $k$ -elementen-deelverzamelingen van $E \setminus \{a\}$ zijn, in aantal $\binom{n-1}{k}$ . Besluit met het optelprincipe. ∎

De regel van Pascal genereert de coëfficiënten rij voor rij — de driehoek van Pascal: elke ingang is de som van de twee erboven.

Driehoek van Pascal, rijen n = 0 tot 5: de regel van Pascal 41 + 42 = 52 in actie. — Driehoek van Pascal, rijen $n = 0$ tot $5$ : de regel van Pascal $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ in actie.

Stelling 27.11 (Binomiaalstelling)

Voor alle $a, b \in \R$ (of $\C$ ) en $n \in \N$ :

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k}\, a^{k}\, b^{\,n-k} .

Bewijs. Ontwikkel het product $(a+b)(a+b)\cdots(a+b)$ ( $n$ factoren): elke term van de ontwikkeling kiest $a$ of $b$ in elke factor, en produceert $a^k b^{n-k}$ waar $k$ het aantal factoren is die $a$ leveren. Het aantal manieren om deze $k$ factoren onder $n$ te kiezen is $\binom nk$ , dat daarom de coëfficiënt van $a^k b^{n-k}$ is. ∎

Gevolg 27.12

$\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$ en $\displaystyle\sum_{k=0}^{n} (-1)^k\binom{n}{k} = 0$ ( $n \geq 1$ ).

Bewijs. Neem $a = b = 1$ , daarna $a = -1$ , $b = 1$ in de binomiaalstelling. De eerste identiteit heeft ook een directe betekenis: een $n$ -elementenverzameling heeft $2^n$ deelverzamelingen (elk element is in of uit: vermenigvuldigingsprincipe), gesorteerd naar grootte. ∎

Methode 27.13 (Het juiste model kiezen)

Voor het tellen: beantwoord twee vragen: speelt volgorde een rol? en zijn herhalingen toegestaan?

	volgorde telt	volgorde irrelevant
herhalingen toegestaan	$n^k$ (tupels)	(universiteit)
geen herhalingen	$\frac{n!}{(n-k)!}$ (arrangementen)	$\binom nk$ (deelverz.)

Ballen trekken uit een urn: met teruglegging, in volgorde $\to$ tupels; zonder teruglegging, in volgorde $\to$ arrangementen; een handvol in één keer $\to$ deelverzamelingen.

27.4 Oefeningen

Oefening 27.1 ★

Een nummerplaat bestaat uit $2$ letters (A–Z), dan $3$ cijfers, dan $2$ letters. Hoeveel platen zijn mogelijk? Hoeveel hebben geen herhaald teken?

Oplossing

Oplossing van Oefening 27.1.

Vermenigvuldigingsprincipe: $26^2 \times 10^3 \times 26^2 = 26^4 \times 10^3 = 456\,976\,000$ .

Zonder herhaald teken moeten de vier letters verschillend zijn ( $26 \times 25 \times 24 \times 23$ manieren, letterposities in volgorde vullen) en de drie cijfers verschillend ( $10 \times 9 \times 8$ ):

26 \times 25 \times 24 \times 23 \times 10 \times 9 \times 8 = 358\,800 \times 720 = 258\,336\,000 .

Oefening 27.2 ★

Bereken $\dbinom{8}{3}$ , $\dbinom{10}{8}$ , en vereenvoudig $\dfrac{\binom{n}{2}}{\binom{n+1}{2}}$ .

Oplossing

Oplossing van Oefening 27.2.

$\dbinom83 = \dfrac{8 \times 7 \times 6}{3!} = 56$ ; $\dbinom{10}{8} = \dbinom{10}{2} = \dfrac{10 \times 9}{2} = 45$ ;

\frac{\binom n2}{\binom{n+1}2} = \frac{n(n-1)/2}{(n+1)n/2} = \frac{n-1}{n+1}.

Oefening 27.3 ★

In een klas van $30$ leerlingen moet men een commissie van $4$ leerlingen kiezen, daarna een voorzitter en een penningmeester binnen de commissie (één persoon kan niet beide functies bekleden). Hoeveel uitkomsten zijn mogelijk?

Oplossing

Oplossing van Oefening 27.3.

Kies de commissie: $\binom{30}{4}$ manieren. Kies daarna voorzitter en penningmeester onder de 4, in volgorde: $4 \times 3 = 12$ manieren. Totaal

\binom{30}{4} \times 12 = 27\,405 \times 12 = 328\,860 .

Oefening 27.4 ★

Ontwikkel $(x + 2)^5$ en $(1 - x)^6$ met de binomiaalstelling. Wat is de coëfficiënt van $x^3$ in $(2x + 3)^7$ ?

Oplossing

Oplossing van Oefening 27.4.

(x+2)^5 = x^5 + 10x^4 + 40x^3 + 80x^2 + 80x + 32 ,

(1-x)^6 = 1 - 6x + 15x^2 - 20x^3 + 15x^4 - 6x^5 + x^6 .

In $(2x+3)^7$ is de term in $x^3$ $\binom{7}{3}(2x)^3\,3^4 = 35 \times 8 \times 81\, x^3$ : de coëfficiënt is $22\,680$ .

Oefening 27.5 ★★

Een standaard pokerhand bestaat uit $5$ kaarten uit een speelkaartendeck van $52$ .

Hoeveel handen zijn er?
Hoeveel handen bevatten precies één aas? Minstens één aas?
Hoeveel handen zijn “full houses” (drie kaarten van één rang, twee van een andere)?

Oplossing

Oplossing van Oefening 27.5.

1. $\dbinom{52}{5} = 2\,598\,960$ .

2. Precies één aas: kies die ( $4$ manieren) en vul aan met $4$ niet-azen: $4 \times \binom{48}{4} = 4 \times 194\,580 = 778\,320$ . Minstens één aas: complementair tellen, $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$ .

3. Kies de waarde van de three-of-a-kind ( $13$ ), haar kleuren ( $\binom43 = 4$ ), de waarde van het paar ( $12$ over), haar kleuren ( $\binom42 = 6$ ): $13 \times 4 \times 12 \times 6 = 3744$ .

Oefening 27.6 ★★

Hoeveel anagrammen (herschikkingen van letters, zinvol of niet) heeft het woord MATH? Het woord BANANA? (Hint voor BANANA: plaats eerst de drie A’s.)

Oplossing

Oplossing van Oefening 27.6.

MATH heeft 4 verschillende letters: $4! = 24$ anagrammen.

BANANA heeft 6 letters: drie A, twee N, één B. Kies de posities van de A ( $\binom63$ ), daarna de N onder de rest ( $\binom32$ ), de B neemt de laatste plaats:

\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60 .

(Equivalent $\frac{6!}{3!\,2!\,1!} = 60$ .)

Oefening 27.7 ★★

Bewijs de identiteit $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ ( $1 \leq k \leq n$ ) op twee manieren: met de factoriale formule, en door op twee manieren de paren (commissie van $k$ personen, haar voorzitter) te tellen gekozen uit $n$ personen.

Oplossing

Oplossing van Oefening 27.7.

Algebraïsch:

k\binom nk = \frac{k\,n!}{k!(n-k)!} = \frac{n!}{(k-1)!\,(n-k)!} = n\,\frac{(n-1)!}{(k-1)!\bigl((n-1)-(k-1)\bigr)!} = n\binom{n-1}{k-1}.

Door dubbel tellen: tel de paren (commissie van $k$ , voorzitter daarin). Of kies de commissie ( $\binom nk$ ) dan haar voorzitter ( $k$ ): $k\binom nk$ paren. Of kies eerst de voorzitter ( $n$ opties) dan de $k-1$ andere leden onder de $n-1$ rest: $n\binom{n-1}{k-1}$ paren.

Oefening 27.8 ★★

Een pad in het vlak gaat van $(0,0)$ naar $(m, n)$ met eenheidstappen Oost of Noord. Toon dat het aantal zulke paden $\dbinom{m+n}{m}$ is.

Oplossing

Oplossing van Oefening 27.8.

Een pad bestaat uit precies $m + n$ stappen, waarvan $m$ Oost en $n$ Noord zijn; het is volledig bepaald door de verzameling momenten (onder de $m+n$ ) waarop men oostwaarts gaat. Er zijn $\binom{m+n}{m}$ zulke keuzes.

Oefening 27.9 ★★★

Bewijs de identiteit van Vandermonde: voor $0 \leq k \leq m + n$ ,

\binom{m+n}{k} = \sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j},

door de $k$ -elementen-deelverzamelingen te tellen van een verzameling opgedeeld in een groep van $m$ en een groep van $n$ . Leid af dat $\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{\!2} = \binom{2n}{n}$ .

Oplossing

Oplossing van Oefening 27.9.

Splits een verzameling van $m + n$ personen in een groep $A$ van $m$ en een groep $B$ van $n$ . Een deelverzameling van $k$ elementen bevat een zeker aantal $j$ leden van $A$ ( $0 \leq j \leq k$ ) en $k - j$ leden van $B$ ; voor vaste $j$ zijn er $\binom mj \binom{n}{k-j}$ zulke delen, en het optelprincipe over $j$ geeft de identiteit van Vandermonde.

Met $m = n = k$ :

\binom{2n}{n} = \sum_{j=0}^n \binom nj \binom{n}{n-j} = \sum_{j=0}^n \binom nj^{2},

met de symmetrie $\binom{n}{n-j} = \binom nj$ .

Oefening 27.10 ★★★

Met de binomiaalstelling, toon dat voor alle $n \geq 1$ ,

\sum_{k=1}^{n} k \binom{n}{k} = n\,2^{n-1}.

(Hint: differentieer ofwel $(1+x)^n$ , of gebruik Oefening 27.7.)

Oplossing

Oplossing van Oefening 27.10.

Via Oefening 27.7:

\sum_{k=1}^n k\binom nk = \sum_{k=1}^n n\binom{n-1}{k-1} = n\sum_{j=0}^{n-1}\binom{n-1}{j} = n\,2^{n-1},

volgens Gevolg 27.12. Via differentiatie: differentiëren van $(1+x)^n = \sum_k \binom nk x^k$ geeft $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$ ; evalueer in $x = 1$ .