Number of Elements in a Conjugacy Class of $S_N$ (Derivation)
$begingroup$
Consider the conjugacy classes of the symmetric group $S_N$. Each conjugacy class consists of permutations that have the same cycle structure. We see that the number of possible cycle structures is given by the number of ways of partitioning N.
For some permutation on N elements made up of $P_j$ $j$-cycles, it is trivial to see that:
$$
N = sum_j j P_j
$$
Given some cycle structure, how can one calculate the number of elements, n, in the class pertaining to said structure?
Pierre Ramond's "Group Theory: A Physicist's Survey" gives this as:
$$
n = frac{N!}{prod_{j=1}^N j^{P_j} P_j!}
$$
Is this formula found by considering a binomial coefficient? I would very much appreciate it if someone could explain to me each term in this equation, specifically the denominator.
With Thanks, Sean.
group-theory permutations binomial-coefficients symmetric-groups
asked Apr 19 '16 at 0:09
VielbeinVielbein
608
$endgroup$
add a comment |
$begingroup$
Consider the conjugacy classes of the symmetric group $S_N$. Each conjugacy class consists of permutations that have the same cycle structure. We see that the number of possible cycle structures is given by the number of ways of partitioning N.
For some permutation on N elements made up of $P_j$ $j$-cycles, it is trivial to see that:
$$
N = sum_j j P_j
$$
Given some cycle structure, how can one calculate the number of elements, n, in the class pertaining to said structure?
Pierre Ramond's "Group Theory: A Physicist's Survey" gives this as:
$$
n = frac{N!}{prod_{j=1}^N j^{P_j} P_j!}
$$
Is this formula found by considering a binomial coefficient? I would very much appreciate it if someone could explain to me each term in this equation, specifically the denominator.
With Thanks, Sean.
group-theory permutations binomial-coefficients symmetric-groups
asked Apr 19 '16 at 0:09
VielbeinVielbein
608
$endgroup$
add a comment |
$begingroup$
Consider the conjugacy classes of the symmetric group $S_N$. Each conjugacy class consists of permutations that have the same cycle structure. We see that the number of possible cycle structures is given by the number of ways of partitioning N.
For some permutation on N elements made up of $P_j$ $j$-cycles, it is trivial to see that:
$$
N = sum_j j P_j
$$
Given some cycle structure, how can one calculate the number of elements, n, in the class pertaining to said structure?
Pierre Ramond's "Group Theory: A Physicist's Survey" gives this as:
$$
n = frac{N!}{prod_{j=1}^N j^{P_j} P_j!}
$$
Is this formula found by considering a binomial coefficient? I would very much appreciate it if someone could explain to me each term in this equation, specifically the denominator.
With Thanks, Sean.
group-theory permutations binomial-coefficients symmetric-groups
asked Apr 19 '16 at 0:09
VielbeinVielbein
608
$endgroup$
Consider the conjugacy classes of the symmetric group $S_N$. Each conjugacy class consists of permutations that have the same cycle structure. We see that the number of possible cycle structures is given by the number of ways of partitioning N.
For some permutation on N elements made up of $P_j$ $j$-cycles, it is trivial to see that:
$$
N = sum_j j P_j
$$
Given some cycle structure, how can one calculate the number of elements, n, in the class pertaining to said structure?
Pierre Ramond's "Group Theory: A Physicist's Survey" gives this as:
$$
n = frac{N!}{prod_{j=1}^N j^{P_j} P_j!}
$$
Is this formula found by considering a binomial coefficient? I would very much appreciate it if someone could explain to me each term in this equation, specifically the denominator.
With Thanks, Sean.
group-theory permutations binomial-coefficients symmetric-groups
group-theory permutations binomial-coefficients symmetric-groups
asked Apr 19 '16 at 0:09
VielbeinVielbein
608
asked Apr 19 '16 at 0:09
VielbeinVielbein
608
asked Apr 19 '16 at 0:09
VielbeinVielbein
608
asked Apr 19 '16 at 0:09
VielbeinVielbein
608
asked Apr 19 '16 at 0:09
VielbeinVielbein
608
608
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are at least two possible proofs, one of them by enumeration and
another one using the exponential formula.
By enumeration, first choose the elements to go on each cycle
(multinomial coefficient):
$$frac{N!}{prod_j (j!)^{P_j}}$$
Each of these elements generates $j!/j$ cycles (in placing labels on a
directed cycle all orbits under the action of the cyclic group have
the same size which is $j$):
$$prod_j frac{(j!)^{P_j}}{j^{P_j}}$$
Permutations of the size $j$ cycles are not distinguished:
$$prod_j frac{1}{P_j!}.$$
This yields the answer
$$frac{N!}{prod_j (j!)^{P_j}}
prod_j frac{(j!)^{P_j}}{j^{P_j}}
prod_j frac{1}{P_j!}
= frac{N!}{prod_j j^{P_j} P_j!}.$$
The second proof uses the exponential formula (OGF of the cycle index
of the symmetric group)
$$Z(S_N) = [z^N]
expleft(a_1 z + a_2 frac{z^2}{2} + a_3 frac{z^3}{3} + cdotsright).$$
Extracting the coefficient of $[z^N a_1^{P_1} a_2^{P_2} timescdots]$
in $N! Z(S_N)$ we get
$$N! [z^N] [prod_j a_j^{P_j}] prod_j expleft(a_jfrac{z^j}{j}right)
= N! [z^N] prod_j frac{z^{j P_j}}{j^{P_j} P_j!}
\ = N! [z^N] z^{sum_j jP_j} prod_j frac{1}{j^{P_j} P_j!}
= N! prod_{j} frac{1}{j^{P_j} P_j!},$$
the same as in the first version. (Here we take $P_j = 0$ for a cycle
size that is absent.)
Remark. The reason for treating the OGF like an EGF is that we
have the labeled species
$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}textsc{SET}(
mathcal{A_1}textsc{CYC}_{=1}(mathcal{Z})
+ mathcal{A_2}textsc{CYC}_{=2}(mathcal{Z})
+ mathcal{A_3}textsc{CYC}_{=3}(mathcal{Z})
+ cdots)$$
and hence we are extracting from an EGF.
answered Apr 19 '16 at 0:35
Marko RiedelMarko Riedel
39.7k339108
$endgroup$
$begingroup$
Could you explain the 2nd equation to me please, I'm not entirely sure where it comes from.
$endgroup$
– Vielbein
Apr 19 '16 at 1:12
1
$begingroup$
Given that you have $j$ distinct labels and want to build a directed cycle you can distribute these into the slots on the cycle in $j!$ ways. However cycles that can be obtained from one another by a rotation (cyclic group) are the same and should count as one. The orbits under this action all have the same size and contain $j$ assignments. Therefore, divide $j!$ by $j$ to get the answer.
$endgroup$
– Marko Riedel
Apr 19 '16 at 1:19
$begingroup$
Makes sense, thanks!
$endgroup$
– Vielbein
Apr 19 '16 at 1:31
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%2f1748851%2fnumber-of-elements-in-a-conjugacy-class-of-s-n-derivation%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$
There are at least two possible proofs, one of them by enumeration and
another one using the exponential formula.
By enumeration, first choose the elements to go on each cycle
(multinomial coefficient):
$$frac{N!}{prod_j (j!)^{P_j}}$$
Each of these elements generates $j!/j$ cycles (in placing labels on a
directed cycle all orbits under the action of the cyclic group have
the same size which is $j$):
$$prod_j frac{(j!)^{P_j}}{j^{P_j}}$$
Permutations of the size $j$ cycles are not distinguished:
$$prod_j frac{1}{P_j!}.$$
This yields the answer
$$frac{N!}{prod_j (j!)^{P_j}}
prod_j frac{(j!)^{P_j}}{j^{P_j}}
prod_j frac{1}{P_j!}
= frac{N!}{prod_j j^{P_j} P_j!}.$$
The second proof uses the exponential formula (OGF of the cycle index
of the symmetric group)
$$Z(S_N) = [z^N]
expleft(a_1 z + a_2 frac{z^2}{2} + a_3 frac{z^3}{3} + cdotsright).$$
Extracting the coefficient of $[z^N a_1^{P_1} a_2^{P_2} timescdots]$
in $N! Z(S_N)$ we get
$$N! [z^N] [prod_j a_j^{P_j}] prod_j expleft(a_jfrac{z^j}{j}right)
= N! [z^N] prod_j frac{z^{j P_j}}{j^{P_j} P_j!}
\ = N! [z^N] z^{sum_j jP_j} prod_j frac{1}{j^{P_j} P_j!}
= N! prod_{j} frac{1}{j^{P_j} P_j!},$$
the same as in the first version. (Here we take $P_j = 0$ for a cycle
size that is absent.)
Remark. The reason for treating the OGF like an EGF is that we
have the labeled species
$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}textsc{SET}(
mathcal{A_1}textsc{CYC}_{=1}(mathcal{Z})
+ mathcal{A_2}textsc{CYC}_{=2}(mathcal{Z})
+ mathcal{A_3}textsc{CYC}_{=3}(mathcal{Z})
+ cdots)$$
and hence we are extracting from an EGF.
answered Apr 19 '16 at 0:35
Marko RiedelMarko Riedel
39.7k339108
$endgroup$
$begingroup$
Could you explain the 2nd equation to me please, I'm not entirely sure where it comes from.
$endgroup$
– Vielbein
Apr 19 '16 at 1:12
1
$begingroup$
Given that you have $j$ distinct labels and want to build a directed cycle you can distribute these into the slots on the cycle in $j!$ ways. However cycles that can be obtained from one another by a rotation (cyclic group) are the same and should count as one. The orbits under this action all have the same size and contain $j$ assignments. Therefore, divide $j!$ by $j$ to get the answer.
$endgroup$
– Marko Riedel
Apr 19 '16 at 1:19
$begingroup$
Makes sense, thanks!
$endgroup$
– Vielbein
Apr 19 '16 at 1:31
add a comment |
$begingroup$
There are at least two possible proofs, one of them by enumeration and
another one using the exponential formula.
By enumeration, first choose the elements to go on each cycle
(multinomial coefficient):
$$frac{N!}{prod_j (j!)^{P_j}}$$
Each of these elements generates $j!/j$ cycles (in placing labels on a
directed cycle all orbits under the action of the cyclic group have
the same size which is $j$):
$$prod_j frac{(j!)^{P_j}}{j^{P_j}}$$
Permutations of the size $j$ cycles are not distinguished:
$$prod_j frac{1}{P_j!}.$$
This yields the answer
$$frac{N!}{prod_j (j!)^{P_j}}
prod_j frac{(j!)^{P_j}}{j^{P_j}}
prod_j frac{1}{P_j!}
= frac{N!}{prod_j j^{P_j} P_j!}.$$
The second proof uses the exponential formula (OGF of the cycle index
of the symmetric group)
$$Z(S_N) = [z^N]
expleft(a_1 z + a_2 frac{z^2}{2} + a_3 frac{z^3}{3} + cdotsright).$$
Extracting the coefficient of $[z^N a_1^{P_1} a_2^{P_2} timescdots]$
in $N! Z(S_N)$ we get
$$N! [z^N] [prod_j a_j^{P_j}] prod_j expleft(a_jfrac{z^j}{j}right)
= N! [z^N] prod_j frac{z^{j P_j}}{j^{P_j} P_j!}
\ = N! [z^N] z^{sum_j jP_j} prod_j frac{1}{j^{P_j} P_j!}
= N! prod_{j} frac{1}{j^{P_j} P_j!},$$
the same as in the first version. (Here we take $P_j = 0$ for a cycle
size that is absent.)
Remark. The reason for treating the OGF like an EGF is that we
have the labeled species
$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}textsc{SET}(
mathcal{A_1}textsc{CYC}_{=1}(mathcal{Z})
+ mathcal{A_2}textsc{CYC}_{=2}(mathcal{Z})
+ mathcal{A_3}textsc{CYC}_{=3}(mathcal{Z})
+ cdots)$$
and hence we are extracting from an EGF.
answered Apr 19 '16 at 0:35
Marko RiedelMarko Riedel
39.7k339108
$endgroup$
$begingroup$
Could you explain the 2nd equation to me please, I'm not entirely sure where it comes from.
$endgroup$
– Vielbein
Apr 19 '16 at 1:12
1
$begingroup$
Given that you have $j$ distinct labels and want to build a directed cycle you can distribute these into the slots on the cycle in $j!$ ways. However cycles that can be obtained from one another by a rotation (cyclic group) are the same and should count as one. The orbits under this action all have the same size and contain $j$ assignments. Therefore, divide $j!$ by $j$ to get the answer.
$endgroup$
– Marko Riedel
Apr 19 '16 at 1:19
$begingroup$
Makes sense, thanks!
$endgroup$
– Vielbein
Apr 19 '16 at 1:31
add a comment |
$begingroup$
There are at least two possible proofs, one of them by enumeration and
another one using the exponential formula.
By enumeration, first choose the elements to go on each cycle
(multinomial coefficient):
$$frac{N!}{prod_j (j!)^{P_j}}$$
Each of these elements generates $j!/j$ cycles (in placing labels on a
directed cycle all orbits under the action of the cyclic group have
the same size which is $j$):
$$prod_j frac{(j!)^{P_j}}{j^{P_j}}$$
Permutations of the size $j$ cycles are not distinguished:
$$prod_j frac{1}{P_j!}.$$
This yields the answer
$$frac{N!}{prod_j (j!)^{P_j}}
prod_j frac{(j!)^{P_j}}{j^{P_j}}
prod_j frac{1}{P_j!}
= frac{N!}{prod_j j^{P_j} P_j!}.$$
The second proof uses the exponential formula (OGF of the cycle index
of the symmetric group)
$$Z(S_N) = [z^N]
expleft(a_1 z + a_2 frac{z^2}{2} + a_3 frac{z^3}{3} + cdotsright).$$
Extracting the coefficient of $[z^N a_1^{P_1} a_2^{P_2} timescdots]$
in $N! Z(S_N)$ we get
$$N! [z^N] [prod_j a_j^{P_j}] prod_j expleft(a_jfrac{z^j}{j}right)
= N! [z^N] prod_j frac{z^{j P_j}}{j^{P_j} P_j!}
\ = N! [z^N] z^{sum_j jP_j} prod_j frac{1}{j^{P_j} P_j!}
= N! prod_{j} frac{1}{j^{P_j} P_j!},$$
the same as in the first version. (Here we take $P_j = 0$ for a cycle
size that is absent.)
Remark. The reason for treating the OGF like an EGF is that we
have the labeled species
$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}textsc{SET}(
mathcal{A_1}textsc{CYC}_{=1}(mathcal{Z})
+ mathcal{A_2}textsc{CYC}_{=2}(mathcal{Z})
+ mathcal{A_3}textsc{CYC}_{=3}(mathcal{Z})
+ cdots)$$
and hence we are extracting from an EGF.
answered Apr 19 '16 at 0:35
Marko RiedelMarko Riedel
39.7k339108
$endgroup$
There are at least two possible proofs, one of them by enumeration and
another one using the exponential formula.
By enumeration, first choose the elements to go on each cycle
(multinomial coefficient):
$$frac{N!}{prod_j (j!)^{P_j}}$$
Each of these elements generates $j!/j$ cycles (in placing labels on a
directed cycle all orbits under the action of the cyclic group have
the same size which is $j$):
$$prod_j frac{(j!)^{P_j}}{j^{P_j}}$$
Permutations of the size $j$ cycles are not distinguished:
$$prod_j frac{1}{P_j!}.$$
This yields the answer
$$frac{N!}{prod_j (j!)^{P_j}}
prod_j frac{(j!)^{P_j}}{j^{P_j}}
prod_j frac{1}{P_j!}
= frac{N!}{prod_j j^{P_j} P_j!}.$$
The second proof uses the exponential formula (OGF of the cycle index
of the symmetric group)
$$Z(S_N) = [z^N]
expleft(a_1 z + a_2 frac{z^2}{2} + a_3 frac{z^3}{3} + cdotsright).$$
Extracting the coefficient of $[z^N a_1^{P_1} a_2^{P_2} timescdots]$
in $N! Z(S_N)$ we get
$$N! [z^N] [prod_j a_j^{P_j}] prod_j expleft(a_jfrac{z^j}{j}right)
= N! [z^N] prod_j frac{z^{j P_j}}{j^{P_j} P_j!}
\ = N! [z^N] z^{sum_j jP_j} prod_j frac{1}{j^{P_j} P_j!}
= N! prod_{j} frac{1}{j^{P_j} P_j!},$$
the same as in the first version. (Here we take $P_j = 0$ for a cycle
size that is absent.)
Remark. The reason for treating the OGF like an EGF is that we
have the labeled species
$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}textsc{SET}(
mathcal{A_1}textsc{CYC}_{=1}(mathcal{Z})
+ mathcal{A_2}textsc{CYC}_{=2}(mathcal{Z})
+ mathcal{A_3}textsc{CYC}_{=3}(mathcal{Z})
+ cdots)$$
and hence we are extracting from an EGF.
answered Apr 19 '16 at 0:35
Marko RiedelMarko Riedel
39.7k339108
edited Dec 19 '18 at 13:26
answered Apr 19 '16 at 0:35
Marko RiedelMarko Riedel
39.7k339108
answered Apr 19 '16 at 0:35
Marko RiedelMarko Riedel
39.7k339108
answered Apr 19 '16 at 0:35
Marko RiedelMarko Riedel
39.7k339108
39.7k339108
$begingroup$
Could you explain the 2nd equation to me please, I'm not entirely sure where it comes from.
$endgroup$
– Vielbein
Apr 19 '16 at 1:12
1
$begingroup$
Given that you have $j$ distinct labels and want to build a directed cycle you can distribute these into the slots on the cycle in $j!$ ways. However cycles that can be obtained from one another by a rotation (cyclic group) are the same and should count as one. The orbits under this action all have the same size and contain $j$ assignments. Therefore, divide $j!$ by $j$ to get the answer.
$endgroup$
– Marko Riedel
Apr 19 '16 at 1:19
$begingroup$
Makes sense, thanks!
$endgroup$
– Vielbein
Apr 19 '16 at 1:31
add a comment |
$begingroup$
Could you explain the 2nd equation to me please, I'm not entirely sure where it comes from.
$endgroup$
– Vielbein
Apr 19 '16 at 1:12
1
$begingroup$
Given that you have $j$ distinct labels and want to build a directed cycle you can distribute these into the slots on the cycle in $j!$ ways. However cycles that can be obtained from one another by a rotation (cyclic group) are the same and should count as one. The orbits under this action all have the same size and contain $j$ assignments. Therefore, divide $j!$ by $j$ to get the answer.
$endgroup$
– Marko Riedel
Apr 19 '16 at 1:19
$begingroup$
Makes sense, thanks!
$endgroup$
– Vielbein
Apr 19 '16 at 1:31
$begingroup$
Could you explain the 2nd equation to me please, I'm not entirely sure where it comes from.
$endgroup$
– Vielbein
Apr 19 '16 at 1:12
$begingroup$
Could you explain the 2nd equation to me please, I'm not entirely sure where it comes from.
$endgroup$
– Vielbein
Apr 19 '16 at 1:12
1
1
$begingroup$
Given that you have $j$ distinct labels and want to build a directed cycle you can distribute these into the slots on the cycle in $j!$ ways. However cycles that can be obtained from one another by a rotation (cyclic group) are the same and should count as one. The orbits under this action all have the same size and contain $j$ assignments. Therefore, divide $j!$ by $j$ to get the answer.
$endgroup$
– Marko Riedel
Apr 19 '16 at 1:19
$begingroup$
Given that you have $j$ distinct labels and want to build a directed cycle you can distribute these into the slots on the cycle in $j!$ ways. However cycles that can be obtained from one another by a rotation (cyclic group) are the same and should count as one. The orbits under this action all have the same size and contain $j$ assignments. Therefore, divide $j!$ by $j$ to get the answer.
$endgroup$
– Marko Riedel
Apr 19 '16 at 1:19
$begingroup$
Makes sense, thanks!
$endgroup$
– Vielbein
Apr 19 '16 at 1:31
$begingroup$
Makes sense, thanks!
$endgroup$
– Vielbein
Apr 19 '16 at 1:31
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%2f1748851%2fnumber-of-elements-in-a-conjugacy-class-of-s-n-derivation%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
