Proposition 10

Let $m$ and $n$ be integers such that $m \leqslant n$. Then $n!/(n - m)!$ is the number of injective mappings of a set $\mathrm{A}$ with $m$ elements into a set $\mathrm{B}$ with $n$ elements.

The proof is by induction on the number $m \leqslant n$ of elements of $\mathrm{A}$. If $m = 0$, the result is evident. Suppose that $m + 1 \leqslant n$. Let $\mathrm{A}$ be a set with $m + 1$ elements, let $\mathrm{A}'$ be a subset of $\mathrm{A}$ with $m$ elements, and let $\{a\} = \mathrm{A} - \mathrm{A}'$. Let $\mathrm{F}$, $\mathrm{F}'$ be the sets of injective mappings of $\mathrm{A}$, $\mathrm{A}'$ respectively into $\mathrm{B}$, and let $\varphi$ be the mapping $f \to f\,|\mathrm{A}'$ which maps each function $f \in \mathrm{F}$ to its restriction to $\mathrm{A}'$. For each $f' \in \mathrm{F}'$ an element $f$ of $\overset{-1}{\varphi}(f')$ is uniquely determined by its value $f(a)$; since $f$ is injective, we must have $f(a) \in \mathrm{B} - f'(\mathrm{A}')$. It follows that $\overset{-1}{\varphi}(f')$ has the same number $n - m$ of elements as $\mathrm{B} - f'(\mathrm{A}')$. Hence, by Proposition 9, $\mathrm{F}$ has

elements by virtue of the inductive hypothesis. This completes the proof.