What is Arrangements, permutations, combinations?

Example 2.14 (Adding a constraint)

Continuing the round table: among the $(n-1)!$ tables of $n \geq 3$ guests, how many seat two given guests $A$ and $B$ apart (not adjacent)? Count the complement. Tables where $A$ and $B$ sit together: glue them into a single block — $n - 1$ objects around the table, i.e. $(n-2)!$ circular arrangements — then order the pair inside its block ($2$ ways): $2\,(n-2)!$ adjacent tables. Hence

tables keep them apart. Sanity checks: $n = 3$ gives $0$ (around a triangle, everyone touches everyone) and $n = 4$ gives $2$, easily listed by hand. The gluing trick — treat a forced block as one object, then count its internal arrangements — is the standard cure for adjacency constraints, linear or circular.

Example 2.18 (One identity, two proofs)

The specialization $a = 2$, $b = 1$ of the binomial theorem reads

Here is the same identity with no algebra at all. The right side counts the words of length $n$ over the alphabet $\{0, 1, 2\}$ (product rule). Classify each word by the set $K$ of positions carrying a nonzero letter: choosing $K$ with $\abs K = k$ costs $\binom nk$, then each position of $K$ independently carries $1$ or $2$: $2^k$ ways. The sum rule over $k$ gives the left side. Beyond the pleasure of agreement, the two proofs have different virtues: the algebraic one generalizes to any value of $a$, the combinatorial one explains the formula and adapts to constraints (forbid the letter $2$ in the last position, say) that no substitution captures. Keeping both techniques active is the practical skill this chapter trains.

Example 2.6 (Finiteness is essential)

On a finite set, Proposition 2.5 is a powerful shortcut: any injective map from $E$ to itself is automatically a permutation of $E$ — half of bijectivity comes for free. Both implications collapse on infinite sets: $n \mapsto n + 1$ is injective from $\N$ to $\N$ but misses $0$, and the map $\N \to \N$ sending $0 \mapsto 0$ and $n \mapsto n - 1$ for $n \geq 1$ is surjective but not injective. Whenever this proposition is invoked, the finiteness hypothesis is doing real work — a theme that the weekend problem of Chapter 1 explores from the other side, where infinite sets are precisely those admitting such self-maps.