Generally speaking, finding all the subgroups of a finite group is a very difficult problem. But because $S_3$ is finite and of small order, it is possible to use brute force to find all of the subgroups. I need to know both a general method for calculating the subgroup structure by brute force and see how this is applied to the group $S_3$ step-by-step. If I don't see it done step-by-step, I cannot understand it.
[Math] How to find all the subgroups of the symmetry group of an equilateral triangle
algorithmsdihedral-groupsfinite-groupsgroup-theorysymmetric-groups
Related Solutions
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
Here's a brute force method (for finite groups $G$).
First, find all the cyclic subgroups, that is, for each $g$ in $G$, find the subgroup generated by $g$.
Then, find all the two-generator subgroups. For each cyclic subgroup $H$, and each element $g$ in $G$ but not in $H$, find the subgroup generated by $H$ and $g$, that is, the smallest subgroup containing both $H$ and $g$.
Then, find all the three-generator subgroups, then all the four-generator subgroups, etc.
There are shortcuts. Keep in mind that the order of a proper subgroup can't exceed half the order of the group, so as soon as you see that some set of generators gives you more than half the elements of the group, you can stop.