# Counting symmetric subgroups of symmetric groups

This question is related to, but much more specific than, this one.

For $k \leq n$, let $a(k,n)$ denote the number of conjugacy classes of subgroups of the symmetric group $S_n$ which are isomorphic to $S_{n-k}$. It is straightforward (see this argument by Christopher Ryba), but not trivial, to show that for $n \neq 6$ we have $a(1,n)=1$.

It is easy to see that $a(2,n) \geq 2$, since we have the standard embedding $S_{n-2} \subset S_n$ as well as the one which sends odd permutations $\sigma$ to $\sigma (n-1 \: n)$. More generally, by adding some transpositions to the odd permutations, we get that $a(k,n) \geq \lfloor k/2 \rfloor +1$.

Weird things happen to the sequences $a(k,n)_{n=1,2,3,...}$ when $n-k \leq 5 < n$ because of the exotic copy of $S_5$ in $S_6$, but it seems that they may stabilize after this.

Question: Does $A(k):=\lim_{n \to \infty} a(k,n)$ exist for all $k$? Is there a reasonable formula (maybe just $\lfloor k/2 \rfloor +1$)?

• There are also some other embeddings like $S_n \subset S_{2n}$ by taking two copies of $S_n$. But they are of no consequence for your limit. – ARG Jun 7 '18 at 4:51

Claim: Indeed, $$A(k)=\lfloor k/2 \rfloor$$ + 1 for all $$k$$.
Proof: Fix $$k$$. Suppose we have an embedding $$S_{n-k} \hookrightarrow S_n$$; this is the same as a faithful action of $$S_{n-k}$$ on $$[n]=\{1,2,...,n\}$$ (and classifying embeddings up to conjugacy is the same as classifying these $$S_{n-k}$$-sets up to isomorphism). Now if we have orbits $$[n]=\bigsqcup_i \mathcal{O}_i$$, we get $$\sum_i |S_{n-k}:Stab(\mathcal{O}_i)|=\sum_i|\mathcal{O}_i|=n.$$
So we want to understand potential (conjugacy classes of ) subgroups $$G=Stab(\mathcal{O})$$ of $$S_{n-k}$$ of small index. I have recently learned that this is a very well-studied subject. In particular Theorem 5.2B of Dixon and Mortimer's "Permutation Groups" implies that, with finitely many exceptions which don't affect the limit, the only possibilities with small enough index are $$G=S_{n-k}, S_{n-k-1},$$ or $$A_{n-k}$$ of indices $$1,n-k,$$ and $$2$$, with the standard embeddings.
Since our action must be faithful, at least one stabilizer must be $$S_{n-k-1}$$, and for $$n$$ at least $$2k$$ there can only be one. The rest of the orbits have stabilizers of order 1 or 2 and correspond to adding fixed points to $$\sigma$$ or 2-cycles to the odd permutations as in the question. Thus the number of embeddings up to conjugacy in the limit is the number of ways to write $$k=2a+b$$ with $$a,b \in \mathbb{Z}_{\geq 0}$$, which is $$\lfloor k/2 \rfloor + 1$$.