Für \(m \in \{1, \dots, n+1\} \) definieren wir abkürzend \(A_m = \{ \sigma \in S_{n+1} \vert \sigma(n+1)=m \} \).

Die Abbildung \( A_{n+1} \to S_n, \ \sigma \to \sigma \vert_{\{1, \dots, n\}} \) ist eine Bijektion. Es gilt also nach Induktionsannahme \( \vert A_{n+1} \vert = \vert S_n \vert = n! \)

Sei nun \(m \in \{1, \dots n\} \). Außerdem sei \( \tau \in S_{n+1} \) die folgende Transposition \( \tau(x) = \begin{cases} n+1 & x=m \\ m & x=n+1 \\ x & sonst \end{cases} \)

Die Abbildung \( A_m \to A_{n+1}, \ \sigma \to \tau \circ \sigma \) ist eine Bijektion. Es gilt also \( \vert A_m \vert = \vert A_{n+1} \vert = n! \)

Wegen \( S_{n+1} = \cup_{m=1}^{n+1} A_m \) (disjunkt) erhalten wir somit \( \vert S_{n+1} \vert = \sum_{m=1}^{n+1} \vert A_m \vert = \sum_{m=1}^{n+1} n! = (n+1)n! = (n+1)! \)