Number of orbits of $k$-subsets of permutations

Abstract

Let $S_n$ denote the symmetric group of order $n$. Say that two subsets $x,y\subseteq S_n$ are \emph{equivalent} if there exist permutations $g_1,g_2\in S_n$ such that $g_{1}x{g}_2=y$, where multiplication is understood elementwise. Recently, [Tripathi, 2024] and [Kushwaha and Triathi, 2025] asked for the asymptotics of $T(n,k)$, the number of subsets of $S_n$ of size $k$ up to this equivalence. It is easy to see that $T(n,0)=T(n,1)=1$ and $T(n,2)=p(n)-1$, where $p(n)$ is the number of integer partitions of $n$. In this work, we show that $T(n,k)={\Lambda }_n(k)(1+o_n(1))$ for $3\le k\le n!-3$, where ${\Lambda }_n(k)=\frac{1}{n{!}^2}\left(\genfrac{}{}{0ex}{}{n!}{k}\right)$. Furthermore, we prove that $$\frac{1}{{\Lambda }_n(n!/2)}T\left(n,\left[\sqrt{\frac{n!}{4}}x+\frac{n!}{2}\right]\right)\stackrel{n\to \infty }{\to }\exp \left(-\frac{x^2}{2}\right),$$ uniformly over $\mathbb{R}$.