Wat is Variaties, permutaties, combinaties?

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

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.

Voorbeeld 2.18 (Eén identiteit, twee bewijzen)

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

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.

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.