Universitaire wiskunde — Bachelor jaar 1 · Bachelor Year 1

2Tellen

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

2.1 Kardinaliteit van eindige verzamelingen

Definitie 2.1 (Eindige verzameling, kardinaliteit)

Voor $n \in \N^*$ schrijven we $\intint{1}{n} = \{1, 2, \dots, n\}$ . Een verzameling $E$ is eindig wanneer $E = \emptyset$ of wanneer er een bijectie is van $\intint{1}{n}$ op $E$ voor een zekere $n \in \N^*$ ; deze $n$ is uniek (Stelling 2.2) en is de kardinaliteit van $E$ , genoteerd $\abs{E}$ (met $\abs{\emptyset} = 0$ ).

Stelling 2.2 (Kardinaliteit is welgedefinieerd)

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

Bewijs. We bewijzen door inductie op $n$ de uitspraak: voor alle $m > n$ is 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 veronderstel dat $f \colon \intint{1}{m} \to \intint{1}{n+1}$ een injectie is met $m > n + 1$ . Als de waarde $n + 1$ niet bereikt wordt, is $f$ een injectie in $\intint{1}{n}$ , wat de inductiehypothese tegenspreekt. Anders geldt $f(a) = n + 1$ voor precies één $a$ ; verwissel $f(a)$ en $f(m)$ (formeel: samenstellen met de transpositie van de twee waarden), zodat de nieuwe injectie $g$ voldoet aan $g(m) = n + 1$ . Dan is de beperking van $g$ tot $\intint{1}{m-1}$ een injectie in $\intint{1}{n}$ met $m - 1 > n$ — opnieuw een tegenspraak. ∎

Gevolg 2.3 (Duiventilprincipe)

Als $\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$ . Als $f$ injectief zou zijn, dan zou $v \circ f \circ u$ een injectie van $\intint1m$ in $\intint1n$ zijn (een samenstelling van injecties, Propositie 1.26), wat Stelling 2.2 tegenspreekt. ∎

Opmerking 2.4 (Intermezzo: waarom de verwisseling in het bewijs van de stelling?)

Het bewijs van Stelling 2.2 bevat de eerste werkelijk vernuftige zet van het hoofdstuk, die het waard is langzaam over te doen. Het obstakel: om de inductiehypothese toe te passen wil men het laatste punt $m$ van het domein en het laatste punt $n+1$ van het doel schrappen, maar $f$ kan een ander punt $a$ naar $n + 1$ sturen, en dan beschadigt het schrappen van het 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 injectiviteit behouden blijft — waarna de lastige waarde $n + 1$ op de onschadelijke positie $m$ staat, en beide schrappingen schoon zijn. Dit patroon van “eerst normaliseren, dan snijden” komt vaker terug: het is hoe de recurrentie voor derangementen $\sigma^{-1}(n+1)$ omleidt in het weekendprobleem van dit hoofdstuk, en hoe permutaties worden bijgesteld doorheen het probleem 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 $f \colon E \to F$ . Dan geldt

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

Bewijs. Veronderstel $f$ injectief. Dan is $f$ een bijectie van $E$ op $f(E)$ , dus $\abs{f(E)} = \abs{E} = \abs{F}$ . Als $f(E)$ een punt $y_0$ van $F$ zou missen, dan zou $f$ een injectie van $E$ in $F \setminus \{y_0\}$ zijn, een verzameling van kardinaliteit $\abs{F} - 1 < \abs{E}$ — onmogelijk volgens het duiventilprincipe. Dus $f(E) = F$ : $f$ is surjectief, en dus bijectief.

Veronderstel $f$ surjectief. Kies voor elke $y \in F$ één origineel $s(y) \in E$ ; dan geldt $f \circ s = \mathrm{id}_F$ , dus $s$ is injectief (Propositie 1.26). Volgens de vorige paragraaf toegepast op $s$ (de kardinaliteiten zijn gelijk) is $s$ bijectief. Uit $f \circ s = \mathrm{id}_F$ krijgen we $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$ , dus $f$ is bijectief. Ten slotte is een bijectieve afbeelding per definitie zowel injectief als surjectief, wat de cyclus van implicaties sluit. ∎

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 vallen weg 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 wanneer deze propositie wordt ingeroepen, doet de eindigheidshypothese echt werk — een thema dat het weekendprobleem van Hoofdstuk 1 vanaf de andere kant verkent, waar oneindige verzamelingen juist die zijn die zulke zelfafbeeldingen toelaten.

Voorbeeld 2.7 (De helft van het werk, gratis)

Beschouw de afbeelding $f$ op $\{0, 1, \dots, 6\}$ die $k$ stuurt naar de rest van $3k$ bij deling door $7$ ; haar waardetabel is

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

Is $f$ een bijectie? Injectiviteit alleen volstaat (Propositie 2.5): als $3k$ en $3k'$ dezelfde rest hebben, dan deelt $7$ het getal $3(k - k')$ , en aangezien $7$ priem is en $3$ niet deelt, deelt het $k - k'$ (lemma van Euclides, hier gebruikt op het niveau van de middelbare school en bewezen in Hoofdstuk 6); met $\abs{k - k'} \leq 6$ dwingt dit $k = k'$ af. Surjectiviteit komt er gratis bij — geen noodzaak om $3k \equiv c$ voor elke $c$ op te lossen, hoewel de tabel bevestigt dat elke waarde precies eenmaal voorkomt. De kortere weg is een werkpaard: hij bewijst de inverteerbaarheid van modulaire vermenigvuldiging (Hoofdstuk 6), drijft de koppeling in de stelling van Wilson aan, en keert terug in de lineaire algebra als “een endomorfisme van een eindigdimensionale ruimte is injectief dan en slechts dan als het surjectief is” (Hoofdstuk 19).

2.2 De telprincipes

Propositie 2.8 (Som- en productregel)

Zij $E, F$ eindige verzamelingen.

Als $E \cap F = \emptyset$ , dan geldt $\abs{E \cup F} = \abs{E} + \abs{F}$ ; algemener, voor een partitie van $E$ in stukken $E_1, \dots, E_k$ , geldt $\abs{E} = \sum_i \abs{E_i}$ .
In het algemeen, $\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) Rijg de opsommingen aaneen: als $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$ op zonder herhaling (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 $\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 van 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$ ; deze correspondentie is een bijectie, en $\abs{F^m} = \abs{F}^m$ volgens (3) en inductie.

(5) Deelverzamelingen van $E$ corresponderen bijectief met afbeeldingen $E \to \{0, 1\}$ (stuur $A$ naar zijn indicatorfunctie); pas (4) toe. ∎

Voorbeeld 2.9 (Tellen via het complement)

Hoeveel $4$ -cijferige pincodes (cijfers $0$ – $9$ , volgorde telt, herhaling toegestaan) bevatten ten minste één herhaald cijfer? Ze rechtstreeks tellen betekent jongleren met de gevallen “precies één paar, twee paren, een drietal, een viertal” — vijf overlappende configuraties. Tel in plaats daarvan het complement: alle codes zijn er $10^4 = 10\,000$ (productregel), de codes met vier verschillende cijfers zijn er $10 \times 9 \times 8 \times 7 = 5\,040$ ( $4$ -schikkingen), dus het antwoord is

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

Bijna de helft van alle pincodes herhaalt een cijfer. Het inzicht: telkens wanneer een telling geformuleerd is met “ten minste” of “niet alle”, probeer het complement eerst — de somregel garandeert dat $\abs{A} = \abs{E} - \abs{\overline A}$ , en het complement is vaak één enkele nette 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 slechts één stap naar rechts (R) of één stap omhoog (U) beweegt. Elk zo’n pad neemt precies $7$ stappen, waarvan $4$ R zijn en $3$ U; omgekeerd beschrijft elk woord van lengte $7$ in de letters R, U met vier R’s precies één pad. De paden corresponderen dus bijectief met de keuzes van de posities van de R’s:

\binom{7}{4} = 35 .

Het inzicht is de codering: de telling werd triviaal op het moment dat elk pad vertaald werd in een woord, d.w.z. een deelverzameling van posities — nog een instantie van de slagzin dat een correcte telling een vermomde bijectie is (Methode 2.19).

Een van de 74 = 35 kortste paden van (0,0) naar (4,3): het getoonde pad codeert het woord RURRURU, d.w.z. de keuze van de posities \1,3,4,6\ voor de letter R onder de zeven stappen. — Een van de $\binom74 = 35$ kortste paden van $(0,0)$ naar $(4,3)$ : het getoonde pad codeert het woord RURRURU, d.w.z. 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 (Schikkingen, permutaties, combinaties)

Zij $E$ een verzameling met $\abs{E} = n$ en zij $0 \leq k \leq n$ .

Een $k$ -schikking van $E$ is een injectief $k$ -tal van elementen van $E$ (een geordende selectie zonder herhaling);
een permutatie van $E$ is een bijectie van $E$ naar zichzelf — equivalent, een $n$ -schikking;
een $k$ -combinatie is een deelverzameling van $E$ met $k$ elementen (een ongeordende selectie zonder herhaling). Hun aantal wordt genoteerd $\binom{n}{k}$ , gelezen als “ $n$ boven $k$ ” .

Stelling 2.12 (De drie tellingen)

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

het aantal $k$ -schikkingen 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$ manieren), dan de tweede ( $n - 1$ resterende keuzes), …, dan de $k$ -de ( $n - k + 1$ keuzes). Formeel, doe inductie op $k$ . Voor $k = 1$ zijn er $n$ injectieve tallen met één term. Neem de telling aan voor $k - 1$ . Elke $k$ -schikking $(x_1, \dots, x_k)$ wordt uit precies één $(k-1)$ -schikking verkregen — haar afknotting $(x_1, \dots, x_{k-1})$ — door een laatste coördinaat toe te voegen buiten $\{x_1, \dots, x_{k-1}\}$ , waarvoor precies $n - (k - 1)$ waarden beschikbaar zijn. De $k$ -schikkingen worden zo, door afknotting, verdeeld in klassen van gemeenschappelijke grootte $n - k + 1$ geïndexeerd door de $(k-1)$ -schikkingen, 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 zich tot $k!$ verschillende $k$ -schikkingen, en elke $k$ -schikking ontstaat uit precies één deelverzameling: dus $\frac{n!}{(n-k)!} = \binom nk \cdot k!$ . ∎

Voorbeeld 2.13 (Ronde tafels: uitdelen door symmetrie)

Op hoeveel manieren kunnen $n$ gasten rond een ronde tafel zitten, waarbij twee plaatsingen identiek zijn wanneer elke gast dezelfde linker- en rechterbuur heeft — d.w.z. op rotatie na? Elke cirkelvormige plaatsing correspondeert met precies $n$ lineaire plaatsingen (knip de cirkel op elk van de $n$ plaatsen), dus de $n!$ lineaire ordeningen vallen samen in groepen van $n$ :

\frac{n!}{n} = (n-1)! \quad\text{cirkelvormige plaatsingen.}

Equivalent: zet één uitverkoren gast ergens neer (waarmee de rotatievrijheid geëlimineerd wordt), ordn dan de overige $n - 1$ gasten met de klok mee. Voor $n = 6$ : $120$ tafels. De twee oplossingen illustreren de twee standaardremedies voor overtelling: deel door het exacte aantal herhalingen, of breek de symmetrie door één object vast te pinnen. Beide vereisen dat de grootte van de groep herhalingen voor elke configuratie dezelfde is — wat het bewijs van de formule $\binom nk = \frac{n!}{k!\,(n-k)!}$ hierboven eveneens gebruikte, met $k!$ in plaats van $n$ .

Voorbeeld 2.14 (Een beperking toevoegen)

De ronde tafel voortzettend: onder de $(n-1)!$ tafels van $n \geq 3$ gasten, hoeveel plaatsen twee gegeven gasten $A$ en $B$ uit elkaar (niet naast elkaar)? Tel het complement. Tafels waar $A$ en $B$ samen zitten: lijm ze aaneen tot één blok — $n - 1$ objecten rond de tafel, d.w.z. $(n-2)!$ cirkelvormige schikkingen — ordn dan het paar binnen zijn blok ( $2$ manieren): $2\,(n-2)!$ tafels waar ze naast elkaar zitten. Dus

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

tafels houden ze uit elkaar. Controles: $n = 3$ geeft $0$ (rond een driehoek raakt iedereen iedereen) en $n = 4$ geeft $2$ , gemakkelijk met de hand opgesomd. De lijmtruc — behandel een gedwongen blok als één object, tel dan zijn interne schikkingen — is de standaardremedie voor beperkingen op aangrenzendheid, lineair of cirkelvormig.

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 $k$ -deelverzamelingen en $(n-k)$ -deelverzamelingen. Regel van Pascal: kies een element $a \in E$ ; de $k$ -deelverzamelingen splitsen zich in die welke $a$ bevatten (kies de $k - 1$ andere: $\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 (Binomiaalstelling)

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

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

Bewijs. Het distributief uitwerken van $(a+b)(a+b)\cdots(a+b)$ levert één term per keuze, in elke factor, van ofwel $a$ ofwel $b$ : de term $a^k b^{n-k}$ verschijnt eenmaal voor elke manier om te kiezen welke $k$ van de $n$ factoren $a$ bijdragen — dat wil zeggen, $\binom nk$ keer. (Alternatief: doe inductie op $n$ met de regel van Pascal.) ∎

Voorbeeld 2.17

Twee klassieke specialisaties: $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$ : onder de deelverzamelingen van een niet-lege verzameling heeft precies de helft een even kardinaliteit.

Voorbeeld 2.18 (Eén identiteit, twee bewijzen)

De specialisatie $a = 2$ , $b = 1$ van de binomiaalstelling luidt

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

Hier is dezelfde identiteit zonder enige algebra. Het rechterlid telt de woorden van lengte $n$ over het alfabet $\{0, 1, 2\}$ (productregel). Classificeer elk woord naar de verzameling $K$ van posities die een niet-nulletter dragen: het kiezen van $K$ met $\abs K = k$ kost $\binom nk$ , dan draagt elke positie van $K$ onafhankelijk $1$ of $2$ : $2^k$ manieren. De somregel over $k$ geeft het linkerlid. Voorbij het genoegen van de overeenstemming hebben de twee bewijzen verschillende verdiensten: het algebraïsche veralgemeent naar elke waarde van $a$ , het combinatorische verklaart de formule en past zich aan aan beperkingen (verbied de letter $2$ op de laatste positie, zeg) die geen enkele substitutie vat. Beide technieken actief houden is de praktische vaardigheid die dit hoofdstuk traint.

Methode 2.19 (Welke telling is van toepassing?)

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

	volgorde telt	volgorde telt niet
geen herhaling	$\dfrac{n!}{(n-k)!}$	$\dbinom{n}{k}$
[6pt] herhaling toegestaan	$n^k$	(Oefening 2.10)

Zoek dan naar een bijectie of een partitie die het probleem herleidt tot deze modeltellingen; een correcte telling is een vermomde bijectie.

Opmerking 2.20 (Veelvoorkomende valkuilen bij het tellen)

Niet-disjuncte gevallen optellen. De somregel vereist een partitie; als configuraties twee gevallen tegelijk kunnen voldoen, worden ze dubbel geteld — de remedie is inclusie–exclusie (Stelling 2.24) of een fijnere gevalsonderscheiding.
Geordend versus ongeordend. Het kiezen van “een commissie van twee” is $\binom n2$ , niet $n(n-1)$ : beslis vóór het rekenen of de selectie een volgorde draagt, en als een geordende telling gemakkelijker is, deel dan aan het einde door het aantal ordeningen — maar alleen wanneer elk ongeordend object uit hetzelfde aantal geordende ontstaat.
Meertraps keuzes die niet onafhankelijk zijn. De productregel vereist dat het aantal opties bij elke trap onafhankelijk is van de voorgaande keuzes. “Kies een kapitein, dan een verschillende vicekapitein” is prima ( $n(n-1)$ ); “kies twee spelers die met elkaar overweg kunnen” is helemaal geen tweetraps product.
Dubbeltelling door constructie. Elk object twee keer opbouwen — bijv. handen met ten minste één aas tellen als (kies een aas) $\times$ (kies $4$ verdere kaarten) — telt handen met twee azen te veel. “Ten minste” vraagt bijna altijd om het complement (Voorbeeld 2.9).

Voorbeeld 2.21 (Telling in pokerstijl)

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

Methode 2.22 (Dubbeltelling)

Om een identiteit tussen twee teluitdrukkingen te bewijzen, zoek één enkele eindige verzameling die beide leden tellen — typisch een verzameling van paren — en evalueer haar kardinaliteit in twee verschillende volgordes. Het prototype is het handdruklemma: tel op een feest de paren (persoon, geschudde hand). Sommeren over personen geeft $\sum_p d_p$ (het aantal handdrukken $d_p$ van elke persoon $p$ ); sommeren over handdrukken geeft tweemaal het aantal handdrukken (elk betreft twee personen). Dus is $\sum_p d_p$ even — zodat het aantal personen dat een oneven aantal handen schudde altijd even is, een niet-triviale conclusie verkregen zonder enige formule. Dezelfde machine drijft Oefening 2.12 en verscheidene vragen van het weekendprobleem hieronder aan.

Voorbeeld 2.23 (De gemiddelde deelverzameling)

Wat is de gemiddelde kardinaliteit van een deelverzameling van een $n$ -elements verzameling $E$ , waarbij 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 totaal dat we willen; 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\}$ ). Dus

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

deelverzamelingen zijn gemiddeld half gevuld — zoals de symmetrie $A \leftrightarrow \overline A$ (die groottes $k$ en $n - k$ koppelt) eveneens voorspelt. 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$ :

\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. Neem een element $x$ van de vereniging en tel zijn bijdrage aan het rechterlid. Zij $J = \{i : x \in A_i\}$ , van kardinaliteit $m \geq 1$ . Het element $x$ wordt eenmaal geteld in $\abs{\bigcap_{i \in I} A_i}$ precies wanneer $\emptyset \neq I \subseteq J$ , met teken $(-1)^{\abs I + 1}$ ; zijn totale bijdrage is

\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. Dus wordt elk element van de vereniging precies eenmaal geteld. ∎

Voorbeeld 2.25 (Relatief prieme gehele getallen tellen)

Hoeveel gehele getallen van $\intint1{120}$ zijn relatief priem met $120 = 2^3 \times 3 \times 5$ ? Een geheel getal deelt een factor met $120$ precies wanneer het deelbaar is door $2$ , $3$ of $5$ , dus tel 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$ telkens wanneer $d$ het getal $120$ deelt — geen vloerfuncties nodig — en $A_2 \cap A_3 = A_6$ , enz. Inclusie–exclusie:

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

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

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

het uitwerken van de drie haakjes reproduceert precies de acht getekende termen van inclusie–exclusie, één per deelverzameling van $\{2, 3, 5\}$ . Deze productvorm definieert de totiëntfunctie van Euler, waarvan de rekenkundige rol met de congruenties van Hoofdstuk 6 verschijnt en ontwikkeld wordt in het volume van Jaar 2.

Voorbeeld 2.26 (Derangementen)

Een derangement is een permutatie zonder vast punt. Zij $A_i$ de verzameling permutaties van $\intint{1}{n}$ die $i$ vastlaten; dan geldt $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$ , en inclusie–exclusie telt de permutaties met ten minste één vast punt; de derangementen zijn er

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

Aangezien $\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 intensief hergebruikte objecten van dit hoofdstuk: ze drijven de binomiaalstelling in Hoofdstuk 8 (uitwerking van $(X + a)^n$ ) aan, 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 een groep — met de signatuur opgebouwd uit het tellen van inversies — in Hoofdstuk 7, en de signatuur definieert op haar beurt determinanten in Hoofdstuk 22. Inclusie–exclusie en de telprincipes zijn de eindige ruggengraat van de discrete kansrekening, ontwikkeld in het volume van Jaar 2; de derangementgetallen van Voorbeeld 2.26 worden in de diepte bestudeerd in het weekendprobleem hieronder.

2.5 Oefeningen

Oefening 2.1 ★

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

Oplossing

Oplossing van Oefening 2.1.

Onafhankelijke trappen en de productregel: $26^2 \times 10^3 \times 26^2 = 26^4 \times 1000 = 456\,976\,000$ platen. Met de vier letters paarsgewijs verschillend vormen de letterstappen een $4$ -schikking 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 wordt bepaald door de posities van de a’s ( $\binom 63$ keuzes), dan van de n’s onder de overige $3$ plaatsen ( $\binom 32$ ), waarbij de b de laatste plaats inneemt: $\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60$ anagrammen (equivalent $6!/(3!\,2!\,1!) = 60$ ).

Oefening 2.3 ★

Een commissie van $4$ personen wordt gekozen uit $7$ vrouwen en $5$ mannen. Hoeveel commissies: in totaal? met precies $2$ vrouwen? met ten minste één man?

Oplossing

Oplossing van Oefening 2.3.

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

Oefening 2.4 ★

Bewijs dat in elke groep van $13$ personen twee dezelfde geboortemaand delen; en dat onder elke $n + 1$ gehele getallen gekozen uit $\intint{1}{2n}$ twee opeenvolgend zijn. (Beide keren het duiventilprincipe: noem de vakjes.)

Oplossing

Oplossing van Oefening 2.4.

Verjaardagen: de vakjes zijn de $12$ maanden; $13$ personen in $12$ vakjes dwingen er twee in hetzelfde vakje (Gevolg 2.3).

Opeenvolgende gehele getallen: de vakjes zijn de $n$ paren $\{1,2\}, \{3,4\}, \dots, \{2n-1, 2n\}$ , die $\intint{1}{2n}$ partitioneren. Het kiezen van $n + 1$ gehele getallen plaatst 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}$ . Hint: leid $(1 + x)^n$ af, of gebruik $k \binom nk = n \binom{n-1}{k-1}$ (bewijs dit).

Oplossing

Oplossing van Oefening 2.5.

Voor $1 \leq k \leq n$ ,

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

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

Oefening 2.6 ★★

Hoeveel strikt stijgende afbeeldingen zijn er van $\intint{1}{k}$ naar $\intint{1}{n}$ ? Leid het aantal stijgende (niet noodzakelijk strikt) afbeeldingen af. Hint 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}$ wordt bepaald door haar beeld, een $k$ -deelverzameling van $\intint{1}{n}$ (som de deelverzameling op in stijgende volgorde); omgekeerd geeft elke $k$ -deelverzameling precies één zo’n afbeelding. Dus $\binom nk$ strikt stijgende afbeeldingen.

Als $f$ enkel stijgend is, stel $g(i) = f(i) + i - 1$ . Dan is $g$ strikt stijgend (tussen opeenvolgende argumenten wint $f$ er $\geq 0$ bij en $i - 1$ wint er $1$ bij) met waarden in $\intint{1}{n + k - 1}$ ; en $f(i) = g(i) - i + 1$ herwint $f$ uit elke strikt stijgende $g$ in $\intint{1}{n+k-1}$ . Dit is een bijectie, dus er zijn $\binom{n + k - 1}{k}$ stijgende afbeeldingen.

Oefening 2.7 ★★

(Vandermonde) Bewijs, door $k$ -deelverzamelingen te tellen van een verzameling gesplitst in twee blokken van groottes $m$ en $n$ :

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

Leid $\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 een zeker aantal $j$ elementen van $M$ ( $0 \leq j \leq k$ ) en $k - j$ van $N$ ; voor 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 geeft de identiteit van Vandermonde.

Met $m = n = k$ : $\binom{2n}{n} = \sum_{j=0}^{n} \binom nj \binom{n}{n-j} = \sum_{j=0}^{n} \binom nj^2$ , waarbij $\binom{n}{n-j} = \binom nj$ gebruikt wordt.

Oefening 2.8 ★★

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

Oplossing

Oplossing van Oefening 2.8.

Zij $A_d$ de veelvouden van $d$ in $\intint{1}{1000}$ , dus $\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$ enz.:

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

Dus $734$ gehele getallen zijn deelbaar door $2$ , $3$ of $5$ .

Oefening 2.9 ★★

Tel de surjecties van een verzameling van $4$ elementen op een verzameling van $2$ elementen; dan op een verzameling van $3$ elementen. Hint: 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 afbeeldingen: $14$ surjecties.

Op $3$ elementen: door inclusie–exclusie op de gemiste waarden is het aantal afbeeldingen van een $4$ -verzameling naar een $3$ -verzameling die ten minste één waarde missen gelijk aan $\binom 31 2^4 - \binom 32 1^4 = 48 - 3 = 45$ ; totaal aantal afbeeldingen $3^4 = 81$ ; surjecties: $81 - 45 = 36$ . (Controle: een surjectie van $4$ op $3$ elementen verdubbelt precies één waarde: kies de verdubbelde waarde ( $3$ ), het paar dat erop afgebeeld wordt ( $\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$ -selecties van $n$ objecten met herhaling, volgorde genegeerd — 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}$ . Hint: 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, …, eindigend 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 worden bepaald door de posities van de sterren: $\binom{n + k - 1}{k}$ . Selecties met herhaling corresponderen met oplossingen van de vergelijking ( $x_i$ = aantal kopieën van object $i$ ), dus de telling is dezelfde.

Oefening 2.11 ★★★

Bewijs de formule van Voorbeeld 2.26 voor $D_n$ in detail, en leid $n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$ af (bewijs deze identiteit ook rechtstreeks door permutaties te classificeren naar hun vast-puntenverzameling).

Oplossing

Oplossing van Oefening 2.11.

Met $A_i = \{\sigma : \sigma(i) = i\}$ laat een permutatie in $\bigcap_{i \in I} A_i$ elke $i \in I$ vast en permuteert de overige $n - \abs I$ punten vrij: $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$ . Inclusie–exclusie:

\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!} ,

aangezien er $\binom nk$ deelverzamelingen $I$ van grootte $k$ zijn. Dus

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: classificeer de permutaties $\sigma$ van $\intint{1}{n}$ naar hun vast-puntenverzameling $F(\sigma)$ . Voor een vaste $k$ -deelverzameling $F$ zijn de permutaties met $F(\sigma) = F$ precies de derangementen van het complement: $D_{n-k}$ ervan. Sommeren over de $\binom nk$ keuzes van $F$ voor elke $k$ : $n! = \sum_{k=0}^{n} \binom nk D_{n-k}$ .

Oefening 2.12 ★★★

Voor $n \in \N^*$ , bewijs door een dubbeltelling van paren (deelverzameling, gemarkeerd element):

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

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

Oplossing

Oplossing van Oefening 2.12.

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

Tweede identiteit. Tel de drietallen $(A, a, b)$ met $a, b \in A$ (mogelijk $a = b$ ). Naar 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 overige $n - 2$ elementen: $n(n-1)\,2^{n-2}$ ). 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 Probleem: Derangementen, of de verkeerd geadresseerde brieven

Probleem 2.1

Een secretaris stopt $n$ brieven in $n$ geadresseerde enveloppen willekeurig: wat is de kans dat niemand de juiste brief ontvangt? Deze klassieke vraag (Montmort, 1708) leidt tot de derangementgetallen $D_n$ van Voorbeeld 2.26. De inclusie–exclusieformule is slechts de openingszet: dit probleem ontwikkelt de recurrenties 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 vaste punten van een willekeurige permutatie, en de merkwaardige rekenkunde van de rij $(D_n)$ . Doorheen dit alles duidt $D_n$ het aantal derangementen (permutaties zonder vast punt) van $\intint1n$ aan, met de conventie $D_0 = 1$ (de lege permutatie heeft geen vast punt).

Deel I — Kleine gevallen en de telling van 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 zou $D_4 = 9$ moeten vinden.)
Voor $0 \leq k \leq n$ , toon aan dat het aantal $P_k(n)$ permutaties van $\intint1n$ met precies $k$ vaste punten gelijk is aan $\binom nk D_{n-k}$ .
Verifieer de telling voor $n = 4$ : bereken $P_0(4), \dots, P_4(4)$ en controleer dat ze sommeren tot $4! = 24$ . Wat is waarschijnlijker voor vier brieven: geen match, of precies één match?
Toon door 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 recurrenties en twee nieuwe bewijzen van de formule.

Bewijs combinatorisch, voor $n \geq 1$ :

$D_{n+1} = n\,(D_n + D_{n-1}) .$

(Classificeer de derangementen $\sigma$ van $\intint1{n+1}$ naar $j = \sigma(n+1)$ , dan naar of $\sigma(j) = n + 1$ ; in het geval $\sigma(j) \neq n+1$ , bouw een bijectie met de derangementen van $\intint1n$ door het origineel van $n + 1$ om te leiden naar $j$ .) Controleer de recurrentie numeriek tot $D_6$ .
Stel $u_n = D_n - n D_{n-1}$ , leid uit vraag 5 af dat $u_{n+1} = -u_n$ , en besluit de tweede recurrentie:

$D_n = n D_{n-1} + (-1)^n \qquad (n \geq 1).$
Bewijs uit vraag 6 door inductie de formule van Voorbeeld 2.26,

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

— een bewijs geheel onafhankelijk van inclusie–exclusie.
(Binomiale inversie) Zij $(a_n)$ en $(b_n)$ twee rijen zodat $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, gebruik dan de alternerende rijsom van Voorbeeld 2.17.)
Pas vraag 8 toe op de identiteit $n! = \sum_k \binom nk D_{n-k}$ van Oefening 2.11 om een derde bewijs van de formule voor $D_n$ te verkrijgen.

Deel III — Het dichtstbijzijnde gehele getal bij $n!/\eu$ . Neem voor dit deel aan — de theorie wordt opgebouwd in Hoofdstuk 17 — dat $\eu^{-1} = \lim_{n \to \infty} s_n$ waarbij $s_n = \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ , met de strikte grens voor alternerende reeksen $\abs{\eu^{-1} - s_n} < \frac1{(n+1)!}$ voor elke $n$ .

Toon aan dat $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ voor alle $n \in \N$ .
Leid de kernstelling 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. (Lokaliseer de eerste verwaarloosde term van de alternerende reeks.)
Bereken $D_7$ tot en met $D_{10}$ met de recurrentie van vraag 5, controleer dan $D_{10}$ tegen $10!/\eu$ ( $10! = 3\,628\,800$ , $\eu \approx 2.718281828$ ).
(De vestiaireprobabiliteit) 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 vijf decimalen. Commentaar: waarom is het antwoord op de vraag van Montmort in wezen onafhankelijk van $n$ — reeds voor een dozijn brieven?

Deel IV — De verdeling van vaste punten.

Zij $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, sommerend tot $1$ , vormen de Poissonverdeling van parameter $1$ , een centraal object van de cursus kansrekening in het volume van Jaar 2.)
Toon door dubbeltelling van de drietallen $(\sigma, i, j)$ waar $i \neq j$ beide vastgelaten worden door $\sigma$ aan dat $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}\, (\abs{\mathrm{Fix}(\sigma)} - 1) = n!$ voor $n \geq 2$ . Gecombineerd met vraag 4: het gemiddelde van $\abs{\mathrm{Fix}}^2$ is $2$ , dus de “spreiding” (variantie) van het aantal vaste punten is gelijk aan $1$ — opnieuw onafhankelijk van $n$ , opnieuw overeenkomend met de Poissonwet.
Bereken het aandeel van de permutaties met ten minste één vast punt voor $n = 4, 5, 6$ (als breuken en tot vier decimalen), en vergelijk met $1 - \eu^{-1} \approx 0.6321$ .
Toon rechtstreeks aan — zonder limieten — dat $s_{n+2} - s_n = (-1)^{n+1}\bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\bigr)$ , en leid af dat de probabiliteiten $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 (resp. oneven) waarden dalen (resp. stijgen) naar de gemeenschappelijke limiet $\eu^{-1}$ .
(Secret Santa) $n$ personen trekken elk één naam uit een hoed; als iemand zijn eigen naam trekt, wordt de hele trekking vanaf nul opnieuw gestart. Gebruik het standaardfeit dat een gebeurtenis met probabiliteit $p$ gemiddeld $1/p$ pogingen kost, schat het gemiddelde aantal volledige trekkingen dat nodig is, 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 voor vaste $j \in \intint2n$ de derangementen van $\intint1n$ met $\sigma(1) = j$ er precies $D_{n-1} + D_{n-2}$ 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 recurrentie 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 uit 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 derangementgetallen bijna precies $n$ is; leg in één zin uit waarom dit consistent is met $D_n \approx n!/\eu$ .
Waar precies gebruikte dit probleem: (i) de product- en somregel; (ii) dubbeltelling; (iii) de binomiaalstelling; (iv) de aangenomen grens voor alternerende reeksen? Eén zin per stuk.
Synthese. De formule voor $D_n$ heeft nu drie bewijzen (inclusie–exclusie, recurrentie plus inductie, binomiale inversie). Vergelijk in een korte paragraaf wat elk bewijs verklaart: welk berekent het snelst, welk veralgemeent naar andere tellingen van vaste punten, en welk onthult waarom $\eu$ verschijnt in een probleem over enveloppen.

Oplossing

Oplossing van Probleem 2.1.

1. $D_1 = 0$ (de enige permutatie laat $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 in elke groep: $D_4 = 9$ .

2. Een permutatie met precies $k$ vaste punten wordt bepaald door de keuze van haar vast-puntenverzameling $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 correspondentie 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 match ( $9$ gevallen) verslaat precies één match ( $8$ gevallen) — nipt.

4. Tel de paren $(\sigma, i)$ met $\sigma(i) = i$ . Voor vaste $i$ zijn de permutaties die $i$ vastlaten de permutaties van de overige $n - 1$ punten: $(n-1)!$ ervan. Dus is het aantal paren gelijk aan $n \cdot (n-1)! = n!$ , en dit aantal is ook $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}$ . Delen door het aantal $n!$ permutaties: 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 ervan: $D_{n-1}$ mogelijkheden. Geval $\sigma(j) \neq n+1$ : zij $i_0 = \sigma^{-1}(n+1)$ ; hier geldt $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 het is een derangement: $\tau(i_0) = j \neq i_0$ , en $\tau(i) = \sigma(i) \neq i$ elders. Omgekeerd herwint men uit een derangement $\tau$ van $\intint1n$ en de waarde $j$ de permutatie $\sigma$ door $\sigma(n+1) = j$ , $\sigma(\tau^{-1}(j)) = n+1$ en $\sigma = \tau$ elders te stellen: een bijectie, die $D_n$ mogelijkheden geeft. Sommeren over $j$ : $D_{n+1} = n(D_n + D_{n-1})$ . Numeriek: $D_5 = 4(9 + 2) = 44$ , $D_6 = 5(44 + 9) = 265$ .

6. Uit vraag 5, $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 .

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

7. Inductie op $n$ . Basis: $D_0 = 1 = 0!\,s_0$ . Stap: aannemende dat $D_{n-1} = (n-1)!\,s_{n-1}$ ,

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 ,

wat de formule is. Geen inclusie–exclusie werd gebruikt: enkel de combinatorische recurrentie 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 uitwerking van $(1 + (-1))^{n-j} = 0^{n-j}$ (binomiaalstelling, Stelling 2.16): hij verdwijnt voor $j < n$ en is gelijk aan $1$ voor $j = n$ . Enkel $j = n$ overleeft, en het rechterlid is $b_n$ , zoals beweerd.

9. Door de symmetrie $\binom nk = \binom n{n-k}$ herschrijft de identiteit van Oefening 2.11 zich als $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!} ,

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

10. $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$ , $\frac1{n+1} \leq \frac12$ , en de ongelijkheid van vraag 10 is strikt: $D_n$ ligt op afstand $< \frac12$ van $n!/\eu$ , dus is het het unieke dichtstbijzijnde gehele getal. Voor $n = 0$ geeft de grens enkel afstand $< 1$ , en inderdaad faalt de bewering daar: $0!/\eu \approx 0.368$ heeft dichtstbijzijnd geheel getal $0$ , 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, dus haar teken is het teken van haar eerste term $(-1)^{n+1}/(n+1)!$ . Dus heeft $s_n - \eu^{-1}$ het teken van $(-1)^n$ : voor $n$ even geldt $s_n > \eu^{-1}$ en $D_n = n!\,s_n > n!/\eu$ ; voor $n$ oneven geldt $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$ , waarvan het dichtstbijzijnde gehele getal $1\,334\,961$ is — en $D_{10} > 10!/\eu$ , zoals vraag 12 voorspelt voor even $n$ .

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), tegen $\eu^{-1} = 0.36788$ ; het verschil ligt onder $1/7! = 1/5040 < 2 \times 10^{-4}$ . De grens $1/(n+1)!$ stort zo snel in dat de probabiliteit reeds voor een dozijn brieven tot vele decimalen vastligt: het antwoord “ongeveer $36.8\%$ ” is, voor elk praktisch doel, onafhankelijk van $n$ — de befaamde verrassing van het probleem.

15. Volgens 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$ met $k$ vast, aangezien $s_{n-k} \to \eu^{-1}$ . De limietwaarden $\eu^{-1}/k!$ ( $k \in \N$ ) zijn de gewichten van de Poissonverdeling van parameter $1$ .

16. Tel de drietallen $(\sigma, i, j)$ met $i \neq j$ , $\sigma(i) = i$ , $\sigma(j) = j$ . Door het geordende paar eerst te kiezen: $n(n-1)$ manieren; de permutaties die zowel $i$ als $j$ vastlaten zijn de permutaties van de overige $n - 2$ punten: $(n-2)!$ ervan. Totaal: $n(n-1)(n-2)! = n!$ . Sommeren in plaats daarvan eerst over $\sigma$ telt, voor elke $\sigma$ , de geordende paren van verschillende vaste punten: $\abs{\mathrm{Fix}(\sigma)}(\abs{\mathrm{Fix}(\sigma)}-1)$ . Vandaar de gestelde identiteit; delen door $n!$ , het gemiddelde van $\abs{\mathrm{Fix}}(\abs{\mathrm{Fix}} - 1)$ is $1$ , dus het gemiddelde van $\abs{\mathrm{Fix}}^2$ is $1 + 1 = 2$ en de variantie is $2 - 1^2 = 1$ .

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

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 de haakjesterm is $> 0$ . Voor $n$ even is het verschil negatief: $s_{n+2} < s_n$ , dus $p_0 > p_2 > p_4 > \dots$ ; voor $n$ oneven is het positief: $p_1 < p_3 < p_5 < \dots$ Gecombineerd met vraag 12 (even boven $\eu^{-1}$ , oneven eronder) en vraag 14 (afstand tot $\eu^{-1}$ gaat naar $0$ ): de twee trappen knijpen $\eu^{-1}$ ertussen samen.

19. Eén volledige trekking is een uniform willekeurige permutatie, geldig wanneer het een derangement is: probabiliteit $p_n \approx \eu^{-1}$ . Volgens het aangehaalde feit is het gemiddelde aantal trekkingen tot succes $1/p_n$ , en vraag 14 geeft $1/p_n \approx \eu$ op een fout na die reeds voor kleine $n$ verwaarloosbaar is. Dus kost een Secret Santa met herstarts gemiddeld ongeveer $\eu \approx 2.72$ volledige trekkingen — of het kantoor nu $6$ personen of $600$ heeft.

20. Zij $j \geq 2$ vast en pas de classificatie van vraag 5 toe op de waarde $\sigma(1) = j$ . Als $\sigma(j) = 1$ : de overige $n - 2$ punten dragen een willekeurig derangement, $D_{n-2}$ manieren. Als $\sigma(j) \neq 1$ : leid het origineel $i_0 = \sigma^{-1}(1)$ om naar $j$ precies zoals in vraag 5; dit is een bijectie met de derangementen van de $n - 1$ punten $\{2, \dots, n\}$ : $D_{n-1}$ manieren. Totaal $D_{n-1} + D_{n-2}$ , hetzelfde voor elke $j$ . Sommeren over de $n - 1$ waarden van $j$ : $D_n = (n-1)(D_{n-1} + D_{n-2})$ , wat de factor $n - 1$ toont: $(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$ , d.w.z. $D_n \equiv nD_{n-1} + 1 \pmod 2$ . Basis: $D_1 = 0$ is even, $n = 1$ oneven: de bewering geldt. Als $n$ even is, is $nD_{n-1}$ even en $D_n \equiv 1$ : oneven, zoals beweerd. Als $n$ oneven is, dan is $n - 1$ even, dus $D_{n-1}$ is oneven per hypothese, en $D_n \equiv D_{n-1} + 1 \equiv 0$ : even. De inductie sluit.

22. $D_n = nD_{n-1} + (-1)^n$ modulo $n$ reduceren doodt de eerste term: $D_n \equiv (-1)^n \pmod n$ . Voor $n = 10$ : $(-1)^{10} = 1$ , en inderdaad eindigt $D_{10} = 1\,334\,961$ op het cijfer $1$ .

23. Voor $n \geq 3$ , $D_{n-1} \geq 1$ en deling van de recurrentie 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$ tendend. Consistentie: als $D_n \approx n!/\eu$ , dan $D_n/D_{n-1} \approx n!/(n-1)! = n$ — de factor $\eu$ valt weg in de verhouding, en de recurrentie bevestigt het tot op nauwkeurigheid $1/D_{n-1}$ .

24. (i) De product- en somregel liggen ten grondslag aan elke telling: vragen 2 en 5 partitioneren verzamelingen permutaties in onafhankelijke trappen. (ii) Dubbeltelling gaf het gemiddelde (vraag 4) en de variantie (vraag 16) van het aantal vaste punten zonder enige formule voor $D_n$ . (iii) De binomiaalstelling evalueerde de alternerende binnenste som $(1-1)^{n-j}$ die binomiale inversie laat werken (vraag 8). (iv) De grens voor alternerende reeksen zette de exacte maar ondoorzichtige som $n!\,s_n$ om in de transparante uitspraak “dichtstbijzijnd geheel getal bij $n!/\eu$ ” (vragen 10–14).

25. Inclusie–exclusie (Voorbeeld 2.26 en Oefening 2.11) is het conceptuele bewijs: het verklaart de alternerende som als overtellingscorrecties, en het veralgemeent woordelijk naar het tellen van elementen die elke familie van “slechte” verzamelingen mijden. De recurrentieweg (vragen 5–7) berekent het snelst — lineaire tijd, exacte geheeltallige rekenkunde, geen faculteiten — en is de bron van de rekenkundige feiten van Deel V. Binomiale inversie (vragen 8–9) plaatst de formule binnen een algemene transformatie die zal terugkeren waar twee driehoekige systemen van identiteiten elkaar tegenkomen. En de verschijning van $\eu$ wordt het best verklaard door de formule zelf: het aandeel derangementen is de partiële som $s_n$ van de reeks voor $\eu^{-1}$ , dus de enveloppen van Montmort berekenden, drie decennia vóór de notatie van Euler, reeds het getal $\eu$ .