Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $n$ is a natural number and $\lambda$ is an unordered integer partition of $n$ such that $\lambda$ has $a_{\lambda,j}$ parts of size $j$ for each $j$... Let $c_\lambda$ be the conjugacy class in the symmetric group of degree $n$ comprising the elements whose cycle type is $\lambda$... Then: $$ \! |c_\lambda| = \frac{n!}{\prod_j (j)^{a_{\lambda,j}}(a_{\lambda,j}!)} $$ (see here for more information: Conjugacy class size formula in symmetric group)

Let $\Lambda$ be the set of all partitions $\lambda$ and $M\subset\Lambda $. For $n\ge5$ there seem to be more than one solution $M$ for the following: $$ \sum_{\mu\in M} |c_\mu|=\frac{n!}2 \tag{1} $$

  • There is at least one solution, since the splitting into odd and even permutations divides the set of all permutations properly.

  • For $n=5$ the even/odd splitting looks like $$ \begin{eqnarray} |c_{(1,1,1,1,1)}|+|c_{(3,1,1)}|+|c_{(2,2,1)}|+|c_{(5)}|&=&1+20+15+24\\ |c_{(2,1,1,1)}|+|c_{(4,1)}|+|c_{(3,2)}|&=&10+30+20, \end{eqnarray} $$ but there are at least $3$ more solutions:

    1. Since $|c_{3,2}|=\frac{5!}{(3^1\cdot 1!)(2^1\cdot 1!)}=|c_{3,1,1}|=\frac{5!}{(3^1\cdot 1!)(1^2\dot 2!)}$ you can interchange the odd conjugacy class of the partition $3+2$ with the even one for the partition $3+1+1$.

    2. and 3. $|c_{(1,1,1,1,1)}|+|c_{(2,2,1)}|+|c_{(5)}|=1+15+24=40$, so we may again add $|c_{(3,2)}|$ or $|c_{(3,1,1)}|$

My question:

Is it possible to give an asymptotic? How many solutions $M$ exist for $(1)$ in general?

share|cite|improve this question

Ok, it was easier than I thought to find a concise way to calculate the number of solutions:

We've got to calculate $$ \prod_{\lambda\in\Lambda} \left(1+x^{|c_\lambda|}\right) $$

and then find the coefficient of $\displaystyle x^\frac{n!}{2}$. Some results:

  • $n=5$ (supported by W|A):

$$(1+x)(1+x^{10})(1+x^{20})^2 (1+x^{15})(1+x^{30})(1+x^{24})=x^{120}+x^{119}+x^{110}+x^{109}+x^{105}+x^{104}+2 x^{100}+2 x^{99}+x^{96}+2 x^{95}+x^{94}+3 x^{90}+3 x^{89}+x^{86}+3 x^{85}+2 x^{84}+x^{81}+3 x^{80}+2 x^{79}+2 x^{76}+5 x^{75}+3 x^{74}+x^{71}+4 x^{70}+3 x^{69}+3 x^{66}+5 x^{65}+2 x^{64}+2 x^{61}+\color{red}{4 x^{60}}+2 x^{59}+2 x^{56}+5 x^{55}+3 x^{54}+3 x^{51}+4 x^{50}+x^{49}+3 x^{46}+5 x^{45}+2 x^{44}+2 x^{41}+3 x^{40}+x^{39}+2 x^{36}+3 x^{35}+x^{34}+3 x^{31}+3 x^{30}+x^{26}+2 x^{25}+x^{24}+2 x^{21}+2 x^{20}+x^{16}+x^{15}+x^{11}+x^{10}+x+1$$

  • $n=6$: $$ (1+x^{1})(1+x^{15})(1+x^{40})^2(1+x^{90})^2(1+x^{45})(1+x^{144})(1+x^{120})^2(1+x^{15})\\=\dots+ \color{red}{12 x^{360}}+\dots $$

  • $n=7$: $(1+x) \dots (1+x^{840}) = \dots+ \color{red}{58 x^{2520}}+\dots$

  • $n=8$: $(1+x) \dots (1+x^{5760}) = \dots+ \color{red}{1016 x^{20160}}+\dots$

So summarizing this we get: $0,2,2,2,4,12,58,1016$ (thanks to Jack) for the first eight symmetric groups. The question about the asymptotics remains open...

share|cite|improve this answer
Some of your earlier terms are wrong, I think. 0, 2, 2, 2, 4, 12, 58, 1016, 53940, ... If you require the identity, then you get 0, 1, 1, 1, 2, 6, 29, 508, 26970, ... (the relationship is kind of neat). – Jack Schmidt Jun 5 '13 at 16:57
next term is 12653364 (or 6326682 if you require the identity; eerie). The consecutive ratios are ∞, 1, 1, 2, 3, 4.8, 17.5, 53.1, 234.6, so that looks super-exponential to me. At any rate, the lesson that numerical coincidences might be helpful in A5, but not in general is pretty clear. :-) – Jack Schmidt Jun 5 '13 at 19:01
@jack, I see that my approach isn't as good as I thought. Gotta think about that: Isn't it the same problem as here: Making Change for a Dollar (and other number partitioning problems)? Ok I didn't use the reciprocal. Do I have to, to solve this problem? But I don't get what you mean by requiring identity... – draks ... Jun 5 '13 at 19:43
Requiring identity: You claimed that there was only one way to find a union of conjugacy classes of size 1 in the symmetric group S2, but obviously there are two ways {()} and {(1,2)} both work. I tried to guess why your count was wrong. I guessed that it was because you were trying to write the alternating group as a union of conjugacy classes, and obviously every subgroup has to the identity, so maybe you wanted that conjugacy class always used. Note that $(1+x)(1+x) = 1 +\color{red}{2x^1} + x^2$, so the polynomial method gives 2 as well. – Jack Schmidt Jun 5 '13 at 20:01
"Super exponential" in the complexity class sense. Faster than exponential, $f:\mathbb{N} \to \mathbb{R}$ is super exponential if for every $C>0, D>1$ there is some $N$ such that $f(n) > C \cdot D^n$ for all $n \geq N$. Note that $(C\cdot D^{n+1})/(C\cdot D^n) = D$, so the consecutive ratios give an estimate for $D$ (namely, infinity). – Jack Schmidt Sep 11 '13 at 14:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.