Enumerating all permutations that are “square roots” of derangementsNon-enumerative proof that there are...
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 8 hours ago
Manfred WeisManfred Weis
4,9442 gold badges15 silver badges48 bronze badges
$endgroup$
|
show 1 more comment
$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 8 hours ago
Manfred WeisManfred Weis
4,9442 gold badges15 silver badges48 bronze badges
$endgroup$
1
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
8 hours ago
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
8 hours ago
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} frac{x^n}{n!} sum_{sigma in mathfrak{S}_n} t_1^{c_1(sigma)}t_2^{c_2(sigma)}cdots = e^{t_1 frac{x}{1} + t_2frac{x^2}{2} + t_3frac{x^3}{3} + 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
8 hours ago
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
8 hours ago
$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
7 hours ago
|
show 1 more comment
$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 8 hours ago
Manfred WeisManfred Weis
4,9442 gold badges15 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 8 hours ago
Manfred WeisManfred Weis
4,9442 gold badges15 silver badges48 bronze badges
asked 8 hours ago
Manfred WeisManfred Weis
4,9442 gold badges15 silver badges48 bronze badges
asked 8 hours ago
Manfred WeisManfred Weis
4,9442 gold badges15 silver badges48 bronze badges
asked 8 hours ago
Manfred WeisManfred Weis
4,9442 gold badges15 silver badges48 bronze badges
asked 8 hours ago
Manfred WeisManfred Weis
4,9442 gold badges15 silver badges48 bronze badges
4,9442 gold badges15 silver badges48 bronze badges
1
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
8 hours ago
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
8 hours ago
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} frac{x^n}{n!} sum_{sigma in mathfrak{S}_n} t_1^{c_1(sigma)}t_2^{c_2(sigma)}cdots = e^{t_1 frac{x}{1} + t_2frac{x^2}{2} + t_3frac{x^3}{3} + 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
8 hours ago
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
8 hours ago
$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
7 hours ago
|
show 1 more comment
1
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
8 hours ago
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
8 hours ago
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} frac{x^n}{n!} sum_{sigma in mathfrak{S}_n} t_1^{c_1(sigma)}t_2^{c_2(sigma)}cdots = e^{t_1 frac{x}{1} + t_2frac{x^2}{2} + t_3frac{x^3}{3} + 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
8 hours ago
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
8 hours ago
$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
7 hours ago
1
1
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
8 hours ago
$begingroup$
Your condition is equivalent to all cycles having length 3 or greater, right?
$endgroup$
– Sam Hopkins
8 hours ago
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
8 hours ago
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
8 hours ago
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} frac{x^n}{n!} sum_{sigma in mathfrak{S}_n} t_1^{c_1(sigma)}t_2^{c_2(sigma)}cdots = e^{t_1 frac{x}{1} + t_2frac{x^2}{2} + t_3frac{x^3}{3} + 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
8 hours ago
$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} frac{x^n}{n!} sum_{sigma in mathfrak{S}_n} t_1^{c_1(sigma)}t_2^{c_2(sigma)}cdots = e^{t_1 frac{x}{1} + t_2frac{x^2}{2} + t_3frac{x^3}{3} + 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
8 hours ago
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
8 hours ago
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
8 hours ago
$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
7 hours ago
$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
7 hours ago
|
show 1 more comment
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 $mathfrak{S}_n$ you are looking for is asymptotically $approx frac{1}{e^{1+1/2}} n!$, just like the number of derangements is $approx frac{1}{e} 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 7 hours ago
Sam HopkinsSam Hopkins
6,7221 gold badge34 silver badges69 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 $mathfrak{S}_n$ you are looking for is asymptotically $approx frac{1}{e^{1+1/2}} n!$, just like the number of derangements is $approx frac{1}{e} 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 7 hours ago
Sam HopkinsSam Hopkins
6,7221 gold badge34 silver badges69 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 $mathfrak{S}_n$ you are looking for is asymptotically $approx frac{1}{e^{1+1/2}} n!$, just like the number of derangements is $approx frac{1}{e} 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 7 hours ago
Sam HopkinsSam Hopkins
6,7221 gold badge34 silver badges69 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 $mathfrak{S}_n$ you are looking for is asymptotically $approx frac{1}{e^{1+1/2}} n!$, just like the number of derangements is $approx frac{1}{e} 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 7 hours ago
Sam HopkinsSam Hopkins
6,7221 gold badge34 silver badges69 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 $mathfrak{S}_n$ you are looking for is asymptotically $approx frac{1}{e^{1+1/2}} n!$, just like the number of derangements is $approx frac{1}{e} 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 7 hours ago
Sam HopkinsSam Hopkins
6,7221 gold badge34 silver badges69 bronze badges
edited 7 hours ago
answered 7 hours ago
Sam HopkinsSam Hopkins
6,7221 gold badge34 silver badges69 bronze badges
answered 7 hours ago
Sam HopkinsSam Hopkins
6,7221 gold badge34 silver badges69 bronze badges
answered 7 hours ago
Sam HopkinsSam Hopkins
6,7221 gold badge34 silver badges69 bronze badges
6,7221 gold badge34 silver badges69 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
8 hours ago
$begingroup$
yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements.
$endgroup$
– Manfred Weis
8 hours ago
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} frac{x^n}{n!} sum_{sigma in mathfrak{S}_n} t_1^{c_1(sigma)}t_2^{c_2(sigma)}cdots = e^{t_1 frac{x}{1} + t_2frac{x^2}{2} + t_3frac{x^3}{3} + 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
8 hours ago
$begingroup$
@SamHopkins thanks for providing that information; I guess that will solve my problem.
$endgroup$
– Manfred Weis
8 hours ago
$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
7 hours ago