# Partition counting using Burnside's lemma

So I just studied Burnside's lemma and one of the exercises ask me to count the number of partitions of $9$ into $3$ parts using the permutation group $S_3$. I'm having trouble applying the lemma. I was thinking that $3$-coloring the set $\{1,\dots,9\}$ might work, then use $S_3$ somehow, but it doesn't seem to lead anywhere. How do I do this problem?

$S_3$ is acting on compositions of $9$ (partitions where the order matters). There are $28$ compositions of $9$ with $3$ parts. Namely we have

$$\begin{array}{cccc} (1,1,7), & (1,2,6), & \cdots, & (1,7,1), \\ (2,1,6), & (2,2,5), & \cdots, & (2,6,1), \\ (3,1,5), & (3,2,4), & \cdots, & (3,5,1), \\ \vdots & & & \\ (7,1,1) \end{array}$$

($7$ in the first row $+ 6$ in the second $+5$ in the third and so on.)

Therefore there are 28 compositions fixed by the identity permutation. Only $(3,3,3)$ is fixed by the two $3$-cycles. You can show that there are $4$ compositions fixed by each $2$-cycle. This gives

$$\frac16(1 \cdot 28 + 3 \cdot 4 + 2 \cdot 1) = 7$$

partitions of $9$ into $3$ parts.

• Thank you very much for the answer. I just figured this out on my own too, but it's great to see confirmation. I am just wondering if there is a less computational approach? – user228960 Oct 15 '17 at 21:56
• @mathstudent_101 There aren't a whole lot of "nice" formulas for numbers of integer partitions. There's a generating function, some asymptotic functions and some recurrence relations. For something this small, listing out each partition is faster than going around the matter with compositions and Burnside's lemma. That, I would say, is the simplest way to get the answer. – Trevor Gunn Oct 15 '17 at 22:01