The symmetric group on $n$ elements, $S_n$, can act on itself by conjugation. The orbits of this action are the conjugacy classes corresponding to integer partitions of $n$. If $S_n$ acts on some particular $\sigma \in S_n$ the elements that fix $\sigma$ are the centraliser - $C(\sigma)$.

By (not) Burnside's Lemma:

$$ t_n = \frac{1}{ \lvert S_n \rvert} \sum_{\sigma \in S_n} \lvert C(\sigma) \rvert $$ where $t_n$ is the number of conjugacy classes of $S_n$.

Let $\sigma \in S_n$ be some permutation written in disjoint cycle notation with $a_j$ cycles of length $j$ for $j = 1,2,3,\dots n$ . Then the order of the centraliser is: $$ \lvert C(\sigma) \rvert = \prod_j j^{a_j} a_j! $$ For example the permutation $\sigma = (12)(345)(67)$ has 2 cycles of length 2 and one cycle of length 3 so $C(\sigma) = (2^2. 2!). (3^1. 1!)$.

QUESTION: Is there a straightforward way to calculate $$X_n = \sum_{\sigma \in S_n} \left(\prod_{j_{\sigma}} a_{j_{\sigma}}!\right), $$ where permutation $\sigma$ consists of $a_{j_{\sigma}}$ cycles of length $j_{\sigma}$?

I have tried (and failed) to find a solution using Burnside's Lemma.

  • $\begingroup$ where did you find this? $\endgroup$
    – Asinomás
    Jun 5, 2014 at 4:22
  • $\begingroup$ This brings to mind math.stackexchange.com/questions/402862/… and a somewhat related question: if we look at the number of ways we can combine conjugacy class sizes to obtain divisors of n!, we find quite large counts (ME402862 only looked at n!/2); is this a 'special' property of those conjugacy class sizes, or does this happen for many k_i summing to n! (like the first Stirling numbers or other ways to partition n!)? $\endgroup$
    – Wouter M.
    Jun 5, 2014 at 21:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.