---
title: "Telkunde"
book: "Universitaire wiskunde — Bachelor jaar 1"
subject: math
language: nl
chapter: 2
exercises: 12
source: https://one-course.com/books/math/3/nl/chapter/2-telkunde
---

# Hoofdstuk 2 — Telkunde

[Eindige verzamelingen](#def-b1-counting-card) tellen klinkt elementair — en wordt snel subtiel. Dit hoofdstuk definieert de [kardinaliteit](#def-b1-counting-card) zoals het hoort (via bijecties, in de geest van [Hoofdstuk 1](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#ch-b1-logic)), stelt de handvol telprincipes vast waaruit al het overige volgt, en leidt daaruit de klassieke tellingen af: lijsten, [permutaties](#def-b1-counting-objects), deelverzamelingen, [binomiaalcoëfficiënten](#def-b1-counting-objects).

## 2.1 Kardinaliteit van eindige verzamelingen

**Definitie 2.1 (Eindige verzameling, kardinaliteit).**

Schrijf voor $n \in \N^*$ kortweg $\intint{1}{n} = \{1, 2, \dots, n\}$. Een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) $E$ heet *eindig* wanneer $E = \emptyset$ of wanneer er voor zekere $n \in \N^*$ een bijectie van $\intint{1}{n}$ op $E$ bestaat; die $n$ is uniek ([Stelling 2.2](#thm-b1-counting-welldef)) en heet de *kardinaliteit* van $E$, genoteerd $\abs{E}$ (met $\abs{\emptyset} = 0$).

**Stelling 2.2 (De kardinaliteit is welgedefinieerd).**

Is $m \neq n$, dan bestaat er geen bijectie van $\intint{1}{m}$ op $\intint{1}{n}$. Preciezer: is $m > n$, dan bestaat er geen injectie van $\intint{1}{m}$ in $\intint{1}{n}$.

**Bewijs.** We bewijzen met inductie naar $n$ de [uitspraak](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-statement): *voor alle $m > n$ bestaat er geen injectie $\intint{1}{m} \to \intint{1}{n}$*. Voor $n = 0$ is het doel leeg en $m \geq 1$: er bestaat helemaal geen [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map). Neem de [uitspraak](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-statement) aan voor $n$ en stel dat $f \colon \intint{1}{m} \to
\intint{1}{n+1}$ een injectie is met $m > n + 1$. Wordt de waarde $n + 1$ niet bereikt, dan is $f$ een injectie in $\intint{1}{n}$, in tegenspraak met de inductiehypothese. Anders is $f(a) = n + 1$ voor precies één $a$; verwissel $f(a)$ en $f(m)$ (formeel: stel samen met de transpositie van die twee waarden), zodat de nieuwe injectie $g$ voldoet aan $g(m) = n +
1$. De beperking van $g$ tot $\intint{1}{m-1}$ is dan een injectie in $\intint{1}{n}$ met $m - 1 > n$ — opnieuw een tegenspraak. ∎

**Gevolg 2.3 (Duivenhokprincipe).**

Is $\abs{E} > \abs{F}$, dan is geen enkele [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) $f \colon E \to F$ [injectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj): twee elementen van $E$ delen hun beeld.

**Bewijs.** Schrijf $\abs E = m$, $\abs F = n$ met $m > n$, en kies bijecties $u
\colon \intint1m \to E$ en $v \colon F \to \intint1n$. Was $f$ [injectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj), dan was $v \circ f \circ u$ een injectie van $\intint1m$ in $\intint1n$ (een samenstelling van injecties, [Propositie 1.26](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#prop-b1-logic-comp)), in tegenspraak met [Stelling 2.2](#thm-b1-counting-welldef). ∎

**Opmerking 2.4 (Tussenspel: waarom die verwisseling in het bewijs?).**

Het bewijs van [Stelling 2.2](#thm-b1-counting-welldef) bevat de eerste werkelijk vernuftige zet van dit hoofdstuk, die het waard is om langzaam te herhalen. Het obstakel: om de inductiehypothese te gebruiken wil je het laatste punt $m$ van het domein *en* het laatste punt $n+1$ van het doel weglaten, maar $f$ kan een ander punt $a$ naar $n + 1$ sturen, en dan beschadigt het weglaten van dat doelpunt de [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) elders. De remedie: stel $f$ samen met de transpositie van de twee *waarden* $f(a)$ en $f(m)$ — een bijectie van het doel, zodat de injectiviteit behouden blijft — waarna de lastige waarde $n + 1$ op de onschadelijke plaats $m$ zit en beide weglatingen schoon verlopen. Dit patroon “eerst normaliseren, dan snijden” keert terug: zo herleidt de recursie voor de derangementen $\sigma^{-1}(n+1)$ in de weekendopgave van dit hoofdstuk, en zo worden [permutaties](#def-b1-counting-objects) overal opgelapt in de opgave over de symmetrische groep in [Hoofdstuk 7](https://one-course.com/books/math/3/nl/chapter/7-algebraische-structuren#ch-b1-structures).

**Propositie 2.5 (Injecties, surjecties en kardinaliteit).**

Zij $E, F$ [eindige verzamelingen](#def-b1-counting-card) met $\abs{E} = \abs{F}$, en zij $f
\colon E \to F$. Dan geldt

$$
f \text{ injectief} \iff f \text{ surjectief} \iff f \text{ bijectief}.
$$

**Bewijs.** Stel $f$ [injectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj). Dan is $f$ een bijectie van $E$ op $f(E)$, dus $\abs{f(E)} = \abs{E} = \abs{F}$. Miste $f(E)$ een punt $y_0$ van $F$, dan was $f$ een injectie van $E$ in $F \setminus \{y_0\}$, een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) met [kardinaliteit](#def-b1-counting-card) $\abs{F} - 1 < \abs{E}$ — onmogelijk wegens het duivenhokprincipe. Dus $f(E) = F$: $f$ is [surjectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) en daarmee [bijectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj).

Stel $f$ [surjectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj). Kies bij elke $y \in F$ één [origineel](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) $s(y) \in E$; dan is $f \circ s = \mathrm{id}_F$, zodat $s$ [injectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) is ([Propositie 1.26](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#prop-b1-logic-comp)). Volgens de vorige alinea, toegepast op $s$ (de [kardinaliteiten](#def-b1-counting-card) zijn gelijk), is $s$ [bijectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj). Uit $f \circ s =
\mathrm{id}_F$ volgt $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$, dus is $f$ [bijectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj). Ten slotte is een [bijectieve](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) per definitie zowel [injectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) als [surjectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj), waarmee de kring van implicaties gesloten is. ∎

**Voorbeeld 2.6 (Eindigheid is essentieel).**

Op een *eindige* [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) is [Propositie 2.5](#prop-b1-counting-injsur) een krachtige kortere weg: elke [injectieve](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) van $E$ naar zichzelf is automatisch een [permutatie](#def-b1-counting-objects) van $E$ — de helft van de bijectiviteit krijg je gratis. Beide implicaties bezwijken op oneindige [verzamelingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets): $n \mapsto n + 1$ is [injectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) van $\N$ naar $\N$ maar mist $0$, en de [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) $\N \to \N$ die $0 \mapsto 0$ en $n \mapsto n - 1$ voor $n
\geq 1$ stuurt, is [surjectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) maar niet [injectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj). Telkens als deze propositie wordt ingeroepen, doet de eindigheidshypothese echt werk — een thema dat de weekendopgave van [Hoofdstuk 1](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#ch-b1-logic) van de andere kant bekijkt, waar oneindige [verzamelingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) juist die [verzamelingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) zijn die zulke [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) op zichzelf toelaten.

**Voorbeeld 2.7 (De helft van het werk, gratis).**

Beschouw de [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) $f$ op $\{0, 1, \dots, 6\}$ die $k$ naar de rest van $3k$ bij deling door $7$ stuurt; haar waardentabel luidt

$$
0,\ 3,\ 6,\ 2,\ 5,\ 1,\ 4 .
$$

Is $f$ een bijectie? Alleen de injectiviteit volstaat ([Propositie 2.5](#prop-b1-counting-injsur)): hebben $3k$ en $3k'$ dezelfde rest, dan deelt $7$ het getal $3(k - k')$, en omdat $7$ priem is en $3$ niet deelt, deelt het $k - k'$ (lemma van Euclides, hier gebruikt zoals bekend uit het bovenbouwvolume en bewezen in [Hoofdstuk 6](https://one-course.com/books/math/3/nl/chapter/6-getaltheorie-in-z#ch-b1-arith)); met $\abs{k - k'} \leq 6$ dwingt dat $k = k'$ af. De surjectiviteit komt er gratis bij — je hoeft $3k \equiv c$ niet voor elke $c$ op te lossen, al bevestigt de tabel dat elke waarde precies één keer voorkomt. Deze kortere weg is een werkpaard: ze bewijst de inverteerbaarheid van de vermenigvuldiging modulo $n$ ([Hoofdstuk 6](https://one-course.com/books/math/3/nl/chapter/6-getaltheorie-in-z#ch-b1-arith)), drijft het koppelen in de stelling van Wilson aan, en keert in de lineaire algebra terug als “een endomorfisme van een eindigdimensionale ruimte is [injectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) precies wanneer het [surjectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) is” ([Hoofdstuk 19](https://one-course.com/books/math/3/nl/chapter/19-eindige-dimensie#ch-b1-findim)).

## 2.2 De telprincipes

**Propositie 2.8 (Som- en productregel).**

Zij $E, F$ [eindige verzamelingen](#def-b1-counting-card).

1. Is $E \cap F = \emptyset$ , dan is $\abs{E \cup F} = \abs{E} +  \abs{F}$ ; algemener geldt voor een [partitie](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#thm-b1-logic-partition) van $E$ in stukken $E_1, \dots, E_k$ dat $\abs{E} = \sum_i \abs{E_i}$ .
2. In het algemeen is $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E  \cap F}$ .
3. $\abs{E \times F} = \abs{E} \times \abs{F}$ .
4. De [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) $F^E$ van alle [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) van $E$ naar $F$ voldoet aan $\abs{F^E} = \abs{F}^{\abs{E}}$ .
5. $\abs{\mathcal{P}(E)} = 2^{\abs{E}}$ .

**Bewijs.** (1) Plak de opsommingen aan elkaar: is $E = \{x_1, \dots, x_m\}$ en $F =
\{y_1, \dots, y_n\}$ zonder herhaling, dan somt $x_1, \dots, x_m, y_1,
\dots, y_n$ de [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) $E \cup F$ zonder herhaling op (wegens de disjunctheid). Inductie breidt dit uit tot $k$ stukken.

(2) $E \cup F$ is de disjuncte vereniging van $E$ en $F \setminus E$, en $F$ is de disjuncte vereniging van $F \cap E$ en $F \setminus E$; dus is $\abs{E \cup F} = \abs{E} + \abs{F \setminus E} = \abs{E} + \abs{F} -
\abs{E \cap F}$.

(3) $E \times F$ is de disjuncte vereniging, over $x \in E$, van de [verzamelingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) $\{x\} \times F$, elk met [kardinaliteit](#def-b1-counting-card) $\abs{F}$; pas (1) toe.

(4) Een [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) van $E = \{x_1, \dots, x_m\}$ naar $F$ is precies de keuze van het $m$-tal $(f(x_1), \dots, f(x_m)) \in F^m$; die overeenkomst is een bijectie, en $\abs{F^m} = \abs{F}^m$ volgens (3) en inductie.

(5) Deelverzamelingen van $E$ komen [bijectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) overeen met [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) $E
\to \{0, 1\}$ (stuur $A$ naar haar indicatorfunctie); pas (4) toe. ∎

**Voorbeeld 2.9 (Tellen via het complement).**

Hoeveel viercijferige pincodes (cijfers $0$–$9$, volgorde telt, herhaling toegestaan) bevatten *minstens één* herhaald cijfer? Rechtstreeks tellen betekent jongleren met de gevallen “precies één paar, twee paren, een drietal, een viertal” — vijf overlappende configuraties. Tel liever het complement: alle codes samen zijn $10^4 = 10\,000$ (productregel), en de codes met vier verschillende cijfers zijn $10 \times 9 \times 8 \times 7 =
5\,040$ ($4$-variaties), zodat het antwoord

$$
10^4 - 10 \cdot 9 \cdot 8 \cdot 7 = 10\,000 - 5\,040 = 4\,960
$$

luidt. Bijna de helft van alle pincodes herhaalt een cijfer. Het inzicht: zodra een telling geformuleerd is met “minstens” of “niet alle”, probeer je eerst het complement — de somregel garandeert $\abs{A} = \abs{E} - \abs{\overline A}$, en het complement is vaak één enkele overzichtelijke configuratie.

**Voorbeeld 2.10 (Roosterpaden).**

Tel de kortste paden van de hoek $(0,0)$ naar de hoek $(4, 3)$ van een rooster, waarbij je telkens één stap naar rechts (R) of één stap omhoog (U) zet. Elk zo’n pad zet precies $7$ stappen, waarvan $4$ een R en $3$ een U; omgekeerd beschrijft elk woord van lengte $7$ in de letters R en U met vier R’s precies één pad. De paden komen dus [bijectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) overeen met de keuzes van de posities van de R’s:

$$
\binom{7}{4} = 35 .
$$

Het inzicht zit in de *codering*: de telling werd triviaal op het moment dat elk pad in een woord vertaald werd, dat wil zeggen in een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) posities — opnieuw een illustratie van de leuze dat een correcte telling een vermomde bijectie is ([Methode 2.19](#met-b1-counting-which)).

![Eén van de 74 = 35 kortste paden van (0,0) naar (4,3): het getekende pad codeert het woord RURRURU, dat wil zeggen de keuze van de posities \1,3,4,6\ voor de letter R onder de zeven stappen.](https://one-course.com/images/onecourse/chapters/math-3/b1-counting/fig-9d38fb7e142a.svg)

*Eén van de $\binom74 = 35$ kortste paden van $(0,0)$ naar $(4,3)$: het getekende pad codeert het woord RURRURU, dat wil zeggen de keuze van de posities $\{1,3,4,6\}$ voor de letter R onder de zeven stappen.*

## 2.3 Lijsten, permutaties, deelverzamelingen

**Definitie 2.11 (Variaties, permutaties, combinaties).**

Zij $E$ een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) met $\abs{E} = n$ en zij $0 \leq k \leq n$.

- Een *$k$-variatie* van $E$ is een [injectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) $k$ -tal elementen van $E$ (een geordende keuze zonder herhaling);
- een *permutatie* van $E$ is een bijectie van $E$ naar zichzelf — equivalent: een $n$ -variatie;
- een *$k$-combinatie* is een deelverzameling van $E$ met $k$ elementen (een ongeordende keuze zonder herhaling). Hun aantal wordt genoteerd $\binom{n}{k}$ , uitgesproken als “ $n$ boven $k$ ”.

**Stelling 2.12 (De drie tellingen).**

Met $n = \abs{E}$ en $0 \leq k \leq n$:

1. het aantal $k$ -variaties van $E$ is $n (n-1) \cdots (n-k+1) =  \dfrac{n!}{(n-k)!}$ ;
2. het aantal [permutaties](#def-b1-counting-objects) van $E$ is $n!$ ;
3. $\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ .

**Bewijs.** (1) Kies de eerste coördinaat ($n$ mogelijkheden), dan de tweede ($n -
1$ resterende), …, dan de $k$-de ($n - k + 1$ mogelijkheden). Formeel gaat de inductie naar $k$. Voor $k = 1$ zijn er $n$ [injectieve](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) tupels met één term. Neem de telling aan voor $k - 1$. Elke $k$-variatie $(x_1, \dots, x_k)$ ontstaat uit precies één $(k-1)$-variatie — haar afknotting $(x_1, \dots, x_{k-1})$ — door er een laatste coördinaat buiten $\{x_1, \dots, x_{k-1}\}$ aan te plakken, waarvoor precies $n - (k - 1)$ waarden beschikbaar zijn. Het afknotten deelt de $k$-variaties dus op in klassen van gemeenschappelijke grootte $n - k + 1$, geïndexeerd door de $(k-1)$-variaties, en de somregel geeft

$$
\frac{n!}{(n-k+1)!}\;(n - k + 1) = \frac{n!}{(n-k)!} .
$$

(2) is (1) met $k = n$.

(3) Elke $k$-deelverzameling ordent tot $k!$ verschillende $k$-variaties, en elke $k$-variatie komt van precies één deelverzameling: dus $\frac{n!}{(n-k)!} = \binom nk \cdot k!$. ∎

**Voorbeeld 2.13 (Ronde tafels: delen door een symmetrie).**

Op hoeveel manieren kunnen $n$ gasten rond een ronde tafel plaatsnemen, waarbij twee opstellingen dezelfde zijn zodra elke gast dezelfde linker- en rechterbuur heeft — dat wil zeggen op rotatie na? Elke ronde opstelling komt overeen met precies $n$ lineaire opstellingen (knip de kring op elk van de $n$ plaatsen door), zodat de $n!$ lineaire volgordes in groepjes van $n$ samenvallen:

$$
\frac{n!}{n} = (n-1)! \quad\text{ronde opstellingen.}
$$

Equivalent: zet één uitgekozen gast willekeurig neer (waarmee de draaivrijheid verdwijnt) en orden de overige $n - 1$ gasten met de klok mee. Voor $n = 6$: $120$ tafels. Beide oplossingen tonen de twee standaardremedies tegen dubbeltellen: deel door het exacte aantal herhalingen, of *breek de symmetrie* door één object vast te pinnen. Beide vergen dat de groep herhalingen voor elke configuratie even groot is — wat het bewijs van de formule $\binom nk =
\frac{n!}{k!\,(n-k)!}$ hierboven ook al gebruikte, met $k!$ in de rol van $n$.

**Voorbeeld 2.14 (Een voorwaarde erbij).**

We blijven bij de ronde tafel: hoeveel van de $(n-1)!$ tafels met $n
\geq 3$ gasten zetten twee gegeven gasten $A$ en $B$ *uit elkaar* (niet naast elkaar)? Tel het complement. Tafels waar $A$ en $B$ naast elkaar zitten: lijm ze tot één blok — $n - 1$ objecten rond de tafel, dus $(n-2)!$ ronde opstellingen — en orden dan het paar binnen zijn blok ($2$ manieren): $2\,(n-2)!$ tafels met de twee naast elkaar. Bijgevolg houden

$$
(n-1)! - 2\,(n-2)! = (n-2)!\,\bigl((n - 1) - 2\bigr)
= (n-3)\,(n-2)!
$$

tafels hen uit elkaar. Controles: $n = 3$ geeft $0$ (rond een driehoek raakt iedereen aan iedereen) en $n = 4$ geeft $2$, met de hand na te gaan. De lijmtruc — behandel een afgedwongen blok als één object en tel daarna zijn interne opstellingen — is de standaardremedie voor buurvoorwaarden, lineair zowel als rond.

**Propositie 2.15 (Basisidentiteiten).**

Voor $0 \leq k \leq n$:

$$
\binom{n}{k} = \binom{n}{n-k},
\qquad
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
\quad (1 \leq k \leq n-1),
\qquad
\sum_{k=0}^{n} \binom{n}{k} = 2^n .
$$

**Bewijs.** Eerste identiteit: $A \mapsto E \setminus A$ is een bijectie tussen de $k$-deelverzamelingen en de $(n-k)$-deelverzamelingen. Regel van Pascal: leg een element $a \in E$ vast; de $k$-deelverzamelingen splitsen in die welke $a$ bevatten (kies de $k -
1$ overige: $\binom{n-1}{k-1}$) en die welke $a$ mijden ($\binom{n-1}{k}$). Derde identiteit: beide leden tellen alle deelverzamelingen van $E$, links opgesplitst naar grootte ([Propositie 2.8](#prop-b1-counting-rules) (1) en (5)). ∎

**Stelling 2.16 (Binomium van Newton).**

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

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

**Bewijs.** Distributief uitwerken van $(a+b)(a+b)\cdots(a+b)$ levert één term per keuze, in elke factor, van $a$ of $b$: de term $a^k b^{n-k}$ verschijnt eenmaal voor elke manier om te kiezen welke $k$ van de $n$ factoren een $a$ bijdragen — dat is $\binom nk$ maal. (Alternatief: inductie naar $n$ met de regel van Pascal.) ∎

**Voorbeeld 2.17.**

Twee klassieke bijzondere gevallen: $a = b = 1$ geeft $\sum_k \binom nk
= 2^n$ terug; $a = -1$, $b = 1$ geeft $\sum_{k} (-1)^k \binom nk = 0$ voor $n \geq 1$: van de deelverzamelingen van een niet-lege [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) heeft precies de helft een even [kardinaliteit](#def-b1-counting-card).

**Voorbeeld 2.18 (Eén identiteit, twee bewijzen).**

Het bijzondere geval $a = 2$, $b = 1$ van het binomium luidt

$$
\sum_{k=0}^{n} \binom nk\,2^k = 3^n .
$$

Hier is dezelfde identiteit zonder ook maar één algebraïsche stap. Het rechterlid telt de woorden van lengte $n$ over het alfabet $\{0,
1, 2\}$ (productregel). Deel elk woord in naar de [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) $K$ van posities met een letter ongelijk aan nul: een $K$ met $\abs K =
k$ kiezen kost $\binom nk$, waarna elke positie van $K$ onafhankelijk een $1$ of een $2$ draagt: $2^k$ manieren. De somregel over $k$ geeft het linkerlid. Behalve het genoegen dat beide overeenstemmen, hebben de twee bewijzen verschillende verdiensten: het algebraïsche veralgemeent naar elke waarde van $a$, het combinatorische *verklaart* de formule en past zich aan voorwaarden aan (verbied bijvoorbeeld de letter $2$ op de laatste positie) die geen enkele substitutie vat. Beide technieken paraat houden is de praktische vaardigheid die dit hoofdstuk traint.

**Methode 2.19 (Welke telling past?).**

Beantwoord vóór het rekenen twee vragen over de keuze: doet de *volgorde* ertoe, en zijn *herhalingen* toegestaan?

|  | volgorde telt | volgorde telt niet |
| --- | --- | --- |
| zonder herhaling | $\dfrac{n!}{(n-k)!}$ | $\dbinom{n}{k}$ |
| [6pt] met herhaling | $n^k$ | ([Oefening 2.10](#exo-b1-counting-10)) |

Ga vervolgens op zoek naar een bijectie of een [partitie](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#thm-b1-logic-partition) die het probleem tot deze modeltellingen herleidt; een correcte telling is een vermomde bijectie.

**Opmerking 2.20 (Veelgemaakte fouten bij het tellen).**

1. *Niet-disjuncte gevallen optellen.* De somregel vergt een [partitie](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#thm-b1-logic-partition) ; kunnen configuraties aan twee gevallen tegelijk voldoen, dan worden ze dubbel geteld — de remedie is inclusie-exclusie ( [Stelling 2.24](#thm-b1-counting-inclexcl) ) of een fijnere gevalsindeling.
2. *Geordend tegenover ongeordend.* “Een commissie van twee” kiezen is $\binom n2$ en niet $n(n-1)$ : beslis *vóór het rekenen* of de keuze een volgorde draagt, en als een geordende telling makkelijker is, deel dan aan het eind door het aantal volgordes — maar alleen wanneer elk ongeordend object uit *even veel* geordende ontstaat.
3. *Meertrapskeuzes die niet onafhankelijk zijn.* De productregel vergt dat het aantal mogelijkheden in elke stap onafhankelijk is van de voorgaande keuzes. “Kies een aanvoerder, dan een andere vice-aanvoerder” is prima ( $n(n-1)$ ); “kies twee spelers die met elkaar overweg kunnen” is helemaal geen product van twee stappen.
4. *Dubbeltellen door de constructie.* Elk object tweemaal bouwen — bijvoorbeeld handen met *minstens* één aas tellen als (kies een aas) $\times$ (kies $4$ andere kaarten) — telt handen met twee azen dubbel. “Minstens” vraagt vrijwel altijd om het complement ( [Voorbeeld 2.9](#ex-b1-counting-complement) ).

**Voorbeeld 2.21 (Een telling in pokerstijl).**

Uit een spel van $52$ kaarten is het aantal handen van $5$ kaarten $\binom{52}{5} = 2\,598\,960$. Handen met precies één aas: kies de aas ($4$ manieren) en dan $4$ kaarten uit de $48$ niet-azen: $4
\binom{48}{4} = 778\,320$. De productregel is van toepassing omdat de keuze in onafhankelijke stappen uiteenvalt.

**Methode 2.22 (Dubbeltellen).**

Om een identiteit tussen twee teluitdrukkingen te bewijzen, zoek je één [eindige verzameling](#def-b1-counting-card) die beide leden tellen — doorgaans een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) *paren* — en bereken je haar [kardinaliteit](#def-b1-counting-card) in twee verschillende volgordes. Het prototype is het *handdruklemma*: tel op een feest de paren (persoon, gegeven handdruk). Sommeren over personen geeft $\sum_p
d_p$ (het aantal handdrukken van persoon $p$); sommeren over handdrukken geeft tweemaal het aantal handdrukken (elke handdruk betreft twee personen). Bijgevolg is $\sum_p d_p$ even — zodat het aantal mensen dat een oneven aantal handen schudde altijd even is, een niet-triviale conclusie zonder ook maar één formule. Dezelfde motor drijft [Oefening 2.12](#exo-b1-counting-12) en verscheidene vragen van de weekendopgave hieronder aan.

**Voorbeeld 2.23 (De gemiddelde deelverzameling).**

Wat is de gemiddelde [kardinaliteit](#def-b1-counting-card) van een deelverzameling van een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) $E$ met $n$ elementen, als alle $2^n$ deelverzamelingen even waarschijnlijk zijn? Dubbeltel de paren $(A, a)$ met $a \in A$: sommeren over deelverzamelingen geeft $\sum_A \abs A$, het gezochte totaal; sommeren over elementen geeft $n \cdot 2^{n-1}$ (elk van de $n$ elementen ligt in precies de helft van de deelverzamelingen — koppel elke $A$ die $a$ bevat aan $A \setminus \{a\}$). Bijgevolg is

$$
\frac{1}{2^n}\sum_{A \subseteq E} \abs A
= \frac{n\,2^{n-1}}{2^n} = \frac n2 :
$$

deelverzamelingen zijn gemiddeld halfvol — zoals ook de symmetrie $A \leftrightarrow \overline A$ voorspelt, die de groottes $k$ en $n - k$ koppelt. Twee bewijzen, één antwoord, en beide vermijden de rechtstreekse berekening $\sum_k k\binom nk$ van [Oefening 2.5](#exo-b1-counting-5): een goedgekozen koppeling vervangt vaak een identiteit.

## 2.4 Inclusie-exclusie

**Stelling 2.24 (Inclusie-exclusie).**

Voor [eindige verzamelingen](#def-b1-counting-card) $A_1, \dots, A_p$ geldt

$$
\Bigl|\, \bigcup_{i=1}^{p} A_i \,\Bigr|
= \sum_{\emptyset \neq I \subseteq \intint{1}{p}}
(-1)^{\abs{I}+1} \Bigl|\, \bigcap_{i \in I} A_i \,\Bigr| .
$$

Voor $p = 3$: $\abs{A \cup B \cup C} = \abs A + \abs B + \abs C - \abs{A \cap B} -
\abs{A \cap C} - \abs{B \cap C} + \abs{A \cap B \cap C}$.

**Bewijs.** Leg een element $x$ van de vereniging vast en tel zijn bijdrage aan het rechterlid. Zij $J = \{i : x \in A_i\}$, met [kardinaliteit](#def-b1-counting-card) $m \geq 1$. Het element $x$ wordt in $\abs{\bigcap_{i \in I} A_i}$ precies één keer meegeteld wanneer $\emptyset \neq I \subseteq J$, met teken $(-1)^{\abs I
+ 1}$; zijn totale bijdrage is dus

$$
\sum_{k=1}^{m} \binom{m}{k} (-1)^{k+1}
= 1 - \sum_{k=0}^{m} \binom mk (-1)^k = 1 - 0 = 1
$$

volgens [Voorbeeld 2.17](#ex-b1-counting-binomial). Elk element van de vereniging wordt dus precies één keer geteld. ∎

**Voorbeeld 2.25 (Relatief priem tellen).**

Hoeveel getallen uit $\intint1{120}$ zijn relatief priem met $120 =
2^3 \times 3 \times 5$? Een geheel getal heeft precies dan een factor gemeen met $120$ wanneer het deelbaar is door $2$, $3$ of $5$; tel dus het complement van $A_2 \cup A_3 \cup A_5$, waarbij $A_d$ de veelvouden van $d$ verzamelt. Binnen $\intint1{120}$ zijn er $120/d$ veelvouden van $d$ zodra $d$ het getal $120$ deelt — geheel zonder afrondingsfuncties — en $A_2 \cap A_3 = A_6$, enzovoort. Inclusie-exclusie geeft

$$
\abs{A_2 \cup A_3 \cup A_5}
= 60 + 40 + 24 - 20 - 12 - 8 + 4 = 88 ,
$$

zodat $120 - 88 = 32$ getallen relatief priem met $120$ zijn. Het is leerzaam de berekening als een product te hergroeperen:

$$
120 - 88 = 120\Bigl(1 - \frac12\Bigr)\Bigl(1 -
\frac13\Bigr)\Bigl(1 - \frac15\Bigr) = 120 \cdot \frac12 \cdot
\frac23 \cdot \frac45 = 32 :
$$

de drie haakjes uitwerken levert precies de acht getekende termen van de inclusie-exclusie op, één per deelverzameling van $\{2, 3, 5\}$. Deze productvorm definieert de indicator van Euler, waarvan de rekenkundige rol opduikt bij de congruenties van [Hoofdstuk 6](https://one-course.com/books/math/3/nl/chapter/6-getaltheorie-in-z#ch-b1-arith) en verder wordt uitgewerkt in het volume van bachelorjaar 2.

**Voorbeeld 2.26 (Derangementen).**

Een *derangement* is een [permutatie](#def-b1-counting-objects) zonder vaste punten. Zij $A_i$ de [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) van de [permutaties](#def-b1-counting-objects) van $\intint{1}{n}$ die $i$ vasthouden; dan is $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$, en de inclusie-exclusie telt de [permutaties](#def-b1-counting-objects) met minstens één vast punt; het aantal derangementen is

$$
D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .
$$

Omdat $\sum (-1)^k / k! \to \eu^{-1}$ (zie [Hoofdstuk 17](https://one-course.com/books/math/3/nl/chapter/17-getallenreeksen#ch-b1-series)), is ongeveer $37\%$ van alle [permutaties](#def-b1-counting-objects) een derangement, wat $n$ ook is.

**Opmerking 2.27 (Waar dit hoofdstuk gebruikt wordt).**

[Binomiaalcoëfficiënten](#def-b1-counting-objects) zijn de meest hergebruikte objecten van dit hoofdstuk: ze dragen het binomium in [Hoofdstuk 8](https://one-course.com/books/math/3/nl/chapter/8-veeltermen#ch-b1-poly) (ontwikkeling van $(X + a)^n$), de formule van Leibniz voor de $n$-de afgeleide van een product in [Hoofdstuk 14](https://one-course.com/books/math/3/nl/chapter/14-differentiaalrekening#ch-b1-derivative), en de coëfficiënten van Taylorontwikkelingen in [Hoofdstuk 16](https://one-course.com/books/math/3/nl/chapter/16-formules-van-taylor-en-asymptotische-ontwikkelingen#ch-b1-taylor). [Permutaties](#def-b1-counting-objects) keren terug als groep — met het teken, gebouwd op het tellen van inversies — in [Hoofdstuk 7](https://one-course.com/books/math/3/nl/chapter/7-algebraische-structuren#ch-b1-structures), en dat teken definieert op zijn beurt de determinanten in [Hoofdstuk 22](https://one-course.com/books/math/3/nl/chapter/22-determinanten-en-lineaire-stelsels#ch-b1-det). Inclusie-exclusie en de telprincipes vormen de eindige ruggengraat van de discrete kansrekening, die uitgewerkt wordt in het volume van bachelorjaar 2; de derangementengetallen van [Voorbeeld 2.26](#ex-b1-counting-derangement) worden grondig bestudeerd in de weekendopgave hieronder.

## 2.5 Oefeningen

**Oefening 2.1 ★.**

Een nummerplaat bestaat uit twee letters (A–Z), dan drie cijfers, dan twee letters. Hoeveel platen zijn er mogelijk? En hoeveel zonder herhaalde letter onder de vier?

**Oplossing van Oefening 2.1.**

Onafhankelijke stappen en de productregel: $26^2 \times 10^3 \times 26^2
= 26^4 \times 1000 = 456\,976\,000$ platen. Zijn de vier letters twee aan twee verschillend, dan vormen de letterstappen een $4$-variatie van het alfabet: $26 \times 25 \times 24 \times 23 = 358\,800$ manieren, dus $358\,800 \times 1000 = 358\,800\,000$ platen.

**Oefening 2.2 ★.**

Hoeveel anagrammen (herschikkingen van de letters, zinvol of niet) heeft het woord orange ? En banana ?

**Oplossing van Oefening 2.2.**

orange heeft $6$ verschillende letters: $6! = 720$ anagrammen. banana heeft $6$ letters met herhalingen ($3$ a’s, $2$ n’s, $1$ b): elk anagram ligt vast door de posities van de a’s ($\binom 63$ keuzes) en dan van de n’s onder de $3$ overblijvende plaatsen ($\binom
32$), waarbij de b de laatste plaats krijgt: $\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60$ anagrammen (equivalent: $6!/(3!\,2!\,1!) = 60$).

**Oefening 2.3 ★.**

Uit $7$ vrouwen en $5$ mannen wordt een commissie van $4$ personen gekozen. Hoeveel commissies zijn er in totaal? Hoeveel met precies $2$ vrouwen? Hoeveel met minstens één man?

**Oplossing van Oefening 2.3.**

In totaal: $\binom{12}{4} = 495$. Precies $2$ vrouwen: kies ze ($\binom 72 = 21$) en $2$ mannen ($\binom 52 = 10$): $210$ commissies. Minstens één man: het complement van “geen enkele man”, $\binom{12}{4} - \binom{7}{4} = 495 - 35 = 460$.

**Oefening 2.4 ★.**

Bewijs dat in elke groep van $13$ personen twee in dezelfde maand jarig zijn, en dat onder $n + 1$ getallen gekozen uit $\intint{1}{2n}$ er twee opeenvolgend zijn. *(Beide keren het duivenhokprincipe: benoem de hokken.)*

**Oplossing van Oefening 2.4.**

*Verjaardagen:* de hokken zijn de $12$ maanden; $13$ personen in $12$ hokken dwingen er twee in hetzelfde hok ([Gevolg 2.3](#cor-b1-counting-pigeonhole)).

*Opeenvolgende getallen:* de hokken zijn de $n$ paren $\{1,2\},
\{3,4\}, \dots, \{2n-1, 2n\}$, die $\intint{1}{2n}$ partitioneren. Kies je $n + 1$ getallen, dan belanden er twee in hetzelfde paar, en de twee elementen van een paar zijn opeenvolgend.

**Oefening 2.5 ★.**

Bereken $\sum_{k=0}^{n} k \binom{n}{k}$. *Aanwijzing: differentieer $(1 + x)^n$, of gebruik $k \binom nk = n \binom{n-1}{k-1}$ (bewijs dat).*

**Oplossing van Oefening 2.5.**

Voor $1 \leq k \leq n$ is

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

Sommeren en herindexeren met $j = k - 1$ geeft

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

volgens [Propositie 2.15](#prop-b1-counting-identities). (Alternatief: differentieer $(1+x)^n = \sum_k \binom nk x^k$ en stel $x = 1$.)

**Oefening 2.6 ★★.**

Hoeveel strikt stijgende [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) zijn er van $\intint{1}{k}$ naar $\intint{1}{n}$? Leid daaruit het aantal stijgende (niet noodzakelijk strikt stijgende) [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) af. *Aanwijzing voor de tweede telling: $f$ stijgend $\mapsto$ $g(i) = f(i) + i - 1$.*

**Oplossing van Oefening 2.6.**

Een strikt stijgende [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) $f \colon \intint{1}{k} \to
\intint{1}{n}$ ligt vast door haar beeld, een $k$-deelverzameling van $\intint{1}{n}$ (som de deelverzameling in stijgende volgorde op); omgekeerd levert elke $k$-deelverzameling precies één zo’n [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map). Er zijn dus $\binom nk$ strikt stijgende [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map).

Is $f$ alleen stijgend, zet dan $g(i) = f(i) + i - 1$. Dan is $g$ strikt stijgend (tussen opeenvolgende argumenten wint $f$ minstens $0$ en wint $i - 1$ precies $1$) met waarden in $\intint{1}{n + k - 1}$; en $f(i) =
g(i) - i + 1$ haalt $f$ terug uit elke strikt stijgende $g$ in $\intint{1}{n+k-1}$. Dit is een bijectie, dus zijn er $\binom{n + k -
1}{k}$ stijgende [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map).

**Oefening 2.7 ★★.**

(Vandermonde) Bewijs, door de $k$-deelverzamelingen te tellen van een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) die in twee blokken van grootte $m$ en $n$ gesplitst is:

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

Leid daaruit $\sum_{j=0}^{n} \binom nj^2 = \binom{2n}{n}$ af.

**Oplossing van Oefening 2.7.**

Splits een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) $E$ met $m + n$ elementen in blokken $M$ ($m$ elementen) en $N$ ($n$ elementen). Een $k$-deelverzameling van $E$ bevat zekere $j$ elementen van $M$ ($0 \leq j \leq k$) en $k - j$ van $N$; bij vaste $j$ zijn er $\binom mj \binom{n}{k-j}$ zulke deelverzamelingen, en de gevallen $j = 0, \dots, k$ partitioneren de $k$-deelverzamelingen. De somregel levert 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$, wegens $\binom{n}{n-j} =
\binom nj$.

**Oefening 2.8 ★★.**

Hoeveel getallen uit $\intint{1}{1000}$ zijn deelbaar door $2$ of $3$ of $5$? (Inclusie-exclusie; $\lfloor 1000/6 \rfloor$ telt de veelvouden van $6$, enzovoort.)

**Oplossing van Oefening 2.8.**

Zij $A_d$ de [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) van de veelvouden van $d$ in $\intint{1}{1000}$, zodat $\abs{A_d} = \lfloor 1000/d \rfloor$. Inclusie-exclusie ([Stelling 2.24](#thm-b1-counting-inclexcl)) met $A_2, A_3, A_5$, waarbij $A_2 \cap
A_3 = A_6$ enzovoort:

$$
500 + 333 + 200 - 166 - 100 - 66 + 33 = 734 .
$$

Er zijn dus $734$ getallen deelbaar door $2$, $3$ of $5$.

**Oefening 2.9 ★★.**

Tel de surjecties van een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) met $4$ elementen op een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) met $2$ elementen, en vervolgens op een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) met $3$ elementen. *Aanwijzing: tel de [niet-surjectieve](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) met inclusie-exclusie op de gemiste waarden.*

**Oplossing van Oefening 2.9.**

Op $2$ elementen: alle $2^4 = 16$ [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) behalve de $2$ constante: $14$ surjecties.

Op $3$ elementen: met inclusie-exclusie op de gemiste waarden is het aantal [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) van een [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) met $4$ elementen naar een met $3$ elementen die minstens één waarde missen gelijk aan $\binom 31 2^4 -
\binom 32 1^4 = 48 - 3 = 45$; in totaal zijn er $3^4 = 81$ [afbeeldingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map), dus $81 - 45 = 36$ surjecties. (Controle: een surjectie van $4$ op $3$ elementen verdubbelt precies één waarde: kies die waarde ($3$), het paar dat erop wordt afgebeeld ($\binom 42 = 6$) en een bijectie voor de rest ($2$): $3 \times 6 \times 2 = 36$.)

**Oefening 2.10 ★★.**

(Sterren en staven) Bewijs dat het aantal $k$-keuzes uit $n$ objecten *met* herhaling en zonder volgorde — equivalent: het aantal $(x_1, \dots, x_n) \in \N^n$ met $x_1 + \dots + x_n = k$ — gelijk is aan $\binom{n + k - 1}{k}$. *Aanwijzing: codeer een oplossing als een rij van $k$ sterren en $n - 1$ staven.*

**Oplossing van Oefening 2.10.**

Een oplossing van $x_1 + \dots + x_n = k$ in $\N^n$ codeert als een rij van $k$ sterren en $n - 1$ staven: schrijf $x_1$ sterren, een staaf, $x_2$ sterren, een staaf, …, en [eindig](#def-b1-counting-card) met $x_n$ sterren. Dit is een bijectie op de woorden van lengte $k + n - 1$ met $k$ sterren en $n - 1$ staven, en die woorden liggen vast door de posities van de sterren: $\binom{n + k - 1}{k}$. Keuzes met herhaling komen overeen met oplossingen van de vergelijking ($x_i$ = aantal exemplaren van object $i$), zodat de telling dezelfde is.

**Oefening 2.11 ★★★.**

Bewijs de formule van [Voorbeeld 2.26](#ex-b1-counting-derangement) voor $D_n$ in detail, en leid daaruit $n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$ af (bewijs die identiteit ook rechtstreeks door de [permutaties](#def-b1-counting-objects) in te delen naar hun [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) vaste punten).

**Oplossing van Oefening 2.11.**

Met $A_i = \{\sigma : \sigma(i) = i\}$ houdt een [permutatie](#def-b1-counting-objects) in $\bigcap_{i \in I} A_i$ elke $i \in I$ vast en permuteert ze de overige $n - \abs I$ punten vrij: $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$. Inclusie-exclusie geeft

$$
\Bigl|\bigcup_i A_i\Bigr|
= \sum_{k=1}^{n} (-1)^{k+1} \binom nk (n-k)!
= \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!} ,
$$

want er zijn $\binom nk$ deelverzamelingen $I$ van grootte $k$. Bijgevolg is

$$
D_n = n! - \Bigl|\bigcup_i A_i\Bigr|
= n!\Bigl(1 - \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!}\Bigr)
= n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .
$$

Voor de tweede identiteit: deel de [permutaties](#def-b1-counting-objects) $\sigma$ van $\intint{1}{n}$ in naar hun [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) vaste punten $F(\sigma)$. Bij een vaste $k$-deelverzameling $F$ zijn de [permutaties](#def-b1-counting-objects) met $F(\sigma) = F$ precies de derangementen van het complement: $D_{n-k}$ stuks. Sommeren over de $\binom nk$ keuzes van $F$ voor elke $k$ geeft $n! =
\sum_{k=0}^{n} \binom nk D_{n-k}$.

**Oefening 2.12 ★★★.**

Bewijs voor $n \in \N^*$, met een dubbeltelling van de paren (deelverzameling, gemarkeerd element):

$$
\sum_{k=1}^{n} k \binom{n}{k} = n\, 2^{n-1},
\qquad\text{en vervolgens}\qquad
\sum_{k=1}^{n} k^2 \binom{n}{k} = n(n+1)\, 2^{n-2} .
$$

*Voor de tweede: tel paren gemarkeerde elementen, gelijk of niet.*

**Oplossing van Oefening 2.12.**

*Eerste identiteit.* Tel de paren $(A, a)$ met $A \subseteq E$ ($\abs E = n$) en $a \in A$. Naar de grootte van $A$: $\sum_k \binom nk
k$ paren. Door eerst het gemarkeerde element te kiezen: $n$ keuzes voor $a$, en dan een willekeurige deelverzameling van de overige $n - 1$ elementen om $A$ af te maken: $n\,2^{n-1}$ paren.

*Tweede identiteit.* Tel de drietallen $(A, a, b)$ met $a, b \in A$ (eventueel $a = b$). Naar de grootte: $\sum_k k^2 \binom nk$. Rechtstreeks: ofwel $a = b$ ($n\,2^{n-1}$ drietallen, vorige telling), ofwel $a \neq b$ ($n(n-1)$ geordende keuzes, dan een willekeurige deelverzameling van de andere $n - 2$ elementen: $n(n-1)\,2^{n-2}$). In totaal

$$
n\,2^{n-1} + n(n-1)\,2^{n-2} = n\,2^{n-2}\,(2 + n - 1)
= n(n+1)\,2^{n-2} .
$$

## 2.6 Opgave: derangementen, of de verkeerd geadresseerde brieven

**Probleem 2.1.**

Een secretaresse stopt $n$ brieven willekeurig in $n$ geadresseerde enveloppen: hoe groot is de kans dat *niemand* de juiste brief krijgt? Deze klassieke vraag (Montmort, 1708) voert naar de derangementengetallen $D_n$ van [Voorbeeld 2.26](#ex-b1-counting-derangement). De formule van de inclusie-exclusie is slechts de openingszet: deze opgave ontwikkelt de recursies die $D_n$ berekenen, twee verdere onafhankelijke bewijzen van de formule, de opvallende stelling dat $D_n$ het gehele getal is dat het dichtst bij $n!/\eu$ ligt, de volledige verdeling van de vaste punten van een willekeurige [permutatie](#def-b1-counting-objects), en de merkwaardige rekenkunde van de rij $(D_n)$. Overal noteert $D_n$ het aantal derangementen ([permutaties](#def-b1-counting-objects) zonder vaste punten) van $\intint1n$, met de afspraak $D_0 = 1$ (de lege [permutatie](#def-b1-counting-objects) heeft geen vast punt).

**Deel I — Kleine gevallen en de telling van de vaste punten.**

1. Bereken $D_1, D_2, D_3$ rechtstreeks, en $D_4$ door de derangementen van $\{1, 2, 3, 4\}$ op te sommen, gegroepeerd naar de waarde van $\sigma(1)$ . (Je vindt $D_4 = 9$ .)
2. Toon voor $0 \leq k \leq n$ aan dat het aantal $P_k(n)$ van de [permutaties](#def-b1-counting-objects) van $\intint1n$ met *precies* $k$ vaste punten gelijk is aan $\binom nk D_{n-k}$ .
3. Ga de telling na voor $n = 4$ : bereken $P_0(4), \dots, P_4(4)$ en controleer dat hun som $4! = 24$ is. Wat is bij vier brieven waarschijnlijker: geen enkele match, of precies één?
4. Toon met een dubbeltelling ([Methode 2.22](#met-b1-counting-doublecount)) van de paren $(\sigma, i)$ met $\sigma(i) = i$ aan dat $$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$$ gemiddeld heeft een willekeurige [permutatie](#def-b1-counting-objects) *precies één* vast punt, wat $n \geq 1$ ook is.

**Deel II — Twee recursies en twee nieuwe bewijzen van de formule.**

5. Bewijs combinatorisch, voor $n \geq 1$: $$D_{n+1} = n\,(D_n + D_{n-1}) .$$ (Deel de derangementen $\sigma$ van $\intint1{n+1}$ in naar $j =  \sigma(n+1)$, en vervolgens naar de vraag of $\sigma(j) = n +  1$; bouw in het geval $\sigma(j) \neq n+1$ een bijectie met de derangementen van $\intint1n$ door het [origineel](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) van $n + 1$ naar $j$ om te leiden.) Controleer de recursie numeriek tot en met $D_6$.
6. Zet $u_n = D_n - n D_{n-1}$ en leid uit vraag 5 af dat $u_{n+1}  = -u_n$; besluit met de tweede recursie: $$D_n = n D_{n-1} + (-1)^n \qquad (n \geq 1).$$
7. Bewijs met inductie uit vraag 6 de formule van [Voorbeeld 2.26](#ex-b1-counting-derangement), $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!},$$ — een bewijs dat volledig losstaat van de inclusie-exclusie.
8. (Binomiale inversie) Zij $(a_n)$ en $(b_n)$ twee rijen met $a_n  = \sum_{k=0}^n \binom nk b_k$ voor alle $n$. Bewijs dat $$b_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k  \qquad (n \in \N).$$ (Stel eerst de *trinomiale herschikking* $\binom nk \binom  kj = \binom nj \binom{n-j}{k-j}$ vast en gebruik dan de alternerende rijsom uit [Voorbeeld 2.17](#ex-b1-counting-binomial).)
9. Pas vraag 8 toe op de identiteit $n! = \sum_k \binom nk D_{n-k}$ uit [Oefening 2.11](#exo-b1-counting-11) om een *derde* bewijs van de formule voor $D_n$ te krijgen.

**Deel III — Het gehele getal het dichtst bij $n!/\eu$.** Neem voor dit deel aan — de theorie wordt opgebouwd in [Hoofdstuk 17](https://one-course.com/books/math/3/nl/chapter/17-getallenreeksen#ch-b1-series) — dat $\eu^{-1} = \lim_{n \to \infty} s_n$ met $s_n = \sum_{k=0}^{n} \frac{(-1)^k}{k!}$, met de strikte afschatting $\abs{\eu^{-1} - s_n} < \frac1{(n+1)!}$ voor alternerende reeksen, geldig voor elke $n$.

10. Toon aan dat $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ voor alle $n \in \N$ .
11. Leid de hoofdstelling af: *voor elke $n \geq 1$ is $D_n$ het gehele getal dat het dichtst bij $n!/\eu$ ligt* . Waarom heeft het argument $n \geq 1$ nodig?
12. Bepaal het teken van de fout: toon aan dat $D_n > n!/\eu$ precies wanneer $n$ even is. (Zoek de eerste verwaarloosde term van de alternerende reeks.)
13. Bereken $D_7$ tot en met $D_{10}$ met de recursie van vraag 5 en toets $D_{10}$ vervolgens aan $10!/\eu$ ( $10! =  3\,628\,800$ , $\eu \approx 2.718281828$ ).
14. (De garderobekans) Zij $p_n = D_n/n!$ de kans dat een uniform willekeurige [permutatie](#def-b1-counting-objects) een derangement is. Toon aan dat $\abs{p_n - \eu^{-1}} < \frac1{(n+1)!}$ en bereken $p_6$ tot op vijf decimalen. Verklaar: waarom is het antwoord op Montmorts vraag in wezen onafhankelijk van $n$ — al bij een dozijn brieven?

**Deel IV — De verdeling van de vaste punten.**

15. Leg $k \in \N$ vast. Toon aan dat het aandeel van de [permutaties](#def-b1-counting-objects) van $\intint1n$ met precies $k$ vaste punten voldoet aan $$\frac{P_k(n)}{n!} = \frac{s_{n-k}}{k!}  \;\xrightarrow[n \to \infty]{}\; \frac{\eu^{-1}}{k!} .$$ (Deze limietwaarden, die samen $1$ opleveren, vormen de *poissonverdeling* met parameter $1$, een centraal object van de cursus kansrekening in het volume van bachelorjaar 2.)
16. Toon met een dubbeltelling van de drietallen $(\sigma, i, j)$ waarin $i \neq j$ beide door $\sigma$ vastgehouden worden aan dat $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}\,  (\abs{\mathrm{Fix}(\sigma)} - 1) = n!$ voor $n \geq 2$ . Samen met vraag 4: het gemiddelde van $\abs{\mathrm{Fix}}^2$ is $2$ , zodat de “spreiding” (variantie) van het aantal vaste punten gelijk is aan $1$ — opnieuw onafhankelijk van $n$ , opnieuw in overeenstemming met de poissonverdeling.
17. Bereken het aandeel van de [permutaties](#def-b1-counting-objects) met minstens één vast punt voor $n = 4, 5, 6$ (als breuk en tot op vier decimalen) en vergelijk met $1 - \eu^{-1} \approx 0.6321$ .
18. Toon rechtstreeks — zonder limieten — aan dat $s_{n+2} - s_n  = (-1)^{n+1}\bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\bigr)$ , en leid daaruit af dat de kansen $p_n = s_n$ van vraag 14 oscilleren: $p_0 > p_2 > p_4 > \dots$ en $p_1 < p_3 < p_5 <  \dots$ , waarbij de even (respectievelijk oneven) waarden dalen (respectievelijk stijgen) naar de gemeenschappelijke limiet $\eu^{-1}$ .
19. (Lootjes trekken) $n$ personen trekken elk één naam uit een hoed; trekt iemand zijn eigen naam, dan wordt de *hele* trekking overgedaan. Schat, met het standaardfeit dat een gebeurtenis met kans $p$ gemiddeld $1/p$ pogingen kost, het gemiddelde aantal volledige trekkingen, en besluit dat de procedure gemiddeld ongeveer $\eu \approx 2.72$ trekkingen kost, in wezen onafhankelijk van $n$ .

**Deel V — De rekenkunde van $D_n$, en een synthese.**

20. Verfijn vraag 5: toon aan dat er voor vaste $j \in \intint2n$ precies $D_{n-1} + D_{n-2}$ derangementen van $\intint1n$ met $\sigma(1) = j$ zijn, onafhankelijk van $j$ . Leid af dat $n - 1$ het getal $D_n$ deelt voor elke $n \geq 2$ .
21. Bewijs dat $D_n$ oneven is dan en slechts dan als $n$ even is. (Werk modulo $2$ in de recursie van vraag 6.)
22. Bewijs dat $D_n \equiv (-1)^n \pmod n$ voor $n \geq 1$ , en controleer de congruentie op het laatste cijfer van $D_{10}$ .
23. Toon met vraag 6 aan dat $\dfrac{D_n}{D_{n-1}} = n +  \dfrac{(-1)^n}{D_{n-1}}$ voor $n \geq 3$ , zodat de verhouding van opeenvolgende derangementengetallen *vrijwel exact* $n$ is; leg in één zin uit waarom dat strookt met $D_n \approx  n!/\eu$ .
24. Waar precies gebruikte deze opgave: (i) de product- en de somregel; (ii) het dubbeltellen; (iii) het binomium; (iv) de aangenomen afschatting voor alternerende reeksen? Eén zin per onderdeel.
25. Synthese. De formule voor $D_n$ heeft nu drie bewijzen (inclusie-exclusie, recursie met inductie, binomiale inversie). Vergelijk in een korte alinea wat elk bewijs *verklaart* : welk bewijs rekent het snelst, welk veralgemeent naar andere tellingen van vaste punten, en welk onthult waarom $\eu$ opduikt in een probleem over enveloppen.

**Oplossing van Probleem 2.1.**

**1.** $D_1 = 0$ (de enige [permutatie](#def-b1-counting-objects) houdt $1$ vast), $D_2 = 1$ (de verwisseling), $D_3 = 2$ (in eenregelige notatie: $231$ en $312$). Voor $n = 4$, gegroepeerd naar $\sigma(1)$: met $\sigma(1) = 2$ zijn de derangementen $2143$, $2341$, $2413$; met $\sigma(1) = 3$: $3142$, $3412$, $3421$; met $\sigma(1) = 4$: $4123$, $4312$, $4321$. Drie per groep: $D_4 = 9$.

**2.** Een [permutatie](#def-b1-counting-objects) met precies $k$ vaste punten ligt vast door de keuze van haar [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) vaste punten $F$ ($\binom nk$ manieren) samen met haar beperking tot het complement, die een [permutatie](#def-b1-counting-objects) van $n - k$ punten *zonder* vast punt moet zijn ($D_{n-k}$ manieren). De twee keuzes zijn onafhankelijk en de overeenkomst is [bijectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj): $P_k(n) =
\binom nk D_{n-k}$.

**3.** $P_0(4) = D_4 = 9$; $P_1(4) = \binom41 D_3 = 4 \times 2 =
8$; $P_2(4) = \binom42 D_2 = 6$; $P_3(4) = \binom43 D_1 = 0$ (drie vaste punten dwingen een vierde af); $P_4(4) = 1$. Som: $9 + 8 + 6 + 0 + 1 =
24 = 4!$. Geen enkele match ($9$ gevallen) wint het — nipt — van precies één match ($8$ gevallen).

**4.** Tel de paren $(\sigma, i)$ met $\sigma(i) = i$. Bij vaste $i$ zijn de [permutaties](#def-b1-counting-objects) die $i$ vasthouden de [permutaties](#def-b1-counting-objects) van de overige $n - 1$ punten: $(n-1)!$ stuks. Het aantal paren is dus $n \cdot (n-1)! =
n!$, en dat aantal is ook $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}$. Deling door het aantal $n!$ [permutaties](#def-b1-counting-objects) geeft: het gemiddelde aantal vaste punten is precies $1$, voor elke $n \geq 1$.

**5.** Zij $\sigma$ een derangement van $\intint1{n+1}$ en $j =
\sigma(n+1) \in \intint1n$: $n$ mogelijke waarden. *Geval $\sigma(j)
= n+1$:* de punten $j$ en $n+1$ verwisselen, en $\sigma$ beperkt tot de overige $n - 1$ punten is een willekeurig derangement daarvan: $D_{n-1}$ mogelijkheden. *Geval $\sigma(j) \neq n+1$:* zij $i_0 =
\sigma^{-1}(n+1)$; hier is $i_0 \neq j$ en $i_0 \leq n$. Definieer $\tau$ op $\intint1n$ door $\tau(i) = \sigma(i)$ voor $i \neq i_0$ en $\tau(i_0) = j$. Dan is $\tau$ een [permutatie](#def-b1-counting-objects) van $\intint1n$ (de waarde $n+1$ is vervangen door de ontbrekende waarde $j$), en wel een derangement: $\tau(i_0) = j \neq i_0$, en elders $\tau(i) = \sigma(i)
\neq i$. Omgekeerd haal je uit een derangement $\tau$ van $\intint1n$ en de waarde $j$ de [permutatie](#def-b1-counting-objects) $\sigma$ terug door $\sigma(n+1) = j$, $\sigma(\tau^{-1}(j)) = n+1$ en elders $\sigma = \tau$ te stellen: een bijectie, goed voor $D_n$ mogelijkheden. Sommeren over $j$ geeft $D_{n+1} = n(D_n + D_{n-1})$. Numeriek: $D_5 = 4(9 + 2) = 44$ en $D_6 =
5(44 + 9) = 265$.

**6.** Uit vraag 5 volgt $D_{n+1} = nD_n + nD_{n-1}$, dus

$$
u_{n+1} = D_{n+1} - (n+1)D_n = nD_n + nD_{n-1} - (n+1)D_n
= -(D_n - nD_{n-1}) = -u_n .
$$

Omdat $u_1 = D_1 - 1 \cdot D_0 = -1$, geeft inductie $u_n = (-1)^n$, oftewel $D_n = nD_{n-1} + (-1)^n$ voor $n \geq 1$.

**7.** Inductie naar $n$. Basis: $D_0 = 1 = 0!\,s_0$. Stap: neem $D_{n-1} = (n-1)!\,s_{n-1}$ aan, dan is

$$
D_n = nD_{n-1} + (-1)^n = n!\,s_{n-1} + (-1)^n
= n!\Bigl(s_{n-1} + \frac{(-1)^n}{n!}\Bigr) = n!\,s_n ,
$$

en dat is de formule. Er kwam geen inclusie-exclusie aan te pas: alleen de combinatorische recursie van vraag 5.

**8.** Trinomiale herschikking, via faculteiten:

$$
\binom nk \binom kj
= \frac{n!}{k!\,(n-k)!} \cdot \frac{k!}{j!\,(k-j)!}
= \frac{n!}{j!\,(n-j)!} \cdot \frac{(n-j)!}{(k-j)!\,(n-k)!}
= \binom nj \binom{n-j}{k-j} .
$$

Substitueer nu $a_k = \sum_j \binom kj b_j$ en verwissel de twee eindige sommen:

$$
\sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k
= \sum_{j=0}^{n} b_j \binom nj
\sum_{k=j}^{n} (-1)^{n-k} \binom{n-j}{k-j}
= \sum_{j=0}^{n} b_j \binom nj
\sum_{i=0}^{n-j} (-1)^{(n-j)-i} \binom{n-j}{i} .
$$

De binnenste som is de ontwikkeling van $(1 + (-1))^{n-j} = 0^{n-j}$ (binomium, [Stelling 2.16](#thm-b1-counting-binomial)): ze is nul voor $j < n$ en gelijk aan $1$ voor $j = n$. Alleen $j = n$ overleeft, en het rechterlid is $b_n$, zoals beweerd.

**9.** Wegens de symmetrie $\binom nk = \binom n{n-k}$ luidt de identiteit van [Oefening 2.11](#exo-b1-counting-11) ook $n! = \sum_{k=0}^n \binom nk
D_k$. Pas vraag 8 toe met $a_n = n!$ en $b_k = D_k$:

$$
D_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk k!
= \sum_{k=0}^{n} (-1)^{n-k} \frac{n!}{(n-k)!}
= n! \sum_{j=0}^{n} \frac{(-1)^j}{j!} ,
$$

na herindexering met $j = n - k$: de formule voor de derde keer.

**10.** Er geldt $D_n = n!\,s_n$ (vraag 7), dus

$$
\Bigl| D_n - \frac{n!}{\eu} \Bigr|
= n!\,\abs{s_n - \eu^{-1}} < \frac{n!}{(n+1)!} = \frac1{n+1} .
$$

**11.** Voor $n \geq 1$ is $\frac1{n+1} \leq \frac12$, en de ongelijkheid van vraag 10 is strikt: $D_n$ ligt op afstand $< \frac12$ van $n!/\eu$ en is dus het unieke dichtstbijzijnde gehele getal. Voor $n
= 0$ geeft de grens alleen afstand $< 1$, en daar faalt de bewering inderdaad: $0!/\eu \approx 0.368$ heeft $0$ als dichtstbijzijnde gehele getal, terwijl $D_0 = 1$.

**12.** $\eu^{-1} - s_n = \sum_{k \geq n+1} (-1)^k/k!$ is een alternerende reeks met strikt dalende termen, zodat haar teken dat van haar eerste term $(-1)^{n+1}/(n+1)!$ is. Bijgevolg heeft $s_n - \eu^{-1}$ het teken van $(-1)^n$: voor even $n$ is $s_n > \eu^{-1}$ en $D_n =
n!\,s_n > n!/\eu$; voor oneven $n$ is $D_n < n!/\eu$.

**13.** $D_7 = 6(265 + 44) = 6 \times 309 = 1854$; $D_8 = 7(1854 +
265) = 7 \times 2119 = 14\,833$; $D_9 = 8(14\,833 + 1854) = 8 \times
16\,687 = 133\,496$; $D_{10} = 9(133\,496 + 14\,833) = 9 \times 148\,329
= 1\,334\,961$. Controle: $10!/\eu = 3\,628\,800 / 2.718281828 \approx
1\,334\,960.92$, met $1\,334\,961$ als dichtstbijzijnde gehele getal — en $D_{10} > 10!/\eu$, zoals vraag 12 voor even $n$ voorspelt.

**14.** $\abs{p_n - \eu^{-1}} = \abs{s_n - \eu^{-1}} <
\frac1{(n+1)!}$. Voor $n = 6$: $p_6 = 265/720 = 0.36806$ (vijf decimalen), tegenover $\eu^{-1} = 0.36788$; het verschil blijft onder $1/7! = 1/5040 < 2 \times 10^{-4}$. De grens $1/(n+1)!$ stort zo snel in dat de kans al bij een dozijn brieven tot op vele decimalen vastligt: het antwoord “ongeveer $36.8\%$” is voor elk praktisch doel onafhankelijk van $n$ — de beroemde verrassing van deze opgave.

**15.** Met vraag 2 en $D_m = m!\,s_m$:

$$
\frac{P_k(n)}{n!} = \frac{\binom nk D_{n-k}}{n!}
= \frac{D_{n-k}}{k!\,(n-k)!} = \frac{s_{n-k}}{k!}
\;\longrightarrow\; \frac{\eu^{-1}}{k!}
$$

als $n \to \infty$ bij vaste $k$, want $s_{n-k} \to \eu^{-1}$. De limietwaarden $\eu^{-1}/k!$ ($k \in \N$) zijn de gewichten van de poissonverdeling met parameter $1$.

**16.** Tel de drietallen $(\sigma, i, j)$ met $i \neq j$, $\sigma(i) = i$ en $\sigma(j) = j$. Kies je eerst het geordende paar: $n(n-1)$ manieren; de [permutaties](#def-b1-counting-objects) die zowel $i$ als $j$ vasthouden zijn de [permutaties](#def-b1-counting-objects) van de overige $n - 2$ punten: $(n-2)!$ stuks. In totaal $n(n-1)(n-2)! = n!$. Sommeer je in plaats daarvan eerst over $\sigma$, dan tel je per $\sigma$ de geordende paren verschillende vaste punten: $\abs{\mathrm{Fix}(\sigma)}(\abs{\mathrm{Fix}(\sigma)}-1)$. Daarmee is de identiteit bewezen; na deling door $n!$ is het gemiddelde van $\abs{\mathrm{Fix}}(\abs{\mathrm{Fix}} - 1)$ gelijk aan $1$, zodat het gemiddelde van $\abs{\mathrm{Fix}}^2$ gelijk is aan $1 + 1 = 2$ en de variantie aan $2 - 1^2 = 1$.

**17.** De aandelen $1 - p_n$: voor $n = 4$ is $1 - \frac 9{24} =
\frac{15}{24} = 0.6250$; voor $n = 5$ is $1 - \frac{44}{120} =
\frac{76}{120} = 0.6333$; voor $n = 6$ is $1 - \frac{265}{720} =
\frac{455}{720} = 0.6319$. Alle drie liggen binnen een procent van $1 -
\eu^{-1} \approx 0.6321$ en oscilleren eromheen.

**18.** Rechtstreeks:

$$
s_{n+2} - s_n = \frac{(-1)^{n+1}}{(n+1)!} +
\frac{(-1)^{n+2}}{(n+2)!}
= (-1)^{n+1}\Bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\Bigr),
$$

en het haakje is $> 0$. Voor even $n$ is het verschil negatief: $s_{n+2} < s_n$, dus $p_0 > p_2 > p_4 > \dots$; voor oneven $n$ is het positief: $p_1 < p_3 < p_5 < \dots$ Samen met vraag 12 (even boven $\eu^{-1}$, oneven eronder) en vraag 14 (de afstand tot $\eu^{-1}$ gaat naar $0$): de twee trappen klemmen $\eu^{-1}$ tussen zich in.

**19.** Eén volledige trekking is een uniform willekeurige [permutatie](#def-b1-counting-objects), en ze is geldig wanneer het een derangement is: kans $p_n
\approx \eu^{-1}$. Volgens het aangehaalde feit is het gemiddelde aantal trekkingen tot succes gelijk aan $1/p_n$, en vraag 14 geeft $1/p_n
\approx \eu$ op een fout na die al voor kleine $n$ verwaarloosbaar is. Lootjes trekken met herstart kost dus gemiddeld ongeveer $\eu \approx
2.72$ volledige trekkingen — of het kantoor nu $6$ of $600$ mensen telt.

**20.** Leg $j \geq 2$ vast en pas de indeling van vraag 5 toe op de waarde $\sigma(1) = j$. Is $\sigma(j) = 1$, dan dragen de overige $n - 2$ punten een willekeurig derangement: $D_{n-2}$ manieren. Is $\sigma(j)
\neq 1$, leid dan het [origineel](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) $i_0 = \sigma^{-1}(1)$ precies als in vraag 5 om naar $j$; dit is een bijectie met de derangementen van de $n -
1$ punten $\{2, \dots, n\}$: $D_{n-1}$ manieren. In totaal $D_{n-1} +
D_{n-2}$, voor elke $j$ hetzelfde. Sommeren over de $n - 1$ waarden van $j$ geeft $D_n = (n-1)(D_{n-1} + D_{n-2})$, waarin de factor $n - 1$ zichtbaar is: $(n-1) \mid D_n$.

**21.** Bewering: $D_n$ is oneven dan en slechts dan als $n$ even is. Inductie met $D_n = nD_{n-1} + (-1)^n$, oftewel $D_n \equiv nD_{n-1}
+ 1 \pmod 2$. Basis: $D_1 = 0$ is even en $n = 1$ is oneven, dus de bewering klopt. Is $n$ even, dan is $nD_{n-1}$ even en $D_n \equiv 1$: oneven, zoals beweerd. Is $n$ oneven, dan is $n - 1$ even, dus $D_{n-1}$ oneven volgens de hypothese, en $D_n \equiv D_{n-1} + 1 \equiv 0$: even. Daarmee sluit de inductie.

**22.** Reduceren we $D_n = nD_{n-1} + (-1)^n$ modulo $n$, dan valt de eerste term weg: $D_n \equiv (-1)^n \pmod n$. Voor $n = 10$ is $(-1)^{10} = 1$, en inderdaad eindigt $D_{10} = 1\,334\,961$ op het cijfer $1$.

**23.** Voor $n \geq 3$ is $D_{n-1} \geq 1$, en deling van de recursie van vraag 6 door $D_{n-1}$ geeft $D_n/D_{n-1} = n +
(-1)^n/D_{n-1}$, met $\abs{(-1)^n/D_{n-1}} \leq 1$ en snel naar $0$ gaand. Dat strookt: is $D_n \approx n!/\eu$, dan is $D_n/D_{n-1} \approx
n!/(n-1)! = n$ — de factor $\eu$ valt in de verhouding weg, en de recursie bevestigt dat tot op $1/D_{n-1}$ nauwkeurig.

**24.** (i) De product- en de somregel liggen onder elke telling: de vragen 2 en 5 partitioneren [verzamelingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) [permutaties](#def-b1-counting-objects) in onafhankelijke stappen. (ii) Het dubbeltellen leverde het gemiddelde (vraag 4) en de variantie (vraag 16) van het aantal vaste punten, zonder ook maar één formule voor $D_n$. (iii) Het binomium berekende de alternerende binnenste som $(1-1)^{n-j}$ die de binomiale inversie doet werken (vraag 8). (iv) De afschatting voor alternerende reeksen zette de exacte maar ondoorzichtige som $n!\,s_n$ om in de doorzichtige [uitspraak](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-statement) “het gehele getal het dichtst bij $n!/\eu$” (vragen 10–14).

**25.** De inclusie-exclusie ([Voorbeeld 2.26](#ex-b1-counting-derangement) en [Oefening 2.11](#exo-b1-counting-11)) is het conceptuele bewijs: ze verklaart de alternerende som als opeenvolgende correcties op dubbeltellingen, en ze veralgemeent letterlijk naar het tellen van elementen die een willekeurige familie “slechte” [verzamelingen](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) mijden. De weg via de recursie (vragen 5–7) rekent het snelst — lineaire tijd, exacte gehele rekenkunde, geen faculteiten — en is de bron van de rekenkundige feiten uit Deel V. De binomiale inversie (vragen 8–9) plaatst de formule binnen een algemene transformatie die opduikt waar twee driehoekige stelsels identiteiten tegenover elkaar staan. En dat $\eu$ verschijnt, verklaart de formule zelf het best: het aandeel derangementen is de partiële som $s_n$ van de reeks voor $\eu^{-1}$, zodat Montmorts enveloppen, drie decennia vóór Eulers notatie, al het getal $\eu$ aan het berekenen waren.