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

  • 5
    $\begingroup$ 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 $\endgroup$ – Wojowu Dec 29 '18 at 15:49
  • $\begingroup$ @Wojowu I got the same and I think this way is not bad. $\endgroup$ – Radmir Sultamuratov Dec 29 '18 at 15:52
  • 3
    $\begingroup$ 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. $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.