Enumerating all permutations that are “square roots” of derangementsNon-enumerative proof that there are many derangements?Statistics on Lehmer codesNon-enumerative proof that there are many simple permutations?Are there enough additive permutations?What is the criterion for a matrix containing vectors and their permutations being invertible?The number of permutations with a special conditionOdd permutations $tauin S_n$ with $sum_k=1^nktau(k)$ an odd square
Enumerating all permutations that are “square roots” of derangements
Non-enumerative proof that there are many derangements?Statistics on Lehmer codesNon-enumerative proof that there are many simple permutations?Are there enough additive permutations?What is the criterion for a matrix containing vectors and their permutations being invertible?The number of permutations with a special conditionOdd permutations $tauin S_n$ with $sum_k=1^nktau(k)$ an odd square
$begingroup$
Is there an algorithm that enumerates all permutations that are "square roots" of derangements, i.e. permutations that, when applied twice, yield a derangement?
Other information about those kind of permutations is also welcome.
permutations enumerative-combinatorics
asked Sep 27 at 17:39
Manfred WeisManfred Weis
8,2482 gold badges16 silver badges48 bronze badges
$endgroup$
|
show 2 more comments
$begingroup$
Is there an algorithm that enumerates all permutations that are "square roots" of derangements, i.e. permutations that, when applied twice, yield a derangement?
Other information about those kind of permutations is also welcome.
permutations enumerative-combinatorics
asked Sep 27 at 17:39
Manfred WeisManfred Weis
8,2482 gold badges16 silver badges48 bronze badges
$endgroup$
1
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
Sep 27 at 17:43
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
Sep 27 at 17:49
6
$begingroup$
It is a classic result (attributed to Touchard?) that the generating function for the cycle index polynomials of symmetric groups is $sum_n geq 0 fracx^nn! sum_sigma in mathfrakS_n t_1^c_1(sigma)t_2^c_2(sigma)cdots = e^t_1 fracx1 + t_2fracx^22 + t_3fracx^33 + cdots$, where $c_k(sigma)$ is the number of cycles of $sigma$ of length $k$. Specializing $t_1=t_2=0$ and $t_3=t_4=cdots=1$ gives the generating function for the permutations you want to count. This should easily allow you to enumerate them.
$endgroup$
– Sam Hopkins
Sep 27 at 17:52
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
Sep 27 at 18:00
$begingroup$
The cycle index polynomials that Sam mentions are also discussed in Stanley's Enumerative Combinatorics, v2, Example 5.2.10, which goes on to consider "$r$th roots" of the identity permutation.
$endgroup$
– Brian Hopkins
Sep 27 at 18:23
|
show 2 more comments
$begingroup$
Is there an algorithm that enumerates all permutations that are "square roots" of derangements, i.e. permutations that, when applied twice, yield a derangement?
Other information about those kind of permutations is also welcome.
permutations enumerative-combinatorics
asked Sep 27 at 17:39
Manfred WeisManfred Weis
8,2482 gold badges16 silver badges48 bronze badges
$endgroup$
Is there an algorithm that enumerates all permutations that are "square roots" of derangements, i.e. permutations that, when applied twice, yield a derangement?
Other information about those kind of permutations is also welcome.
permutations enumerative-combinatorics
permutations enumerative-combinatorics
asked Sep 27 at 17:39
Manfred WeisManfred Weis
8,2482 gold badges16 silver badges48 bronze badges
asked Sep 27 at 17:39
Manfred WeisManfred Weis
8,2482 gold badges16 silver badges48 bronze badges
asked Sep 27 at 17:39
Manfred WeisManfred Weis
8,2482 gold badges16 silver badges48 bronze badges
asked Sep 27 at 17:39
Manfred WeisManfred Weis
8,2482 gold badges16 silver badges48 bronze badges
asked Sep 27 at 17:39
Manfred WeisManfred Weis
8,2482 gold badges16 silver badges48 bronze badges
8,2482 gold badges16 silver badges48 bronze badges
1
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
Sep 27 at 17:43
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
Sep 27 at 17:49
6
$begingroup$
It is a classic result (attributed to Touchard?) that the generating function for the cycle index polynomials of symmetric groups is $sum_n geq 0 fracx^nn! sum_sigma in mathfrakS_n t_1^c_1(sigma)t_2^c_2(sigma)cdots = e^t_1 fracx1 + t_2fracx^22 + t_3fracx^33 + cdots$, where $c_k(sigma)$ is the number of cycles of $sigma$ of length $k$. Specializing $t_1=t_2=0$ and $t_3=t_4=cdots=1$ gives the generating function for the permutations you want to count. This should easily allow you to enumerate them.
$endgroup$
– Sam Hopkins
Sep 27 at 17:52
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
Sep 27 at 18:00
$begingroup$
The cycle index polynomials that Sam mentions are also discussed in Stanley's Enumerative Combinatorics, v2, Example 5.2.10, which goes on to consider "$r$th roots" of the identity permutation.
$endgroup$
– Brian Hopkins
Sep 27 at 18:23
|
show 2 more comments
1
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
Sep 27 at 17:43
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
Sep 27 at 17:49
6
$begingroup$
It is a classic result (attributed to Touchard?) that the generating function for the cycle index polynomials of symmetric groups is $sum_n geq 0 fracx^nn! sum_sigma in mathfrakS_n t_1^c_1(sigma)t_2^c_2(sigma)cdots = e^t_1 fracx1 + t_2fracx^22 + t_3fracx^33 + cdots$, where $c_k(sigma)$ is the number of cycles of $sigma$ of length $k$. Specializing $t_1=t_2=0$ and $t_3=t_4=cdots=1$ gives the generating function for the permutations you want to count. This should easily allow you to enumerate them.
$endgroup$
– Sam Hopkins
Sep 27 at 17:52
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
Sep 27 at 18:00
$begingroup$
The cycle index polynomials that Sam mentions are also discussed in Stanley's Enumerative Combinatorics, v2, Example 5.2.10, which goes on to consider "$r$th roots" of the identity permutation.
$endgroup$
– Brian Hopkins
Sep 27 at 18:23
1
1
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
Sep 27 at 17:43
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
Sep 27 at 17:43
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
Sep 27 at 17:49
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
Sep 27 at 17:49
6
6
$begingroup$
It is a classic result (attributed to Touchard?) that the generating function for the cycle index polynomials of symmetric groups is $sum_n geq 0 fracx^nn! sum_sigma in mathfrakS_n t_1^c_1(sigma)t_2^c_2(sigma)cdots = e^t_1 fracx1 + t_2fracx^22 + t_3fracx^33 + cdots$, where $c_k(sigma)$ is the number of cycles of $sigma$ of length $k$. Specializing $t_1=t_2=0$ and $t_3=t_4=cdots=1$ gives the generating function for the permutations you want to count. This should easily allow you to enumerate them.
$endgroup$
– Sam Hopkins
Sep 27 at 17:52
$begingroup$
It is a classic result (attributed to Touchard?) that the generating function for the cycle index polynomials of symmetric groups is $sum_n geq 0 fracx^nn! sum_sigma in mathfrakS_n t_1^c_1(sigma)t_2^c_2(sigma)cdots = e^t_1 fracx1 + t_2fracx^22 + t_3fracx^33 + cdots$, where $c_k(sigma)$ is the number of cycles of $sigma$ of length $k$. Specializing $t_1=t_2=0$ and $t_3=t_4=cdots=1$ gives the generating function for the permutations you want to count. This should easily allow you to enumerate them.
$endgroup$
– Sam Hopkins
Sep 27 at 17:52
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
Sep 27 at 18:00
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
Sep 27 at 18:00
$begingroup$
The cycle index polynomials that Sam mentions are also discussed in Stanley's Enumerative Combinatorics, v2, Example 5.2.10, which goes on to consider "$r$th roots" of the identity permutation.
$endgroup$
– Brian Hopkins
Sep 27 at 18:23
$begingroup$
The cycle index polynomials that Sam mentions are also discussed in Stanley's Enumerative Combinatorics, v2, Example 5.2.10, which goes on to consider "$r$th roots" of the identity permutation.
$endgroup$
– Brian Hopkins
Sep 27 at 18:23
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Check out "Example 2. Permutations with no small cycles" on pg. 176 of H. Wilf's "generatingfunctionology": https://www.math.upenn.edu/~wilf/DownldGF.html. It explains, using generating functions, how the number of permutations in $mathfrakS_n$ you are looking for is asymptotically $approx frac1e^1+1/2 n!$, just like the number of derangements is $approx frac1e n!$. In general the fraction of permutations with cycles all of length $>q$ is $e^-H_q$ where $H_q = 1+1/2+1/3+...+1/q$.
answered Sep 27 at 18:21
Sam HopkinsSam Hopkins
9,8771 gold badge35 silver badges77 bronze badges
$endgroup$
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "504"
;
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/4.0/"u003ecc by-sa 4.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%2fmathoverflow.net%2fquestions%2f342613%2fenumerating-all-permutations-that-are-square-roots-of-derangements%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$
Check out "Example 2. Permutations with no small cycles" on pg. 176 of H. Wilf's "generatingfunctionology": https://www.math.upenn.edu/~wilf/DownldGF.html. It explains, using generating functions, how the number of permutations in $mathfrakS_n$ you are looking for is asymptotically $approx frac1e^1+1/2 n!$, just like the number of derangements is $approx frac1e n!$. In general the fraction of permutations with cycles all of length $>q$ is $e^-H_q$ where $H_q = 1+1/2+1/3+...+1/q$.
answered Sep 27 at 18:21
Sam HopkinsSam Hopkins
9,8771 gold badge35 silver badges77 bronze badges
$endgroup$
add a comment
|
$begingroup$
Check out "Example 2. Permutations with no small cycles" on pg. 176 of H. Wilf's "generatingfunctionology": https://www.math.upenn.edu/~wilf/DownldGF.html. It explains, using generating functions, how the number of permutations in $mathfrakS_n$ you are looking for is asymptotically $approx frac1e^1+1/2 n!$, just like the number of derangements is $approx frac1e n!$. In general the fraction of permutations with cycles all of length $>q$ is $e^-H_q$ where $H_q = 1+1/2+1/3+...+1/q$.
answered Sep 27 at 18:21
Sam HopkinsSam Hopkins
9,8771 gold badge35 silver badges77 bronze badges
$endgroup$
add a comment
|
$begingroup$
Check out "Example 2. Permutations with no small cycles" on pg. 176 of H. Wilf's "generatingfunctionology": https://www.math.upenn.edu/~wilf/DownldGF.html. It explains, using generating functions, how the number of permutations in $mathfrakS_n$ you are looking for is asymptotically $approx frac1e^1+1/2 n!$, just like the number of derangements is $approx frac1e n!$. In general the fraction of permutations with cycles all of length $>q$ is $e^-H_q$ where $H_q = 1+1/2+1/3+...+1/q$.
answered Sep 27 at 18:21
Sam HopkinsSam Hopkins
9,8771 gold badge35 silver badges77 bronze badges
$endgroup$
Check out "Example 2. Permutations with no small cycles" on pg. 176 of H. Wilf's "generatingfunctionology": https://www.math.upenn.edu/~wilf/DownldGF.html. It explains, using generating functions, how the number of permutations in $mathfrakS_n$ you are looking for is asymptotically $approx frac1e^1+1/2 n!$, just like the number of derangements is $approx frac1e n!$. In general the fraction of permutations with cycles all of length $>q$ is $e^-H_q$ where $H_q = 1+1/2+1/3+...+1/q$.
answered Sep 27 at 18:21
Sam HopkinsSam Hopkins
9,8771 gold badge35 silver badges77 bronze badges
edited Sep 27 at 18:27
answered Sep 27 at 18:21
Sam HopkinsSam Hopkins
9,8771 gold badge35 silver badges77 bronze badges
answered Sep 27 at 18:21
Sam HopkinsSam Hopkins
9,8771 gold badge35 silver badges77 bronze badges
answered Sep 27 at 18:21
Sam HopkinsSam Hopkins
9,8771 gold badge35 silver badges77 bronze badges
9,8771 gold badge35 silver badges77 bronze badges
add a comment
|
add a comment
|
Thanks for contributing an answer to MathOverflow!
- 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%2fmathoverflow.net%2fquestions%2f342613%2fenumerating-all-permutations-that-are-square-roots-of-derangements%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
1
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
Sep 27 at 17:43
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
Sep 27 at 17:49
6
$begingroup$
It is a classic result (attributed to Touchard?) that the generating function for the cycle index polynomials of symmetric groups is $sum_n geq 0 fracx^nn! sum_sigma in mathfrakS_n t_1^c_1(sigma)t_2^c_2(sigma)cdots = e^t_1 fracx1 + t_2fracx^22 + t_3fracx^33 + cdots$, where $c_k(sigma)$ is the number of cycles of $sigma$ of length $k$. Specializing $t_1=t_2=0$ and $t_3=t_4=cdots=1$ gives the generating function for the permutations you want to count. This should easily allow you to enumerate them.
$endgroup$
– Sam Hopkins
Sep 27 at 17:52
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
Sep 27 at 18:00
$begingroup$
The cycle index polynomials that Sam mentions are also discussed in Stanley's Enumerative Combinatorics, v2, Example 5.2.10, which goes on to consider "$r$th roots" of the identity permutation.
$endgroup$
– Brian Hopkins
Sep 27 at 18:23