What is the number of squares in $S_n$?

Solution 1:

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