Mixing
What is the number of squares in $S_n$?
$begingroup$
Let $$X_n={sigmamidsigma=tau^2 text{ for some }tauin 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 $nleq 5$ and $X_nsubset A_n$ for $ngeq6$.
group-theory finite-groups permutations generating-functions symmetric-groups
edited Jan 8 at 8:26
Alexander Gruber♦
20k25102172
asked Dec 29 '18 at 15:30
Radmir SultamuratovRadmir Sultamuratov
724
$endgroup$
add a comment |
$begingroup$
Let $$X_n={sigmamidsigma=tau^2 text{ for some }tauin 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 $nleq 5$ and $X_nsubset A_n$ for $ngeq6$.
group-theory finite-groups permutations generating-functions symmetric-groups
edited Jan 8 at 8:26
Alexander Gruber♦
20k25102172
asked Dec 29 '18 at 15:30
Radmir SultamuratovRadmir Sultamuratov
724
$endgroup$
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_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$. 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
add a comment |
$begingroup$
Let $$X_n={sigmamidsigma=tau^2 text{ for some }tauin 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 $nleq 5$ and $X_nsubset A_n$ for $ngeq6$.
group-theory finite-groups permutations generating-functions symmetric-groups
edited Jan 8 at 8:26
Alexander Gruber♦
20k25102172
asked Dec 29 '18 at 15:30
Radmir SultamuratovRadmir Sultamuratov
724
$endgroup$
Let $$X_n={sigmamidsigma=tau^2 text{ for some }tauin 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 $nleq 5$ and $X_nsubset A_n$ for $ngeq6$.
group-theory finite-groups permutations generating-functions symmetric-groups
group-theory finite-groups permutations generating-functions symmetric-groups
edited Jan 8 at 8:26
Alexander Gruber♦
20k25102172
asked Dec 29 '18 at 15:30
Radmir SultamuratovRadmir Sultamuratov
724
edited Jan 8 at 8:26
Alexander Gruber♦
20k25102172
asked Dec 29 '18 at 15:30
Radmir SultamuratovRadmir Sultamuratov
724
edited Jan 8 at 8:26
Alexander Gruber♦
20k25102172
edited Jan 8 at 8:26
Alexander Gruber♦
20k25102172
edited Jan 8 at 8:26
Alexander Gruber♦
20k25102172
20k25102172
asked Dec 29 '18 at 15:30
Radmir SultamuratovRadmir Sultamuratov
724
asked Dec 29 '18 at 15:30
Radmir SultamuratovRadmir Sultamuratov
724
asked Dec 29 '18 at 15:30
Radmir SultamuratovRadmir Sultamuratov
724
724
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_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$. 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
add a comment |
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_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$. 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
5
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$
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
$begingroup$
@Wojowu I got the same and I think this way is not bad.
$endgroup$
– Radmir Sultamuratov
Dec 29 '18 at 15:52
3
3
$begingroup$
This sequence is in OEIS. It's not too hard to figure out that its exponential generating function is $prod_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$. 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
$begingroup$
This sequence is in OEIS. It's not too hard to figure out that its exponential generating function is $prod_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$. 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
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The strategy here is to rewrite the generating function $g(x)=sum_{kgeq 0}left|X_kright|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_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$
Since we're multiplying like bases, the left term can be simplified to $$prod_{ktext{ odd}}e^{x^k/k}=text{exp}left(sum_{ktext{ odd}}frac{x^{k}}{k}right)label{star}tag{$star$}$$
We can rewrite $sum_{ktext{ odd}}frac{x^{k}}{k}$ as
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{ktext{ odd}}frac{x^{k}}{k}+sum_{ktext{ even}}left(-frac{x^{k}}{k}+frac{x^{k}}{k}right)\
&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{ktext{ even}}frac{x^{k}}{k}
end{eqnarray*}$$
Tack another $sum_{ktext{ odd}}frac{x^{k}}{k}$ to each side and we get
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}+sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{ktext{ even}}frac{x^{k}}{k}+sum_{ktext{ odd}}frac{x^{k}}{k}\
2sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}\
sum_{ktext{ odd}}frac{x^{k}}{k}&=&frac{1}{2}left(sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}right)\end{eqnarray*}$$
at which point we are haunted by the spectre of calc 2:
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}&=&frac{1}{2}left(sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}right)\
&=&frac{1}{2}left(lnleft(1+xright)-lnleft(1-xright)right)\
&=&lnleft(sqrt{frac{1+x}{1-x}}right)end{eqnarray*}$$
So, going back to $ref{star}$, we've got $$prod_{ktext{ odd}}e^{x^k/k}=text{exp}left(sum_{ktext{ odd}}frac{x^{k}}{k}right)=e^{lnleft(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_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$
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_{ktext{ even}\ text{ }kleq n}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$ 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 $ngeq (k-3)/4$, and compute $g_n^{(k)}(0)$.
answered Jan 8 at 7:56
Alexander Gruber♦Alexander Gruber
20k25102172
$endgroup$
$begingroup$
Veery nice! Thanks!
$endgroup$
– Radmir Sultamuratov
Jan 9 at 22:18
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3055946%2fwhat-is-the-number-of-squares-in-s-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The strategy here is to rewrite the generating function $g(x)=sum_{kgeq 0}left|X_kright|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_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$
Since we're multiplying like bases, the left term can be simplified to $$prod_{ktext{ odd}}e^{x^k/k}=text{exp}left(sum_{ktext{ odd}}frac{x^{k}}{k}right)label{star}tag{$star$}$$
We can rewrite $sum_{ktext{ odd}}frac{x^{k}}{k}$ as
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{ktext{ odd}}frac{x^{k}}{k}+sum_{ktext{ even}}left(-frac{x^{k}}{k}+frac{x^{k}}{k}right)\
&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{ktext{ even}}frac{x^{k}}{k}
end{eqnarray*}$$
Tack another $sum_{ktext{ odd}}frac{x^{k}}{k}$ to each side and we get
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}+sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{ktext{ even}}frac{x^{k}}{k}+sum_{ktext{ odd}}frac{x^{k}}{k}\
2sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}\
sum_{ktext{ odd}}frac{x^{k}}{k}&=&frac{1}{2}left(sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}right)\end{eqnarray*}$$
at which point we are haunted by the spectre of calc 2:
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}&=&frac{1}{2}left(sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}right)\
&=&frac{1}{2}left(lnleft(1+xright)-lnleft(1-xright)right)\
&=&lnleft(sqrt{frac{1+x}{1-x}}right)end{eqnarray*}$$
So, going back to $ref{star}$, we've got $$prod_{ktext{ odd}}e^{x^k/k}=text{exp}left(sum_{ktext{ odd}}frac{x^{k}}{k}right)=e^{lnleft(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_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$
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_{ktext{ even}\ text{ }kleq n}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$ 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 $ngeq (k-3)/4$, and compute $g_n^{(k)}(0)$.
answered Jan 8 at 7:56
Alexander Gruber♦Alexander Gruber
20k25102172
$endgroup$
$begingroup$
Veery nice! Thanks!
$endgroup$
– Radmir Sultamuratov
Jan 9 at 22:18
add a comment |
$begingroup$
The strategy here is to rewrite the generating function $g(x)=sum_{kgeq 0}left|X_kright|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_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$
Since we're multiplying like bases, the left term can be simplified to $$prod_{ktext{ odd}}e^{x^k/k}=text{exp}left(sum_{ktext{ odd}}frac{x^{k}}{k}right)label{star}tag{$star$}$$
We can rewrite $sum_{ktext{ odd}}frac{x^{k}}{k}$ as
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{ktext{ odd}}frac{x^{k}}{k}+sum_{ktext{ even}}left(-frac{x^{k}}{k}+frac{x^{k}}{k}right)\
&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{ktext{ even}}frac{x^{k}}{k}
end{eqnarray*}$$
Tack another $sum_{ktext{ odd}}frac{x^{k}}{k}$ to each side and we get
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}+sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{ktext{ even}}frac{x^{k}}{k}+sum_{ktext{ odd}}frac{x^{k}}{k}\
2sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}\
sum_{ktext{ odd}}frac{x^{k}}{k}&=&frac{1}{2}left(sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}right)\end{eqnarray*}$$
at which point we are haunted by the spectre of calc 2:
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}&=&frac{1}{2}left(sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}right)\
&=&frac{1}{2}left(lnleft(1+xright)-lnleft(1-xright)right)\
&=&lnleft(sqrt{frac{1+x}{1-x}}right)end{eqnarray*}$$
So, going back to $ref{star}$, we've got $$prod_{ktext{ odd}}e^{x^k/k}=text{exp}left(sum_{ktext{ odd}}frac{x^{k}}{k}right)=e^{lnleft(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_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$
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_{ktext{ even}\ text{ }kleq n}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$ 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 $ngeq (k-3)/4$, and compute $g_n^{(k)}(0)$.
answered Jan 8 at 7:56
Alexander Gruber♦Alexander Gruber
20k25102172
$endgroup$
$begingroup$
Veery nice! Thanks!
$endgroup$
– Radmir Sultamuratov
Jan 9 at 22:18
add a comment |
$begingroup$
The strategy here is to rewrite the generating function $g(x)=sum_{kgeq 0}left|X_kright|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_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$
Since we're multiplying like bases, the left term can be simplified to $$prod_{ktext{ odd}}e^{x^k/k}=text{exp}left(sum_{ktext{ odd}}frac{x^{k}}{k}right)label{star}tag{$star$}$$
We can rewrite $sum_{ktext{ odd}}frac{x^{k}}{k}$ as
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{ktext{ odd}}frac{x^{k}}{k}+sum_{ktext{ even}}left(-frac{x^{k}}{k}+frac{x^{k}}{k}right)\
&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{ktext{ even}}frac{x^{k}}{k}
end{eqnarray*}$$
Tack another $sum_{ktext{ odd}}frac{x^{k}}{k}$ to each side and we get
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}+sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{ktext{ even}}frac{x^{k}}{k}+sum_{ktext{ odd}}frac{x^{k}}{k}\
2sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}\
sum_{ktext{ odd}}frac{x^{k}}{k}&=&frac{1}{2}left(sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}right)\end{eqnarray*}$$
at which point we are haunted by the spectre of calc 2:
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}&=&frac{1}{2}left(sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}right)\
&=&frac{1}{2}left(lnleft(1+xright)-lnleft(1-xright)right)\
&=&lnleft(sqrt{frac{1+x}{1-x}}right)end{eqnarray*}$$
So, going back to $ref{star}$, we've got $$prod_{ktext{ odd}}e^{x^k/k}=text{exp}left(sum_{ktext{ odd}}frac{x^{k}}{k}right)=e^{lnleft(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_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$
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_{ktext{ even}\ text{ }kleq n}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$ 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 $ngeq (k-3)/4$, and compute $g_n^{(k)}(0)$.
answered Jan 8 at 7:56
Alexander Gruber♦Alexander Gruber
20k25102172
$endgroup$
The strategy here is to rewrite the generating function $g(x)=sum_{kgeq 0}left|X_kright|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_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$
Since we're multiplying like bases, the left term can be simplified to $$prod_{ktext{ odd}}e^{x^k/k}=text{exp}left(sum_{ktext{ odd}}frac{x^{k}}{k}right)label{star}tag{$star$}$$
We can rewrite $sum_{ktext{ odd}}frac{x^{k}}{k}$ as
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{ktext{ odd}}frac{x^{k}}{k}+sum_{ktext{ even}}left(-frac{x^{k}}{k}+frac{x^{k}}{k}right)\
&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{ktext{ even}}frac{x^{k}}{k}
end{eqnarray*}$$
Tack another $sum_{ktext{ odd}}frac{x^{k}}{k}$ to each side and we get
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}+sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{ktext{ even}}frac{x^{k}}{k}+sum_{ktext{ odd}}frac{x^{k}}{k}\
2sum_{ktext{ odd}}frac{x^{k}}{k}&=&sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}\
sum_{ktext{ odd}}frac{x^{k}}{k}&=&frac{1}{2}left(sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}right)\end{eqnarray*}$$
at which point we are haunted by the spectre of calc 2:
$$begin{eqnarray*}sum_{ktext{ odd}}frac{x^{k}}{k}&=&frac{1}{2}left(sum_{kgeq 1}(-1)^{k+1}frac{x^{k}}{k}+sum_{kgeq 1}frac{x^{k}}{k}right)\
&=&frac{1}{2}left(lnleft(1+xright)-lnleft(1-xright)right)\
&=&lnleft(sqrt{frac{1+x}{1-x}}right)end{eqnarray*}$$
So, going back to $ref{star}$, we've got $$prod_{ktext{ odd}}e^{x^k/k}=text{exp}left(sum_{ktext{ odd}}frac{x^{k}}{k}right)=e^{lnleft(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_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$
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_{ktext{ even}\ text{ }kleq n}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$$ 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 $ngeq (k-3)/4$, and compute $g_n^{(k)}(0)$.
answered Jan 8 at 7:56
Alexander Gruber♦Alexander Gruber
20k25102172
edited Jan 8 at 19:53
answered Jan 8 at 7:56
Alexander Gruber♦Alexander Gruber
20k25102172
answered Jan 8 at 7:56
Alexander Gruber♦Alexander Gruber
20k25102172
answered Jan 8 at 7:56
Alexander Gruber♦Alexander Gruber
20k25102172
20k25102172
$begingroup$
Veery nice! Thanks!
$endgroup$
– Radmir Sultamuratov
Jan 9 at 22:18
add a comment |
$begingroup$
Veery nice! Thanks!
$endgroup$
– Radmir Sultamuratov
Jan 9 at 22:18
$begingroup$
Veery nice! Thanks!
$endgroup$
– Radmir Sultamuratov
Jan 9 at 22:18
$begingroup$
Veery nice! Thanks!
$endgroup$
– Radmir Sultamuratov
Jan 9 at 22:18
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3055946%2fwhat-is-the-number-of-squares-in-s-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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_{ktext{ odd}}e^{x^k/k}prod_{ktext{ even}}left(frac{e^{x^k/k}+e^{-x^k/k}}2right)$. 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