Universitaire wiskunde — Bachelor jaar 1 · Bachelor Year 1

2Telkunde

Eindige verzamelingen tellen klinkt elementair — en wordt snel subtiel. Dit hoofdstuk definieert de kardinaliteit zoals het hoort (via bijecties, in de geest van Hoofdstuk 1), stelt de handvol telprincipes vast waaruit al het overige volgt, en leidt daaruit de klassieke tellingen af: lijsten, permutaties, deelverzamelingen, binomiaalcoëfficiënten.

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 $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) 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: 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. Neem de uitspraak 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 $f \colon E \to F$ injectief: 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, dan was $v \circ f \circ u$ een injectie van $\intint1m$ in $\intint1n$ (een samenstelling van injecties, Propositie 1.26), in tegenspraak met Stelling 2.2. ∎

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

Het bewijs van Stelling 2.2 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 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 overal opgelapt in de opgave over de symmetrische groep in Hoofdstuk 7.

Propositie 2.5 (Injecties, surjecties en kardinaliteit)

Zij $E, F$ eindige verzamelingen 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. 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 met kardinaliteit $\abs{F} - 1 < \abs{E}$ — onmogelijk wegens het duivenhokprincipe. Dus $f(E) = F$ : $f$ is surjectief en daarmee bijectief.

Stel $f$ surjectief. Kies bij elke $y \in F$ één origineel $s(y) \in E$ ; dan is $f \circ s = \mathrm{id}_F$ , zodat $s$ injectief is (Propositie 1.26). Volgens de vorige alinea, toegepast op $s$ (de kardinaliteiten zijn gelijk), is $s$ bijectief. Uit $f \circ s = \mathrm{id}_F$ volgt $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$ , dus is $f$ bijectief. Ten slotte is een bijectieve afbeelding per definitie zowel injectief als surjectief, waarmee de kring van implicaties gesloten is. ∎

Voorbeeld 2.6 (Eindigheid is essentieel)

Op een eindige verzameling is Propositie 2.5 een krachtige kortere weg: elke injectieve afbeelding van $E$ naar zichzelf is automatisch een permutatie van $E$ — de helft van de bijectiviteit krijg je gratis. Beide implicaties bezwijken op oneindige verzamelingen: $n \mapsto n + 1$ is injectief van $\N$ naar $\N$ maar mist $0$ , en de afbeelding $\N \to \N$ die $0 \mapsto 0$ en $n \mapsto n - 1$ voor $n \geq 1$ stuurt, is surjectief maar niet injectief. Telkens als deze propositie wordt ingeroepen, doet de eindigheidshypothese echt werk — een thema dat de weekendopgave van Hoofdstuk 1 van de andere kant bekijkt, waar oneindige verzamelingen juist die verzamelingen zijn die zulke afbeeldingen op zichzelf toelaten.

Voorbeeld 2.7 (De helft van het werk, gratis)

Beschouw de afbeelding $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): 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); 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), 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 precies wanneer het surjectief is” (Hoofdstuk 19).

2.2 De telprincipes

Propositie 2.8 (Som- en productregel)

Zij $E, F$ eindige verzamelingen.

Is $E \cap F = \emptyset$ , dan is $\abs{E \cup F} = \abs{E} + \abs{F}$ ; algemener geldt voor een partitie van $E$ in stukken $E_1, \dots, E_k$ dat $\abs{E} = \sum_i \abs{E_i}$ .
In het algemeen is $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap F}$ .
$\abs{E \times F} = \abs{E} \times \abs{F}$ .
De verzameling $F^E$ van alle afbeeldingen van $E$ naar $F$ voldoet aan $\abs{F^E} = \abs{F}^{\abs{E}}$ .
$\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 $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 $\{x\} \times F$ , elk met kardinaliteit $\abs{F}$ ; pas (1) toe.

(4) Een afbeelding 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 overeen met afbeeldingen $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 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 posities — opnieuw een illustratie van de leuze dat een correcte telling een vermomde bijectie is (Methode 2.19).

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. — 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 met $\abs{E} = n$ en zij $0 \leq k \leq n$ .

Een $k$ -variatie van $E$ is een injectief $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$ :

het aantal $k$ -variaties van $E$ is $n (n-1) \cdots (n-k+1) = \dfrac{n!}{(n-k)!}$ ;
het aantal permutaties van $E$ is $n!$ ;
$\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 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 (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 heeft precies de helft een even kardinaliteit.

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 $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)

Ga vervolgens op zoek naar een bijectie of een partitie die het probleem tot deze modeltellingen herleidt; een correcte telling is een vermomde bijectie.

Opmerking 2.20 (Veelgemaakte fouten bij het tellen)

Niet-disjuncte gevallen optellen. De somregel vergt een partitie; kunnen configuraties aan twee gevallen tegelijk voldoen, dan worden ze dubbel geteld — de remedie is inclusie-exclusie (Stelling 2.24) of een fijnere gevalsindeling.
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.
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.
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).

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 die beide leden tellen — doorgaans een verzameling paren — en bereken je haar kardinaliteit 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 en verscheidene vragen van de weekendopgave hieronder aan.

Voorbeeld 2.23 (De gemiddelde deelverzameling)

Wat is de gemiddelde kardinaliteit van een deelverzameling van een verzameling $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: een goedgekozen koppeling vervangt vaak een identiteit.

2.4 Inclusie-exclusie

Stelling 2.24 (Inclusie-exclusie)

Voor eindige verzamelingen $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 $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. 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 en verder wordt uitgewerkt in het volume van bachelorjaar 2.

Voorbeeld 2.26 (Derangementen)

Een derangement is een permutatie zonder vaste punten. Zij $A_i$ de verzameling van de permutaties 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 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), is ongeveer $37\%$ van alle permutaties een derangement, wat $n$ ook is.

Opmerking 2.27 (Waar dit hoofdstuk gebruikt wordt)

Binomiaalcoëfficiënten zijn de meest hergebruikte objecten van dit hoofdstuk: ze dragen het binomium in Hoofdstuk 8 (ontwikkeling van $(X + a)^n$ ), de formule van Leibniz voor de $n$ -de afgeleide van een product in Hoofdstuk 14, en de coëfficiënten van Taylorontwikkelingen in Hoofdstuk 16. Permutaties keren terug als groep — met het teken, gebouwd op het tellen van inversies — in Hoofdstuk 7, en dat teken definieert op zijn beurt de determinanten in Hoofdstuk 22. 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 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

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

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

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

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

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

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. (Alternatief: differentieer $(1+x)^n = \sum_k \binom nk x^k$ en stel $x = 1$ .)

Oefening 2.6 ★★

Hoeveel strikt stijgende afbeeldingen zijn er van $\intint{1}{k}$ naar $\intint{1}{n}$ ? Leid daaruit het aantal stijgende (niet noodzakelijk strikt stijgende) afbeeldingen af. Aanwijzing voor de tweede telling: $f$ stijgend $\mapsto$ $g(i) = f(i) + i - 1$ .

Oplossing

Oplossing van Oefening 2.6.

Een strikt stijgende afbeelding $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. Er zijn dus $\binom nk$ strikt stijgende afbeeldingen.

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.

Oefening 2.7 ★★

(Vandermonde) Bewijs, door de $k$ -deelverzamelingen te tellen van een verzameling 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

Oplossing van Oefening 2.7.

Splits een verzameling $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

Oplossing van Oefening 2.8.

Zij $A_d$ de verzameling van de veelvouden van $d$ in $\intint{1}{1000}$ , zodat $\abs{A_d} = \lfloor 1000/d \rfloor$ . Inclusie-exclusie (Stelling 2.24) 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 met $4$ elementen op een verzameling met $2$ elementen, en vervolgens op een verzameling met $3$ elementen. Aanwijzing: tel de niet-surjectieve afbeeldingen met inclusie-exclusie op de gemiste waarden.

Oplossing

Oplossing van Oefening 2.9.

Op $2$ elementen: alle $2^4 = 16$ afbeeldingen behalve de $2$ constante: $14$ surjecties.

Op $3$ elementen: met inclusie-exclusie op de gemiste waarden is het aantal afbeeldingen van een verzameling 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, 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

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 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 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 in te delen naar hun verzameling vaste punten).

Oplossing

Oplossing van Oefening 2.11.

Met $A_i = \{\sigma : \sigma(i) = i\}$ houdt een permutatie 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 $\sigma$ van $\intint{1}{n}$ in naar hun verzameling vaste punten $F(\sigma)$ . Bij een vaste $k$ -deelverzameling $F$ zijn de permutaties 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

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. 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, en de merkwaardige rekenkunde van de rij $(D_n)$ . Overal noteert $D_n$ het aantal derangementen (permutaties zonder vaste punten) van $\intint1n$ , met de afspraak $D_0 = 1$ (de lege permutatie heeft geen vast punt).

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

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$ .)
Toon voor $0 \leq k \leq n$ aan dat het aantal $P_k(n)$ van de permutaties van $\intint1n$ met precies $k$ vaste punten gelijk is aan $\binom nk D_{n-k}$ .
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?
Toon met een dubbeltelling (Methode 2.22) van de paren $(\sigma, i)$ met $\sigma(i) = i$ aan dat

$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$

gemiddeld heeft een willekeurige permutatie precies één vast punt, wat $n \geq 1$ ook is.

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

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 van $n + 1$ naar $j$ om te leiden.) Controleer de recursie numeriek tot en met $D_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).$
Bewijs met inductie uit vraag 6 de formule van Voorbeeld 2.26,

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

— een bewijs dat volledig losstaat van de inclusie-exclusie.
(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.)
Pas vraag 8 toe op de identiteit $n! = \sum_k \binom nk D_{n-k}$ uit Oefening 2.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 — 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$ .

Toon aan dat $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ voor alle $n \in \N$ .
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?
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.)
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$ ).
(De garderobekans) Zij $p_n = D_n/n!$ de kans dat een uniform willekeurige permutatie 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.

Leg $k \in \N$ vast. Toon aan dat het aandeel van de permutaties 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.)
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.
Bereken het aandeel van de permutaties 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$ .
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}$ .
(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.

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$ .
Bewijs dat $D_n$ oneven is dan en slechts dan als $n$ even is. (Werk modulo $2$ in de recursie van vraag 6.)
Bewijs dat $D_n \equiv (-1)^n \pmod n$ voor $n \geq 1$ , en controleer de congruentie op het laatste cijfer van $D_{10}$ .
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$ .
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.
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

Oplossing van Probleem 2.1.

1. $D_1 = 0$ (de enige permutatie 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 met precies $k$ vaste punten ligt vast door de keuze van haar verzameling vaste punten $F$ ( $\binom nk$ manieren) samen met haar beperking tot het complement, die een permutatie van $n - k$ punten zonder vast punt moet zijn ( $D_{n-k}$ manieren). De twee keuzes zijn onafhankelijk en de overeenkomst is bijectief: $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 die $i$ vasthouden de permutaties 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 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 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 $\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): 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 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 die zowel $i$ als $j$ vasthouden zijn de permutaties 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, 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 $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 permutaties 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 “het gehele getal het dichtst bij $n!/\eu$ ” (vragen 10–14).

25. De inclusie-exclusie (Voorbeeld 2.26 en Oefening 2.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 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.