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?


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...

  • $\begingroup$ 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). $\endgroup$ Jun 5 '13 at 16:57
  • 1
    $\begingroup$ 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. :-) $\endgroup$ Jun 5 '13 at 19:01
  • $\begingroup$ @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... $\endgroup$
    – draks ...
    Jun 5 '13 at 19:43
  • $\begingroup$ 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. $\endgroup$ Jun 5 '13 at 20:01
  • 1
    $\begingroup$ "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). $\endgroup$ Sep 11 '13 at 14:40

Your Answer

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

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