Question

Prove that${\mathit{S}}_{\mathbf{n}}$ has order$\mathit{n}\mathbf{!}$ . [Hint: There are possible images for 1; after one has been chosen, there are $\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{)}$possible images for 2; etc.]

Short answer

It is proved that the order of${\mathit{S}}_{\mathbf{n}}$ is $n!$.

Step-by-step solution

Permutation

Let $\mathit{S}$be a non-empty set. A permutation on$\mathit{S}$ is defined as a bijective mapping

$\mathit{f}\mathbf{:}\mathit{S}\mathbf{\to }\mathit{S}$. If$\mathit{S}\mathbf{=}\mathbf{\{}{\mathbf{a}}_{\mathbf{1}}\mathbf{,}{\mathbf{a}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{......}\mathbf{,}{\mathbf{a}}_{\mathbf{n}}\mathbf{\}}$ .

Let one of the bijection be$\mathit{f}$ which maps${\mathit{a}}_{\mathbf{i}}$ to$\mathit{f}\mathbf{\left(}{\mathbf{a}}_{\mathbf{i}}\mathbf{\right)}$ . This is denoted by the symbol,

$\mathbf{\left(}\begin{array}{cccc}{\mathbf{a}}_{\mathbf{1}}& {\mathbf{a}}_{\mathbf{2}}& \mathbf{.}\mathbf{..}& {\mathbf{a}}_{\mathbf{n}}\\ \mathbf{f}\mathbf{\left(}{\mathbf{a}}_{\mathbf{1}}\mathbf{\right)}& \mathbf{f}\mathbf{\left(}{\mathbf{a}}_{\mathbf{2}}\mathbf{\right)}& \mathbf{.}\mathbf{..}& \mathbf{f}\mathbf{\left(}{\mathbf{a}}_{\mathbf{n}}\mathbf{\right)}\end{array}\mathbf{\right)}$

Order of a group:

The order of a group$\mathit{G}$ is defined as the number of elements in the group.

Conclusion

By the definition $S_n$, it has a collection of bijection defined on$n$symbols. And, to find its order, we have to find the number of such bijection.

If we consider the set, $S_n=\{a_1,a_2,\mathrm{.......},a_n\}$.

Then$a_1$,has$n$ choices, but after has been selected,$a_2$has $(n-1)$choices as the mappings are one-to-one. It goes in this way until we reach the last element $a_n$but there remains only one way to map. So,$a_n$ has only 1 choice.

Hence, the number of such maps is given by $n\cdot (n-1)\cdot (n-2)\mathrm{............3}\cdot 2\cdot 1=n!$.

Therefore, the order of$S_n$ is $n!$.