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.
I think that for small groups like $S_3$ this not very difficult to do by hand.
$S_3=\{id,(12),(13),(23),(123),(132)\}$
Clearly, $\{id\}$ and $S_3$ are subgroups of $S_3$
Now let us have a look at subgroups generated by one elements (cyclic subgroups). (We only have 6 elements to try, and we have already considered $[id]=\{id\}$.)
$[(12)]=\{id,(12)\}$
$[(13)]=\{id,(13)\}$
$[(23)]=\{id,(23)\}$
$[(123)]=[(132)]=\{id,(123),(132)\}$
Is this list of all subgroups? Yes, it is.
We can do this by trial and error -- trying adding one element to subgroup from our list and checking whether they generate the whole group $S_3$. (Which seems tedious, but in fact we only have to check whether any subgroup containing at least one 2-cycle and at least one 3-cycle is the whole $S_3$; and also observe that two different 2-cycles give us a 3-cycle.)
But quicker way is to notice that any proper subgroup of $S_3$ must have 1, 2 or 3 elements. (Order of subgroup must divide order of the group.) And any group of prime order is cyclic. So by enumerating cyclic subgroups we have obtain list
of all proper subgroups of $S_3$.
We can check our result at groupprops wiki (or elsewhere): Subgroup structure of symmetric group:S3.
You also asked about $S_4$. As I have mentioned in my comment, there is another question on this site about subgroups of $S_4$: How to enumerate subgroups of each order of $S_4$ by hand
Best Answer
A subgroup of $S_6$ must, of course, contain the identity permutation id.
A subgroup of order three, say $A\leq S_6$, must must then contain two additional permutations, $\varphi$ and $\tau$ such that $\varphi^3 = \tau^3 = id$, each of which generates $A$, and such that $\varphi$ and $\tau$ are inverses of each other. Take, for example, the two 3-cycles $\varphi = (1 , 2, 3)\in S_6$ and $\tau = \varphi^2 = (1, 3, 2) \in S_6$. They are inverses of each other; you can check $\varphi ^3 = \tau ^3 = id.$ So each is of order $3$, and $\varphi \circ \tau = (1, 2, 3)(1, 3, 2) = \tau \circ \varphi = id $, so they are inverses of each other. Hence $A = \{id, (1, 2, 3), (1, 3, 2)\}$ is a subgroup of $S_6$.
Hence, $A$ is a subgroup of $S_6$ of order $3$. Your task is to determine how many such subgroups of order $3$ exist in $S_6$.
Theorem: The order of a cycle is equal to its length. The order of a product of disjoint cycles of lengths $i, j$ is equal to the $\text{lcm}(i, j)$.
So in $S_6$, (a) all permutations that are cycles of length $3$, and (b) all permutations that are the product of two disjoint cycles each of length $3$, like, say, $(2, 4, 6)(1, 3, 5)$, are of order $3$, and no other cycle-types are. Every subgroup of order three contains two distinct 3-cycles and the identity, or else two distinct products of disjoint 3-cycles.
Count all such permutations of type (a) or (b) in $S_6$ divide by 2, and you'll have the number of subgroups of $S_6$ whose order is $3$.