Wiskunde bovenbouw · Grades 10–12

27Combinatoriek en tellen

De combinatoriek is de kunst van het tellen zonder op te sommen. Haar twee elementaire principes — tel de omvang van disjuncte alternatieven op, vermenigvuldig de aantallen onafhankelijke keuzen — volstaan om de variaties, de permutaties en de deelverzamelingen van een eindige verzameling te tellen, en monden uit in het binomium van Newton.

27.1 De twee telprincipes

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

Propositie 27.1 (Somprincipe)

Wordt een eindige verzameling $E$ verdeeld in deelverzamelingen $A_1, \dots, A_k$ (paarsgewijs disjunct, met vereniging $E$ ), dan geldt

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

Propositie 27.2 (Productprincipe)

Wordt een object opgebouwd met een opeenvolging van $k$ keuzen, met $n_1$ mogelijkheden voor de eerste keuze en, wat de vorige keuzen ook waren, $n_i$ mogelijkheden voor de $i$ -de, dan is het aantal gebouwde objecten gelijk aan $n_1 \times n_2 \times \dots \times n_k$ .

Bewijs. Beide uitspraken bewijs je met inductie op $k$ ; het geval $k = 2$ van de tweede komt neer op een rechthoekige tabel rij per rij tellen. ∎

Voorbeeld 27.3

Een restaurant biedt 4 voorgerechten, 6 hoofdgerechten en 3 nagerechten: $4 \times 6 \times 3 = 72$ verschillende driegangenmenu’s.

27.2 $k$ -tallen, permutaties, faculteiten

Definitie 27.4 ( $k$ -tallen)

Een $k$ -tal van een verzameling $E$ is een geordende lijst $(x_1, \dots, x_k)$ van elementen van $E$ , met herhalingen toegestaan. Een $k$ -tal van verschillende elementen heet een variatie van $k$ elementen van $E$ .

Propositie 27.5

Zij $\abs E = n$ . Het aantal $k$ -tallen van $E$ is $n^k$ . Het aantal variaties van $k$ elementen van $E$ ( $0 \leq k \leq n$ ) is

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

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

Bewijs. Productprincipe: voor een $k$ -tal zijn er $n$ mogelijkheden bij elk van de $k$ stappen; voor een variatie zijn er $n$ mogelijkheden voor $x_1$ , daarna $n - 1$ voor $x_2$ (één element is opgebruikt), …, en $n - k + 1$ voor $x_k$ . ∎

Definitie 27.6 (Permutatie)

Een permutatie van $E$ is een variatie van alle $n$ elementen van $E$ : een rangschikking van $E$ . Volgens Propositie 27.5 (het geval $k = n$ ) is het aantal permutaties van een verzameling met $n$ elementen gelijk aan $n!$ .

Voorbeeld 27.7

Vijf lopers kunnen een wedstrijd in $5! = 120$ verschillende volgordes beëindigen. Het aantal mogelijke podia (de 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 (zonder volgorde, zonder herhaling). Hun aantal wordt $\dbinom{n}{k}$ geschreven en gelezen als “ $n$ boven $k$ ”.

Stelling 27.9

Voor $0 \leq k \leq n$ geldt

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

Bewijs. Tel de variaties van $k$ elementen van $E$ op twee manieren. Rechtstreeks: $\frac{n!}{(n-k)!}$ . Anders: kies eerst de onderliggende deelverzameling ( $\binom nk$ manieren) en rangschik ze daarna ( $k!$ manieren); het productprincipe geeft $\binom{n}{k}\,k!$ . Gelijkstellen levert $\binom nk = \frac{n!}{k!(n-k)!}$ . ∎

Propositie 27.10 (Basisidentiteiten)

Voor $0 \leq k \leq n$ geldt

\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 het complement nemen de deelverzamelingen met $k$ elementen één op één koppelt aan die met $n-k$ elementen. Voor de regel van Pascal kies je een element $a \in E$ vast en sorteer je de deelverzamelingen met $k$ elementen in die welke $a$ bevatten — verkregen door $a$ toe te voegen aan een deelverzameling met $k-1$ elementen van $E \setminus \{a\}$ , en daarvan zijn er $\binom{n-1}{k-1}$ — en die welke $a$ mijden, en dat zijn de deelverzamelingen met $k$ elementen van $E \setminus \{a\}$ , dus $\binom{n-1}{k}$ stuks. Besluit met het somprincipe. ∎

De regel van Pascal brengt de coëfficiënten rij per rij voort — de driehoek van Pascal: elk getal is de som van de twee erboven.

De driehoek van Pascal, rijen n = 0 tot 5: de regel van Pascal 41 + 42 = 52 aan het werk. — De driehoek van Pascal, rijen $n = 0$ tot $5$ : de regel van Pascal $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ aan het werk.

Stelling 27.11 (Binomium van Newton)

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

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

Bewijs. Werk het product $(a+b)(a+b)\cdots(a+b)$ ( $n$ factoren) uit: elke term van de uitwerking kiest in elke factor $a$ of $b$ , en levert $a^k b^{n-k}$ op, waarbij $k$ het aantal factoren is dat $a$ bijdraagt. Het aantal manieren om die $k$ factoren uit $n$ te kiezen is $\binom nk$ , en dat is dus de coëfficiënt van $a^k b^{n-k}$ . ∎

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$ , en daarna $a = -1$ , $b = 1$ in het binomium van Newton. De eerste identiteit heeft ook een rechtstreekse betekenis: een verzameling met $n$ elementen heeft $2^n$ deelverzamelingen (elk element zit erin of niet: productprincipe), gesorteerd naar omvang. ∎

Methode 27.13 (Het juiste model kiezen)

Beantwoord vóór je telt twee vragen: doet de volgorde ertoe? en zijn herhalingen toegestaan?

	volgorde telt	volgorde telt niet
herhaling toegestaan	$n^k$ ( $k$ -tallen)	(universiteit)
geen herhaling	$\frac{n!}{(n-k)!}$ (variaties)	$\binom nk$ (deelverzamelingen)

Ballen uit een urne trekken: met teruglegging, in volgorde $\to$ $k$ -tallen; zonder teruglegging, in volgorde $\to$ variaties; een handvol in één greep $\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 er mogelijk? Hoeveel ervan hebben geen enkel herhaald teken?

Oplossing

Oplossing van Oefening 27.1.

Productprincipe: $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, door de letterplaatsen in volgorde in te vullen) en de drie cijfers ook ( $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}$ en $\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 een comité van 4 leerlingen verkozen worden, en daarna binnen dat comité een voorzitter en een penningmeester (één persoon kan niet beide ambten bekleden). Hoeveel uitkomsten zijn er mogelijk?

Oplossing

Oplossing van Oefening 27.3.

Kies het comité: $\binom{30}{4}$ manieren. Kies daarna de voorzitter en de penningmeester uit de 4, in volgorde: $4 \times 3 = 12$ manieren. In totaal

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

Oefening 27.4 ★

Werk $(x + 2)^5$ en $(1 - x)^6$ uit met het binomium van Newton. 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$ gelijk aan $\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 pokerhand bestaat uit 5 kaarten uit een spel van 52 kaarten.

Hoeveel handen zijn er?
Hoeveel handen bevatten precies één aas? En minstens één aas?
Hoeveel handen zijn een “full house” (drie kaarten van één waarde en twee van een andere)?

Oplossing

Oplossing van Oefening 27.5.

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

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

3. Kies de waarde van het drietal ( $13$ ), zijn kleuren ( $\binom43 = 4$ ), de waarde van het paar ( $12$ resterende), zijn kleuren ( $\binom42 = 6$ ): $13 \times 4 \times 12 \times 6 = 3744$ .

Oefening 27.6 ★★

Hoeveel anagrammen (herschikkingen van de letters, met of zonder betekenis) heeft het woord GETAL? En het woord BANANA? (Tip voor BANANA: plaats eerst de drie A’s.)

Oplossing

Oplossing van Oefening 27.6.

GETAL heeft 5 verschillende letters: $5! = 120$ anagrammen.

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

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

(Even goed: $\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 formule met faculteiten, en door de paren (comité van $k$ personen, zijn voorzitter), gekozen uit $n$ mensen, op twee manieren te tellen.

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}.

Met dubbel tellen: tel de paren (comité van $k$ personen, voorzitter erin). Ofwel kies je het comité ( $\binom nk$ ) en daarna zijn voorzitter ( $k$ ): $k\binom nk$ paren. Ofwel kies je eerst de voorzitter ( $n$ mogelijkheden) en daarna de $k-1$ andere leden uit de $n-1$ overige: $n\binom{n-1}{k-1}$ paren.

Oefening 27.8 ★★

Een pad in het vlak gaat van $(0,0)$ naar $(m, n)$ met eenheidsstappen naar het oosten of naar het noorden. Toon aan 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 er $m$ naar het oosten en $n$ naar het noorden gaan; het ligt volledig vast door de verzameling tijdstippen (uit de $m+n$ ) waarop je naar het oosten stapt. Er zijn $\binom{m+n}{m}$ zulke keuzen.

Oefening 27.9 ★★★

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

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

door de deelverzamelingen met $k$ elementen te tellen van een verzameling die in een groep van $m$ en een groep van $n$ gesplitst is. 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 met $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 deelverzamelingen, en het somprincipe 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},

waarbij de symmetrie $\binom{n}{n-j} = \binom nj$ gebruikt wordt.

Oefening 27.10 ★★★

Toon met het binomium van Newton aan dat voor alle $n \geq 1$ geldt

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

(Tip: leid $(1+x)^n$ af, 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 afleiden: het afleiden van $(1+x)^n = \sum_k \binom nk x^k$ geeft $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$ ; vul $x = 1$ in.

27.5 Opgave: de kunst van het dubbel tellen

Probleem 27.1

Weekendopgave — sterren en strepen, verwisselde hoeden, en identiteiten bewezen door één ding op twee manieren te tellen

De diepste truc van de combinatoriek is ontwapenend eenvoudig: tel dezelfde verzameling twee keer, op twee verschillende manieren, en stel de antwoorden gelijk. Deze opgave oefent de modellen van Methode 27.13, voegt er een techniek aan toe die de cursus van dit hoofdstuk niet nodig had — de sterren en strepen van het ijsjes tellen — telt daarna precies de beroemde verwisselde hoeden, en vindt onder in de hoedenstapel het getal $\frac1\eu$ , dat hier voor de derde keer in dit boek opduikt.

Deel I — Het model kiezen.

Tel de nummerplaten van $2$ letters gevolgd door $3$ cijfers; en daarna de anagrammen van BANANA.
Tel uit een spel van $32$ kaarten de handen van $5$ kaarten; en daarna de handen met precies $2$ van de $4$ azen.
Een robot loopt van $(0,0)$ naar $(4,3)$ met alleen eenheidsstappen naar rechts of naar boven: hoeveel paden zijn er? (Codeer een pad als een woord in R en B.)
Werk $(1 + x)^4$ uit met het binomium van Newton (Stelling 27.11); vul daarna $x = 1$ en $x = -1$ in: welke twee identiteiten over de getallen $\binom nk$ vallen eruit?
Bewijs met dubbel tellen dat $k\binom nk = n\binom{n-1}{k-1}$ (tel de comités met voorzitter op twee manieren), en leid $\sum_{k=0}^{n} k\binom nk = n\,2^{n-1}$ af.

Deel II — Sterren en strepen.

Een ijssalon verkoopt $4$ smaken; je bestelt $10$ bollen (smaken mogen zich herhalen, en de volgorde in het hoorntje doet er niet toe). Codeer een bestelling als een rij van $10$ sterren (de bollen) gescheiden door $3$ strepen (de overgangen tussen smaken), en tel de bestellingen.
Tel de drietallen niet-negatieve gehele getallen met $x + y + z = 12$ .
Tel de drietallen positieve gehele getallen met $x + y + z = 12$ (substitueer $x = 1 + x'$ , enzovoort).
Hoeveel verschillende monomen komen voor in de uitwerking van $(a + b + c)^5$ ?
Toets de methode: tel met de formule de bestellingen van $3$ bollen uit $2$ smaken, som ze daarna allemaal op en vergelijk.
Zeg precies waar “de bollen zijn identiek” in de codering binnenkwam — en tel wat er in de plaats gebeurt wanneer de bollen in volgorde opgegeten worden (verschillende plaatsen), met de checklist van Methode 27.13.

Deel III — De verwisselde hoeden. Een derangement is een herverdeling van $n$ hoeden onder hun $n$ eigenaars waarbij niemand zijn eigen hoed krijgt; zij $D_n$ hun aantal. (Probleem 18.1 toonde dat gemiddeld één gast zijn eigen hoed terugvindt — nu tellen we de volledig ongelukkige feesten exact.)

Bereken $D_1$ , $D_2$ en $D_3$ door op te sommen, en $D_4$ geduldig (of slim).
Verantwoord de recursie $D_n = (n - 1)\left(D_{n-1} + D_{n-2}\right)$ : gast 1 krijgt een hoed $k \neq 1$ ( $n - 1$ keuzen); splits daarna op naargelang gast $k$ hoed 1 krijgt of niet. Ga na dat ze $D_4$ oplevert en bereken $D_5$ .
Bewijs voor $n = 3$ met inclusie en exclusie (trek de toewijzingen af die minstens één hoed op zijn plaats laten, en tel de dubbeltellingen weer op) dat $D_3 = 3!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}\right)$ , en formuleer de algemene formule.
Bereken $\frac{D_5}{5!}$ en vergelijk met $\frac1\eu \approx 0.3679$ : de kans dat een groot geschud feest volledig verwisselt, is $\frac1\eu$ — het derde optreden van die constante, na de loterij en de secretaresse van Probleem 23.1. (Waarom: de formule van vraag 14 is het begin van een beroemde reeks voor $\eu^{-1}$ , verteld in de universitaire volumes.)
Secret Santa onder $10$ vrienden: de namen worden uniform willekeurig getrokken. Wat is de kans dat de trekking geldig is (niemand trekt zichzelf), en hoeveel hertrekkingen mag de groep verwachten?

Deel IV — Twee keer tellen, twee keer winnen.

Het handdruklemma: op elk feest telt de som over de gasten van het aantal handen dat elk schudde, elke handdruk precies twee keer. Leid af dat het aantal gasten dat een oneven aantal handen schudde altijd even is — en ga na dat de bewering klopt op een feest met drie gasten.
Bewijs het juweel $1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2$ met inductie, en ga het na voor $n = 3$ . (De som van de kleine Gauss, gekwadrateerd, telt derde machten.)
De identiteit van Vandermonde (Oefening 27.9) via paden: duid $\binom{2n}{n}$ als het aantal roosterpaden uit vraag 3 van $(0,0)$ naar $(n,n)$ , knip elk pad door waar het de antidiagonaal kruist, en leg uit hoe $\sum_j \binom nj^2$ verschijnt.
Slotstuk — de vier zetten van de teller, telkens één regel met een voorbeeld uit deze opgave: vermenigvuldig fasen en tel gevallen op; codeer slim (sterren en strepen, padwoorden); tel hetzelfde twee keer (comité met voorzitter, handdrukken); trek het ongewenste af en corrigeer de dubbeltellingen (de derangementen). En noteer waar het tellen vervolgens aan de slag gaat: in de kansrekening, en bij de paden uit het hoofdstuk over matrices en grafen.

Oplossing

Oplossing van Probleem 27.1.

1. $26^2 \times 10^3 = 676\,000$ nummerplaten. BANANA: $6$ letters met A verdrievoudigd en N verdubbeld: $\frac{6!}{3!\,2!} = 60$ anagrammen.

2. $\binom{32}{5} = 201\,376$ handen; $\binom42 \binom{28}{3} = 6 \times 3\,276 = 19\,656$ met precies twee azen.

3. Een pad is een woord met $4$ R’s en $3$ B’s: kies de plaatsen van de B’s: $\binom73 = 35$ .

4. $(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$ . Voor $x = 1$ : $\sum_k \binom nk = 2^n$ ; voor $x = -1$ : $\sum_k (-1)^k \binom nk = 0$ — de rijsommen en de alternerende rijsommen van de driehoek van Pascal.

5. Comités van $k$ personen met een voorzitter, uit $n$ : kies het comité en daarna zijn voorzitter ( $\binom nk \times k$ ), of de voorzitter en daarna de overige leden ( $n \times \binom{n-1}{k-1}$ ): gelijk. Sommeren over $k$ : het rechterlid sommeert tot $n \sum_j \binom{n-1}{j} = n\,2^{n-1}$ .

6. Een rij van $10$ sterren en $3$ strepen codeert de bestelling (de bollen van smaak 1 vóór de eerste streep, enzovoort); de rij telt $13$ symbolen en ligt vast door de plaatsen van de strepen: $\binom{13}{3} = 286$ bestellingen.

7. $12$ sterren, $2$ strepen: $\binom{14}{2} = 91$ .

8. Met $x', y', z' \geq 0$ en $x' + y' + z' = 9$ : $\binom{11}{2} = 55$ .

9. Een monoom $a^i b^j c^k$ met $i + j + k = 5$ : $\binom72 = 21$ .

10. Met de formule: $3$ sterren, $1$ streep: $\binom41 = 4$ ; de opsomming: $(3,0)$ , $(2,1)$ , $(1,2)$ , $(0,3)$ : overeenstemming.

11. “Identiek” kwam binnen op het ogenblik dat een bestelling niets anders dan de aantallen per smaak bleek te zijn — de sterren dragen geen namen. Worden de bollen in volgorde opgegeten, dan kiest elk van de $10$ verschillende plaatsen vrij een smaak: $4^{10} = 1\,048\,576$ mogelijkheden — een ander model en een andere wereld (Methode 27.13: vraag altijd geordend? verschillend? herhaling toegestaan?).

12. $D_1 = 0$ ; $D_2 = 1$ (verwisselen); $D_3 = 2$ (de twee $3$ -cykels); $D_4 = 9$ .

13. Gast 1 krijgt hoed $k \neq 1$ : $n - 1$ keuzen. Krijgt gast $k$ hoed 1, dan verwisselen de overige $n - 2$ gasten hun eigen hoeden: $D_{n-2}$ manieren. Krijgt gast $k$ hoed 1 niet, herdoop dan hoed 1 tot de verboden hoed van gast $k$ : de $n - 1$ resterende gasten verwisselen: $D_{n-1}$ manieren. Dus $D_n = (n-1)(D_{n-1} + D_{n-2})$ . Controle: $D_4 = 3(2 + 1) = 9$ ; en $D_5 = 4(9 + 2) = 44$ .

14. Trek van de $3! = 6$ toewijzingen die af welke minstens één hoed op zijn plaats laten: er zijn er drie die een gegeven hoed vastleggen ( $2!$ elk, $3 \times 2 = 6$ ), waarbij de paren dubbel geteld worden ( $3$ paren, $1!$ elk) en dus moeten terugkeren, en de identieke toewijzing ( $1$ ) weer afgetrokken wordt: $D_3 = 6 - 6 + 3 - 1 = 2$ , dat wil zeggen $3!\left(1 - 1 + \frac12 - \frac16\right) = 2$ . In het algemeen is $D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ .

15. $\frac{D_5}{120} = \frac{44}{120} \approx 0.3667$ , al dicht bij $\frac1\eu \approx 0.3679$ : de alternerende som $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \dots$ stapt naar $\eu^{-1}$ . Op een groot feest verwisselen de hoeden zich in ongeveer $36.8\,\%$ van de gevallen — de constante van de loterij en van de secretaresse, derde waarneming.

16. $\P(\text{geldig}) = \frac{D_{10}}{10!} \approx 0.368$ . Elke hertrekking slaagt met kans $\approx \frac1\eu$ , dus het verwachte aantal trekkingen is ongeveer $\eu \approx 2.7$ : reken op drie rondes met de hoed.

17. Elke handdruk draagt $2$ bij aan de totale graadsom, dus de som van alle handdrukaantallen van de gasten is even. Een som van gehele getallen is alleen even als het aantal oneven termen even is: de oneven schudders komen in even aantallen. (Bij drie gasten: de mogelijke handdrukprofielen hebben nooit precies één of drie oneven waarden — ga de vier mogelijke grafen na.)

18. $n = 1$ : $1 = 1$ . Geldt $1^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ , dan geeft $(n+1)^3$ erbij:

\frac{n^2(n+1)^2}{4} + (n+1)^3 = \frac{(n+1)^2\left(n^2 + 4n + 4\right)}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^{\!2} :

overerving. Voor $n = 3$ : $1 + 8 + 27 = 36 = 6^2$ .

19. Een pad naar $(n, n)$ zet $2n$ stappen en kruist de antidiagonaal $x + y = n$ in precies één roosterpunt $(j, n - j)$ ; de eerste helft is een pad met $j$ R’s onder $n$ stappen ( $\binom nj$ keuzen), en de tweede helft, achterstevoren gelezen, eveneens ( $\binom nj$ opnieuw, wegens de symmetrie). Sommeren over het kruispunt geeft $\binom{2n}{n} = \sum_j \binom nj^2$ — de identiteit van Vandermonde, getekend.

20. Vermenigvuldig fasen, tel gevallen op: de nummerplaten en de pokerhanden. Codeer: paden als RB-woorden, bestellingen als sterren en strepen. Tel twee keer: comités met voorzitter, handdrukken, doormidden geknipte paden. Trek af en corrigeer: de verwisselde hoeden, met $\frac1\eu$ als restant. Volgende haltes: deze tellingen onder de breuken van de kansrekening, en de padentellende machten van de verbindingsmatrices twee hoofdstukken verderop.

Begrippen gedefinieerd in dit hoofdstuk

Bekijk alle 395 begrippen in de begrippenlijst

27.1 De twee telprincipes

27.2 kkk-tallen, permutaties, faculteiten

27.3 Combinaties en binomiaalcoëfficiënten

27.4 Oefeningen

27.5 Opgave: de kunst van het dubbel tellen

Begrippen gedefinieerd in dit hoofdstuk

27.2 $k$ -tallen, permutaties, faculteiten