I've always heard that it's trivial that $|S_n|=n!$ where $S_n$ is the symmetric group of degree $n$. Now, my proof was the following: consider $I_n=\{1,\dots,n\}$ and consider $\mathcal{I}=\prod_{k=1}^n I_n$. Set the following map $\varphi : S_n\to \mathcal{I}$ given by $\varphi(f) = (f(1),\dots,f(n))$. If we denote $A=\varphi(S_n)$, the obviously $\varphi$ is surjective over $A$. Also, it's injective, because if $\varphi(f)=\varphi(g)$, then for each $i$, $f(i)=g(i)$ and hence $f=g$. In that case $|S_n|=|A|$.

Finally, to find $|A|$ we argue as follows, if $(i_1,\dots,i_n)\in A$, then there's a function $f : I_n\to I_n$ that is bijective and such that $i_k = f(k)$. Because of that, there are $n$ possible values for $i_1$. When such a value is selected, since the function must be injective, there are remaining $n-1$ values for $i_2$, and so on, until $i_n$. In that case, there are $n!$ objects to choose, and hence $|S_n|=n!$.

I think this proof is not good, I feel it's not rigorous. Is this proof allright? If not, how can I improve it?

Thanks very much in advance!

  • 1
    $\begingroup$ Just think of how many ways are there to put the numbers ${1,2,..,N}$ in line.There are $n!$ ways. Simple combinatorics:) $\endgroup$ – Haha Oct 30 '13 at 14:12
  • $\begingroup$ The approach in the second paragraph is correct. In the first paragraph you seem to be carefully constucting a correspondence between elements of $S_n$ and functions $f:I_n\rightarrow I_n$ -- but your elements of $S_n$ were exactly such functions to begin with. I'd suggest you're worrying too much about 'rigour' here, it's just disguising your perfectly good argument. $\endgroup$ – aPaulT Oct 30 '13 at 15:45

Yes, your proof is correct.

However, it would be more rigorous if you had a clear definition of $S_n$ to start with.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.