# 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 permutation is a square iff for each even $k$, the permutation has evenly many cycles of length $k$. I'm not sure what the best way to count them is – Wojowu Dec 29 '18 at 15:49
• @Wojowu I got the same and I think this way is not bad. – Radmir Sultamuratov Dec 29 '18 at 15:52
• This sequence is in OEIS. It's not too hard to figure out that its exponential generating function is $\prod_{k\text{ odd}}e^{x^k/k}\prod_{k\text{ even}}\left(\frac{e^{x^k/k}+e^{-x^k/k}}2\right)$. You can simplify the product over odd $k$, but the even $k$ cause trouble. I doubt there's an explicit formula for the answer. – Milo Brandt Dec 31 '18 at 0:25

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)$$.