**The question**


What is the order of magnitude for the function $n\mapsto |{\rm cd}(S\_n)|$?


**The motivation**


In my research on character degrees of finite groups, I have in recent years been focusing on symmetric groups as a test bed for general conjectures. Among my more recent investigations, I have come up with (what is to me, at least) an interesting reduction: I can prove a statement true regarding the full set ${\rm cd}(S\_n)$ of degrees of irreducible, complex-valued characters on the symmetric group of degree $n$ (for a fixed $n$) by showing a statement is true regarding the set of primes $\{p\leq n\mid p~{\rm is~prime}\}$. What I would like is to develop a feeling for just how much of a reduction this is. Obviously, the prime counting function is approximated by $n/\ln n$, but I don't have a feel for, as a function of $n$, how quickly the function $|{\rm cd}(S\_n)|$ grows. I have a reduction in effort *to* a sublinear function, and I would like to know what that reduction is *from*. Is it quadratic, is it exponential? 


**The (failed) searches**


As an aside, I admit that part of my problem is knowing how to conduct the research. For example, if I do a Google search for "how quickly does |cd(Sn)| grow", I get results pertaining to cancer. If I add "math:" at the beginning, the returns are from freshmen calculus involving convergence of sequences. When I write things out in words using no symbols, other issues become evident. Such searches, when correctly limited to math, are further complicated by the dual use of the word "degree" in this context, the degree of the permutation group versus the degrees of the representations. Furthermore, results abound on the maximal norm of character values and asymptotics related to those values. But, results on the order of magnitute for the function $n\mapsto |{\rm cd}(S\_n)|$ are at the very least very well hidden. (OK, not so much; a comment below points out there is an OEIS entry).



Growth rate of $|{\rm cd}(S_n)|$
If $cd(S\_n)$ is the set of degrees of irreducible, complex-valued characters on the symmetric group $S\_n$, then by the basic representation theory of the symmetric group this is the same as the set $\{f^{\lambda}\colon \lambda\vdash n\}$, where for a partition $\lambda\vdash n$, $f^{\lambda}$ is the number of Standard Young Tableaux of shape $\lambda$, which by the hook-length formula has the explicit form $f^{\lambda}=n! \cdot \prod\_{u \in \lambda}\frac{1}{h\_u!}$. I would imagine that the number of pairs of partitions $\lambda,\nu \vdash n$ with $f^{\lambda}=f^{\nu}$ is very small as a fraction of all pairs of partitions of $n$. And probably that would not be hard to formally establish (for instance using the hook-length formula). So the size $|cd(S\_n)|$ of the set of degrees of irreps should be basically the same as the number of partitions on $n$. This is a very famous quantity whose asymptotics are well-understood (in particular the partition number is known grow super-polynomially; for a starting point see e.g. the Wikipedia entry <https://en.wikipedia.org/wiki/Partition_function_(number_theory)>).


EDIT: As pointed out in the comments below, there are some collisions you do have to worry about if you want to understand precise asymptotics (e.g. a partition and its transpose have the same number of SYT), but nevertheless if you just want to establish that $|cd(S\_n)|$ grows super-polynomially, surely this naive reasoning should be enough.


EDIT 2: In the comments a heuristic why there should be few collisions was requested. A simple heuristic why there should be few collisions of values of $f^\lambda$ is that the maximum value of $f^\lambda$ over $\lambda \vdash n$ is on the order of $\sqrt{n!}e^{-\alpha\sqrt{n}}$ (see e.g. <https://arxiv.org/abs/1804.04693>), while $f^\lambda$ can be as small as one, so the range of values taken on by $f^\lambda$ is quite large (compared to say the number of partitions of $n$).


