The number of distinct subgroups of the symmetric group on n points are given for n ≤ 13 in oeis:A005432, the number of conjugacy classes of subgroups is oeis:A000638 for n ≤ 18, and the number of (abstract) isomorphism classes amongst the subgroups is oeis:A174511 for n ≤ 10 (I get 894 for n=11, 2065 for n=12, 3845 for n=13, and I think 7872 for n=14).
To give a feel for these numbers, I include them in a table below for n ≤ 15. I also include the number of transitive subgroups of Sn, since this is a very different number. The number of conjugacy classes is also known as the number of permutation groups (transitive and intransitive alike). As far as I know, combining the transitive groups to form intransitive groups involves an enormous amount of book-keeping and calculation and so has not been done (the number of transitive groups are known up into the 30s and maybe up to n ≤ 63 by now). I do not include the naive estimate of $2^{n!}$ since for $n=5$ one gets 1329227995784915872903807060280344576, which is quite a bit bigger than the number of subgroups, which is 156.
$$\begin{array}{r|rrrrrrrrrr}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
\#sub & 1 & 2 & 6 & 30 & 156 & 1455 & 11300 & 151221 & 1694723 & 29594446 \\
\#ccs & 1 & 2 & 4 & 11 & 19 & 56 & 96 & 296 & 554 & 1593 \\
\#iso & 1 & 2 & 4 & 9 & 16 & 29 & 55 & 137 & 241 & 453 \\
\#trn & 1 & 1 & 2 & 5 & 5 & 16 & 7 & 50 & 34 & 45 \\
\end{array}$$
$$\begin{array}{r|rrrrr}
n & 11 & 12 & 13 & 14 & 15 \\ \hline
\#sub & 404126228 & 10594925360 & 175238308453 & 5651774693595 & ? \\
\#ccs & 3094 & 10723 & 20832 & 75154 & 159129 \\
\#iso & 894 & 2065 & 3845 & 7872 & ? \\
\#trn & 8 & 301 & 9 & 63 & 104 \\
\end{array}$$
No known method is particularly "efficient" in n, otherwise one would have calculated these quite a bit further. To find the number of subgroups given the conjugacy classes of subgroups, one takes a representative of each conjugacy class of subgroups, and sums the indices of the normalizers. In particular, #sub is not much harder than #ccs to calculate, but it is much much larger and less useful.
Asymptotics on these numbers are fairly different than these early terms, but are given in Pyber (1993) and Pyber-Shalev (1997):
- $2^{\left(\tfrac1{16}+o(1)\right)n^2} \leq \#\text{sub} \leq 24^{\left(\tfrac16+o(1)\right)n^2}$ with the lower bound conjectured to be tight.
- $\log(\#\text{sub}) = \Theta(n^2)$, in other words
- $\log(\#\text{ccs}) = \Theta(n^2)$, because a subgroup can have at most $n!$ conjugates, and $n!$ is so tiny
- $C^{n^2/\log(n)} \leq \#\text{iso}$ for some $C>1$
The lower bounds are mostly obtained by considering p-subgroups which dominate once n is sufficiently large. The upper bound requires the CFSG to control the insoluble subgroups. I didn't see the upper bound for #iso, but of course one can use #iso ≤ #ccs.
As requested, here is a summary of the points raised in the comments.
The argument as posted in the question is very nearly complete.
As is true for any homomorphism, $Ker(\phi)$ is a normal subgroup. Of course, $S_5$ really hasn't got any normal subgroups. There is $S_5$ itself, the trivial group, and $A_5$. Now, as was sorted out in the question itself, the fact that all the $5$-Sylow subgroups are conjugate implies that $Im(\phi)$ is non-trivial, it has to have at least $6$ elements! It follows that $Ker(\phi)≤20$. That rules out both the complete group $S_5$ and the alternating group $A_5$, so $Ker(\phi)$ must be trivial. As was pointed out (correctly) in the question this is all that was needed to complete the argument.
Best Answer
Yes. If a group $G$ of order $n$ acts on a set $X$ of size $n$ transitively, then the stabilizer must be trivial, so $X$ must be isomorphic to the left regular representation of $G$. In particular there is a unique isomorphism class of such action, so any two such actions on $X$ must be conjugate.
(The left and right regular representations are isomorphic, if by the right regular representation you mean $\rho(g) x = xg^{-1}$. The isomorphism sends $x$ to $x^{-1}$.)