Proof of the number of permutations by counting injections

Proof

We show that the permutations of $X$ are exactly the injections from $X$ to $X$, and then count injections.

1. A permutation of $X$ is a bijection $\sigma : X \to X$. In particular it is injective.
2. Conversely, let $\sigma : X \to X$ be injective, and put $C = \sigma(X)$. Then $\sigma$ is a bijection from $X$ onto $C$.
3. Composing a numbering of $X$ with $\sigma$ numbers $C$. So $|C| = |X| = n$, as in the bijection principle.
4. By the complement principle, $|X \setminus C| = n - n = 0$. So $X \setminus C$ is empty and $C = X$.
5. So $\sigma$ is surjective, hence a bijection of $X$, that is, a permutation.
6. By steps 1 to 5, the permutations of $X$ are exactly the injections from $X$ to $X$.
7. By the number of injections, there are $(n)_n$ of them, where $(n)_n$ is the falling factorial.
8. For $n = 0$, $(0)_0 = 1 = 0!$. For $n \ge 1$, $(n)_n = n (n-1) \cdots 1$, which is $n!$ by the definition of the factorial.
9. Hence $X$ has exactly $n!$ permutations.