Mixing
Number of permutations that are products of disjoint cycles of distinct length
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
What is the number of permutations $piin S_n$ that are products of disjoint cycles of distinct length? What is the number of permutations that are products of disjoint cycles such that no more than $k$ cycles are of any given length?
I am really interested in the asymptotics of the proportion of permutations in $S_n$ with these properties as $nto infty$. What is a good reference for this sort of statistics?
permutations permutation-groups random-permutations
asked 4 hours ago
H A Helfgott
4,42712579
add a comment |Â
up vote
4
down vote
favorite
What is the number of permutations $piin S_n$ that are products of disjoint cycles of distinct length? What is the number of permutations that are products of disjoint cycles such that no more than $k$ cycles are of any given length?
I am really interested in the asymptotics of the proportion of permutations in $S_n$ with these properties as $nto infty$. What is a good reference for this sort of statistics?
permutations permutation-groups random-permutations
asked 4 hours ago
H A Helfgott
4,42712579
Dumb question (from me): you are ignoring cycles of length one (fixed points), right? In which case, a good start on estimating the size of the complement is counting all permutations with two cycles of length two, and over counting by adding those with two cycles of length three. For back of the envelope estimates I would start with that. Gerhard "Higher Order Terms Can Wait" Paseman, 2018.11.02.
– Gerhard Paseman
2 hours ago
Actually, both versions of the question interest me - ignoring fixed points and considering them as cycles of length 1.
– H A Helfgott
1 hour ago
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
What is the number of permutations $piin S_n$ that are products of disjoint cycles of distinct length? What is the number of permutations that are products of disjoint cycles such that no more than $k$ cycles are of any given length?
I am really interested in the asymptotics of the proportion of permutations in $S_n$ with these properties as $nto infty$. What is a good reference for this sort of statistics?
permutations permutation-groups random-permutations
asked 4 hours ago
H A Helfgott
4,42712579
What is the number of permutations $piin S_n$ that are products of disjoint cycles of distinct length? What is the number of permutations that are products of disjoint cycles such that no more than $k$ cycles are of any given length?
I am really interested in the asymptotics of the proportion of permutations in $S_n$ with these properties as $nto infty$. What is a good reference for this sort of statistics?
permutations permutation-groups random-permutations
permutations permutation-groups random-permutations
asked 4 hours ago
H A Helfgott
4,42712579
asked 4 hours ago
H A Helfgott
4,42712579
asked 4 hours ago
H A Helfgott
4,42712579
asked 4 hours ago
H A Helfgott
4,42712579
asked 4 hours ago
H A Helfgott
4,42712579
4,42712579
Dumb question (from me): you are ignoring cycles of length one (fixed points), right? In which case, a good start on estimating the size of the complement is counting all permutations with two cycles of length two, and over counting by adding those with two cycles of length three. For back of the envelope estimates I would start with that. Gerhard "Higher Order Terms Can Wait" Paseman, 2018.11.02.
– Gerhard Paseman
2 hours ago
Actually, both versions of the question interest me - ignoring fixed points and considering them as cycles of length 1.
– H A Helfgott
1 hour ago
add a comment |Â
Dumb question (from me): you are ignoring cycles of length one (fixed points), right? In which case, a good start on estimating the size of the complement is counting all permutations with two cycles of length two, and over counting by adding those with two cycles of length three. For back of the envelope estimates I would start with that. Gerhard "Higher Order Terms Can Wait" Paseman, 2018.11.02.
– Gerhard Paseman
2 hours ago
Actually, both versions of the question interest me - ignoring fixed points and considering them as cycles of length 1.
– H A Helfgott
1 hour ago
Dumb question (from me): you are ignoring cycles of length one (fixed points), right? In which case, a good start on estimating the size of the complement is counting all permutations with two cycles of length two, and over counting by adding those with two cycles of length three. For back of the envelope estimates I would start with that. Gerhard "Higher Order Terms Can Wait" Paseman, 2018.11.02.
– Gerhard Paseman
2 hours ago
Dumb question (from me): you are ignoring cycles of length one (fixed points), right? In which case, a good start on estimating the size of the complement is counting all permutations with two cycles of length two, and over counting by adding those with two cycles of length three. For back of the envelope estimates I would start with that. Gerhard "Higher Order Terms Can Wait" Paseman, 2018.11.02.
– Gerhard Paseman
2 hours ago
Actually, both versions of the question interest me - ignoring fixed points and considering them as cycles of length 1.
– H A Helfgott
1 hour ago
Actually, both versions of the question interest me - ignoring fixed points and considering them as cycles of length 1.
– H A Helfgott
1 hour ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
If we denote by $c_i(sigma)$ the number of cycles of length $i$ in $sigma$, we can write the exponential generating function of permutations with cycle statistics as
$$sum_ngeq 1sum_sigmain S_nleft(fracx^nn!prod_igeq 1t_i^c_i(sigma)right)=expleft(sum_igeq 1 fract_ix^iiright) =prod_igeq 1 left(1+fract_ix^ii+fract_i^2x^2i2i^2+cdotsright)$$
From here we see that the exponential generating function of permutations with distinct cycle sizes can be obtained by removing all terms where any $t_i$ has exponent $geq 2$, and then setting all $t_i=1$. So we get
$$prod_igeq 1left(1+fracx^iiright)$$
From here the methods of A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics by P. Flajolet, E. Fusy, X. Gourdon, D. Panario, N. Pouyanne show that the coefficient of $x^n$ is asymptotically equal to
$$e^-gamma+frace^-gamman+Oleft(fraclog nn^2right)$$
which means that our desired number of permutations is asymptotically given by $$n!left(e^-gamma+frace^-gamman+Oleft(fraclog nn^2right)right).$$
Notice that in section 3 they actually provide much more refined asymptotics, in case you wanted more terms. Moreover, I believe their method should let you compute the asymptotics for permutations with cycles of the same length appearing at most $k$ times whose generating function is given by
$$prod_igeq 1left(1+fracx^ii+fracx^2i2i^2+cdots +fracx^kik!i^kright)$$
from the same considerations as above.
answered 2 hours ago
Gjergji Zaimi
60.8k4158300
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
If we denote by $c_i(sigma)$ the number of cycles of length $i$ in $sigma$, we can write the exponential generating function of permutations with cycle statistics as
$$sum_ngeq 1sum_sigmain S_nleft(fracx^nn!prod_igeq 1t_i^c_i(sigma)right)=expleft(sum_igeq 1 fract_ix^iiright) =prod_igeq 1 left(1+fract_ix^ii+fract_i^2x^2i2i^2+cdotsright)$$
From here we see that the exponential generating function of permutations with distinct cycle sizes can be obtained by removing all terms where any $t_i$ has exponent $geq 2$, and then setting all $t_i=1$. So we get
$$prod_igeq 1left(1+fracx^iiright)$$
From here the methods of A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics by P. Flajolet, E. Fusy, X. Gourdon, D. Panario, N. Pouyanne show that the coefficient of $x^n$ is asymptotically equal to
$$e^-gamma+frace^-gamman+Oleft(fraclog nn^2right)$$
which means that our desired number of permutations is asymptotically given by $$n!left(e^-gamma+frace^-gamman+Oleft(fraclog nn^2right)right).$$
Notice that in section 3 they actually provide much more refined asymptotics, in case you wanted more terms. Moreover, I believe their method should let you compute the asymptotics for permutations with cycles of the same length appearing at most $k$ times whose generating function is given by
$$prod_igeq 1left(1+fracx^ii+fracx^2i2i^2+cdots +fracx^kik!i^kright)$$
from the same considerations as above.
answered 2 hours ago
Gjergji Zaimi
60.8k4158300
add a comment |Â
up vote
5
down vote
If we denote by $c_i(sigma)$ the number of cycles of length $i$ in $sigma$, we can write the exponential generating function of permutations with cycle statistics as
$$sum_ngeq 1sum_sigmain S_nleft(fracx^nn!prod_igeq 1t_i^c_i(sigma)right)=expleft(sum_igeq 1 fract_ix^iiright) =prod_igeq 1 left(1+fract_ix^ii+fract_i^2x^2i2i^2+cdotsright)$$
From here we see that the exponential generating function of permutations with distinct cycle sizes can be obtained by removing all terms where any $t_i$ has exponent $geq 2$, and then setting all $t_i=1$. So we get
$$prod_igeq 1left(1+fracx^iiright)$$
From here the methods of A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics by P. Flajolet, E. Fusy, X. Gourdon, D. Panario, N. Pouyanne show that the coefficient of $x^n$ is asymptotically equal to
$$e^-gamma+frace^-gamman+Oleft(fraclog nn^2right)$$
which means that our desired number of permutations is asymptotically given by $$n!left(e^-gamma+frace^-gamman+Oleft(fraclog nn^2right)right).$$
Notice that in section 3 they actually provide much more refined asymptotics, in case you wanted more terms. Moreover, I believe their method should let you compute the asymptotics for permutations with cycles of the same length appearing at most $k$ times whose generating function is given by
$$prod_igeq 1left(1+fracx^ii+fracx^2i2i^2+cdots +fracx^kik!i^kright)$$
from the same considerations as above.
answered 2 hours ago
Gjergji Zaimi
60.8k4158300
add a comment |Â
up vote
5
down vote
up vote
5
down vote
If we denote by $c_i(sigma)$ the number of cycles of length $i$ in $sigma$, we can write the exponential generating function of permutations with cycle statistics as
$$sum_ngeq 1sum_sigmain S_nleft(fracx^nn!prod_igeq 1t_i^c_i(sigma)right)=expleft(sum_igeq 1 fract_ix^iiright) =prod_igeq 1 left(1+fract_ix^ii+fract_i^2x^2i2i^2+cdotsright)$$
From here we see that the exponential generating function of permutations with distinct cycle sizes can be obtained by removing all terms where any $t_i$ has exponent $geq 2$, and then setting all $t_i=1$. So we get
$$prod_igeq 1left(1+fracx^iiright)$$
From here the methods of A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics by P. Flajolet, E. Fusy, X. Gourdon, D. Panario, N. Pouyanne show that the coefficient of $x^n$ is asymptotically equal to
$$e^-gamma+frace^-gamman+Oleft(fraclog nn^2right)$$
which means that our desired number of permutations is asymptotically given by $$n!left(e^-gamma+frace^-gamman+Oleft(fraclog nn^2right)right).$$
Notice that in section 3 they actually provide much more refined asymptotics, in case you wanted more terms. Moreover, I believe their method should let you compute the asymptotics for permutations with cycles of the same length appearing at most $k$ times whose generating function is given by
$$prod_igeq 1left(1+fracx^ii+fracx^2i2i^2+cdots +fracx^kik!i^kright)$$
from the same considerations as above.
answered 2 hours ago
Gjergji Zaimi
60.8k4158300
If we denote by $c_i(sigma)$ the number of cycles of length $i$ in $sigma$, we can write the exponential generating function of permutations with cycle statistics as
$$sum_ngeq 1sum_sigmain S_nleft(fracx^nn!prod_igeq 1t_i^c_i(sigma)right)=expleft(sum_igeq 1 fract_ix^iiright) =prod_igeq 1 left(1+fract_ix^ii+fract_i^2x^2i2i^2+cdotsright)$$
From here we see that the exponential generating function of permutations with distinct cycle sizes can be obtained by removing all terms where any $t_i$ has exponent $geq 2$, and then setting all $t_i=1$. So we get
$$prod_igeq 1left(1+fracx^iiright)$$
From here the methods of A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics by P. Flajolet, E. Fusy, X. Gourdon, D. Panario, N. Pouyanne show that the coefficient of $x^n$ is asymptotically equal to
$$e^-gamma+frace^-gamman+Oleft(fraclog nn^2right)$$
which means that our desired number of permutations is asymptotically given by $$n!left(e^-gamma+frace^-gamman+Oleft(fraclog nn^2right)right).$$
Notice that in section 3 they actually provide much more refined asymptotics, in case you wanted more terms. Moreover, I believe their method should let you compute the asymptotics for permutations with cycles of the same length appearing at most $k$ times whose generating function is given by
$$prod_igeq 1left(1+fracx^ii+fracx^2i2i^2+cdots +fracx^kik!i^kright)$$
from the same considerations as above.
answered 2 hours ago
Gjergji Zaimi
60.8k4158300
answered 2 hours ago
Gjergji Zaimi
60.8k4158300
answered 2 hours ago
Gjergji Zaimi
60.8k4158300
answered 2 hours ago
Gjergji Zaimi
60.8k4158300
60.8k4158300
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f314421%2fnumber-of-permutations-that-are-products-of-disjoint-cycles-of-distinct-length%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Dumb question (from me): you are ignoring cycles of length one (fixed points), right? In which case, a good start on estimating the size of the complement is counting all permutations with two cycles of length two, and over counting by adding those with two cycles of length three. For back of the envelope estimates I would start with that. Gerhard "Higher Order Terms Can Wait" Paseman, 2018.11.02.
– Gerhard Paseman
2 hours ago
Actually, both versions of the question interest me - ignoring fixed points and considering them as cycles of length 1.
– H A Helfgott
1 hour ago