I'm considering the symmetric group $S_n$ on $n$ letters, and a function $f: S_n \rightarrow S_n$ defined as $f(x)=x^2$. I'm interested in the kernel of this function, $G = \ker f$, which is the set of all permutations in $S_n$ for which $x^2$ is the identity permutation.
I would like to know the order of magnitude of the size of $G$. I don't need the exact size, but rather a rough estimate would be sufficient. Specifically, I'm considering the case where $n=256$. Would it be feasible to enumerate all elements of $G$ in this case?
This is the number of involutions, counted by the telephone numbers / involution numbers $I_n$, A000085 on OEIS. General results imply that it has exponential generating function
$$\sum_{n \ge 0} \frac{I_n}{n!} t^n = e^{t + \frac{t^2}{2}}$$
which gives a closed-ish form
$$I_n = \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \frac{n!}{(n-2k)! 2^k k!}$$
(this can also be proven more directly) as well as an asymptotic
$$I_n \sim \frac{1}{\sqrt{2} e^{\frac{1}{4}}} \left( \frac{n}{e} \right)^{\frac{n}{2}} \exp(\sqrt{n})$$
cited on the OEIS entry which I assume can be proven using the saddle point method. Wikipedia says it can also be proven using Stirling's approximation on the binomial summation.