What is the number of squares in $S_n$? Let $$X_n=\{\sigma\mid\sigma=\tau^2 \text{ for some }\tau\in S_n\}.$$
What is the cardinality of $X_n$?
For example, permutation $(12)(3456)$ is not a square in S_n. 
I know that $X_n=A_n$ for $n\leq 5$ and $X_n\subset A_n$ for $n\geq6$. 
 A: The strategy here is to rewrite the generating function $g(x)=\sum_{k\geq 0}\left|X_k\right|\frac{x^k}{k!}$ in a way that makes it feasible for us compute its Taylor series. We can then extract $|X_k|$ from the Taylor coefficients.
As Milo mentioned in the comments, the generating function is $$g(x)=\prod_{k\text{ odd}}e^{x^k/k}\prod_{k\text{ even}}\left(\frac{e^{x^k/k}+e^{-x^k/k}}2\right)$$
Since we're multiplying like bases, the left term can be simplified to $$\prod_{k\text{ odd}}e^{x^k/k}=\text{exp}\left(\sum_{k\text{ odd}}\frac{x^{k}}{k}\right)\label{star}\tag{$\star$}$$
We can rewrite $\sum_{k\text{ odd}}\frac{x^{k}}{k}$ as 
$$\begin{eqnarray*}\sum_{k\text{ odd}}\frac{x^{k}}{k}&=&\sum_{k\text{ odd}}\frac{x^{k}}{k}+\sum_{k\text{ even}}\left(-\frac{x^{k}}{k}+\frac{x^{k}}{k}\right)\\
&=&\sum_{k\geq 1}(-1)^{k+1}\frac{x^{k}}{k}+\sum_{k\text{ even}}\frac{x^{k}}{k}
\end{eqnarray*}$$
Tack another $\sum_{k\text{ odd}}\frac{x^{k}}{k}$ to each side and we get
$$\begin{eqnarray*}\sum_{k\text{ odd}}\frac{x^{k}}{k}+\sum_{k\text{ odd}}\frac{x^{k}}{k}&=&\sum_{k\geq 1}(-1)^{k+1}\frac{x^{k}}{k}+\sum_{k\text{ even}}\frac{x^{k}}{k}+\sum_{k\text{ odd}}\frac{x^{k}}{k}\\
2\sum_{k\text{ odd}}\frac{x^{k}}{k}&=&\sum_{k\geq 1}(-1)^{k+1}\frac{x^{k}}{k}+\sum_{k\geq 1}\frac{x^{k}}{k}\\
\sum_{k\text{ odd}}\frac{x^{k}}{k}&=&\frac{1}{2}\left(\sum_{k\geq 1}(-1)^{k+1}\frac{x^{k}}{k}+\sum_{k\geq 1}\frac{x^{k}}{k}\right)\\\end{eqnarray*}$$
at which point we are haunted by the spectre of calc 2:
$$\begin{eqnarray*}\sum_{k\text{ odd}}\frac{x^{k}}{k}&=&\frac{1}{2}\left(\sum_{k\geq 1}(-1)^{k+1}\frac{x^{k}}{k}+\sum_{k\geq 1}\frac{x^{k}}{k}\right)\\
&=&\frac{1}{2}\left(\ln\left(1+x\right)-\ln\left(1-x\right)\right)\\
&=&\ln\left(\sqrt{\frac{1+x}{1-x}}\right)\end{eqnarray*}$$
So, going back to $\ref{star}$, we've got $$\prod_{k\text{ odd}}e^{x^k/k}=\text{exp}\left(\sum_{k\text{ odd}}\frac{x^{k}}{k}\right)=e^{\ln\left(\sqrt{\frac{1+x}{1-x}}\right)}=\sqrt{\frac{1+x}{1-x}}$$
and so the generating function is
$$g(x)=\sqrt{\frac{1+x}{1-x}}\prod_{k\text{ even}}\left(\frac{e^{x^k/k}+e^{-x^k/k}}2\right)$$
From here, to get the Taylor coefficients, you can just truncate the function at an appropriate $n$, $$g_n(x)=\sqrt{\frac{1+x}{1-x}}\prod_{k\text{ even}\\ \text{ }k\leq n}\left(\frac{e^{x^k/k}+e^{-x^k/k}}2\right)$$ But which $n$ is appropriate? Since $\frac{e^{x^k/k}+e^{-x^k/k}}2=1+\frac{1}{2k^2}x^{2k}+O(x^{2k+1})$, that means the $k^\text{th}$ Taylor coefficients of $g_n(x)$ will be equal to the $k^\text{th}$ Taylor coefficients of $g(x)$ for every $k$ up to $3+4n$.
Thus, if you want to know $|X_k|$, choose the smallest integer $n\geq (k-3)/4$, and compute $g_n^{(k)}(0)$.
