Do we have a formula to calculate the number of subgroups of $S_n$?

Question

I’ve seen a lot of information about the symmetric group $S_n$, and, when it comes down to numbers, it is always covered the number of “normal subgroups” or the existence of a “subgroup of order $k$”. But, is there a formula to actually “count” the total number of subgroups that $S_n$ will have as a function of the parameter $n$?

Answer 1

Probably no closed-form formula exists: Like Arthur wrote in his comment, none are given in the OEIS entry (A005432) for the sequence $(a_n)$ of the counts of subgroups of $S_n$. The GAP command for generating the sequence given in the OEIS entry is the naive one:

List([2..5], n->Sum( List( ConjugacyClassesSubgroups( SymmetricGroup(n)), Size)));

The entry gives explicit values $a_n$ for $n = 1, \ldots, 18$, respectively, and perhaps these are all that are known:

\begin{multline}1, 2, 6, 30, 156, 1455, 11300, 151221, 1694723, 29594446, 404126228,\\ 10594925360, 175238308453, 5651774693595, 117053117995400,\\ 5320744503742316, 125889331236297288, 7598016157515302757\end{multline}

For example, the subgroups of the symmetric group $S_3$ on $3$ symbols, say, $1,2,3$, are $$\{1\}, \langle (12) \rangle, \langle (13) \rangle, \langle (23) \rangle, A_3, S_3,$$ so $a_3 = 6$.

Asymptotic bounds for $a_n$ are known, but they are loose: Corollary 3.3 of Pyber's "Enumerating Finite Groups of Given Order" gives that $$(2^{\frac1{16}})^{n^2(1+o(1))} \leq a_n \leq (24^\frac16)^{(n^2(1+o(1))} .$$ (Here, $2^{\frac1{16}} \approx 1.044273782$ and $24^\frac16 \approx 1.698381330$.) The author conjectures that the lower bound is sharp.

L. Pyber, "Enumerating Finite Groups of Given Order," Ann. Math. , Second Series, 137(1) (Jan. 1993), pp. 203-220. https://www.jstor.org/stable/2946623 https://doi.org/10.2307/2946623