[proofplan] We identify an element of $S_n$ with the ordered list of its values on $1,\dots,n$. Such a list is exactly an $n$-tuple in which each element of $\{1,\dots,n\}$ appears once. We then count these tuples by choosing entries successively: there are $n$ choices for the first entry, $n-1$ for the second, and so on down to one choice for the last entry. [/proofplan]

[step:Encode each permutation by its ordered list of values] Let \begin{align*} E_n := \{1,\dots,n\}. \end{align*} Define the set of ordered distinct-value lists by \begin{align*} T_n := \{(a_1,\dots,a_n) \in E_n^n : a_i \neq a_j \text{ whenever } i \neq j\}. \end{align*} Define the map \begin{align*} \Phi:S_n \to T_n,\qquad \Phi(\sigma)=(\sigma(1),\dots,\sigma(n)). \end{align*} This map is well-defined because every $\sigma \in S_n$ is injective, so the values $\sigma(1),\dots,\sigma(n)$ are pairwise distinct elements of $E_n$. The map $\Phi$ is injective: if $\Phi(\sigma)=\Phi(\tau)$ for $\sigma,\tau \in S_n$, then $\sigma(i)=\tau(i)$ for every $i \in E_n$, so $\sigma=\tau$ as functions $E_n \to E_n$. The map $\Phi$ is surjective: given $(a_1,\dots,a_n) \in T_n$, define \begin{align*} \sigma_{(a_1,\dots,a_n)}:E_n \to E_n,\qquad \sigma_{(a_1,\dots,a_n)}(i)=a_i. \end{align*} Since the entries $a_1,\dots,a_n$ are pairwise distinct and there are exactly $n$ of them in the $n$-element set $E_n$, the map $\sigma_{(a_1,\dots,a_n)}$ is bijective. Hence $\sigma_{(a_1,\dots,a_n)} \in S_n$ and $\Phi(\sigma_{(a_1,\dots,a_n)})=(a_1,\dots,a_n)$. Therefore $\Phi$ is a bijection, and finite sets in bijection have the same cardinality: \begin{align*} |S_n|=|T_n|. \end{align*} [/step]

[step:Count the distinct-value lists by successive choices]For each integer $k$ with $0 \leq k \leq n$, define \begin{align*} T_{n,k}:=\{(a_1,\dots,a_k) \in E_n^k : a_i \neq a_j \text{ whenever } i \neq j\}. \end{align*} For $k=0$, interpret $T_{n,0}$ as the singleton set containing the empty tuple, so $|T_{n,0}|=1$. For $1 \leq k \leq n$, every tuple $(a_1,\dots,a_{k-1}) \in T_{n,k-1}$ has exactly $n-(k-1)$ possible extensions to an element of $T_{n,k}$, because the new entry $a_k$ may be any element of \begin{align*} E_n \setminus \{a_1,\dots,a_{k-1}\}. \end{align*} This set has cardinality $n-k+1$. By the finite multiplication principle, \begin{align*} |T_{n,k}|=(n-k+1)|T_{n,k-1}|. \end{align*} Iterating this recurrence from $k=1$ to $k=n$ gives \begin{align*} |T_n|=|T_{n,n}|=n(n-1)\cdots 2 \cdot 1=n!. \end{align*}[/step]

[guided]The set $T_n$ records exactly the possible value lists of permutations, but it is useful to count it one coordinate at a time. For this reason, for each integer $k$ with $0 \leq k \leq n$, we define \begin{align*} T_{n,k}:=\{(a_1,\dots,a_k) \in E_n^k : a_i \neq a_j \text{ whenever } i \neq j\}. \end{align*} Thus $T_{n,k}$ is the set of valid first $k$ entries of a permutation value list. The case $k=0$ is the empty list; there is exactly one empty list, so $|T_{n,0}|=1$. Now fix an integer $k$ with $1 \leq k \leq n$. Suppose that the first $k-1$ entries have already been chosen, giving a tuple $(a_1,\dots,a_{k-1}) \in T_{n,k-1}$. To extend this tuple to a tuple in $T_{n,k}$, the next entry $a_k$ must be an element of $E_n$ that has not already appeared. Therefore the allowable choices form the set \begin{align*} E_n \setminus \{a_1,\dots,a_{k-1}\}. \end{align*} The set $\{a_1,\dots,a_{k-1}\}$ has $k-1$ elements because the tuple lies in $T_{n,k-1}$ and therefore has pairwise distinct entries. Since $E_n$ has $n$ elements, the number of allowable choices for $a_k$ is \begin{align*} n-(k-1)=n-k+1. \end{align*} This number depends only on $k$, not on the particular partial tuple. By the finite multiplication principle, the number of length-$k$ distinct-entry tuples is therefore \begin{align*} |T_{n,k}|=(n-k+1)|T_{n,k-1}|. \end{align*} Starting from $|T_{n,0}|=1$ and applying this recurrence successively gives \begin{align*} |T_{n,n}|=n(n-1)\cdots 2 \cdot 1. \end{align*} By the definition of factorial, the right-hand side is $n!$. Since $T_n=T_{n,n}$, we conclude that \begin{align*} |T_n|=n!. \end{align*}[/guided]

[step:Transfer the count back to the symmetric group] From the bijection $\Phi:S_n \to T_n$ constructed above and the count $|T_n|=n!$, we obtain \begin{align*} |S_n|=|T_n|=n!. \end{align*} This proves the asserted order formula for the [symmetric group](/page/Symmetric%20Group) $S_n$. [/step]