Can we use Burnside's lemma to count partitions of an integer?

Question

I am currently learning group theory and find that Burnside Lemma can be used to calculate partition number, although not that efficiently.

Suppose we want to distribute $n$ different balls into $n$ different boxes. Each way of doing this corresponds to a function from $\{1,2,...,n\}$ to $\{1,2,...,n\}$. Let $X$ consist of all these functions. But the partition number is the number of ways when the balls and the boxes are all identical. To achieve this, we use Burnside’s lemma. Let $S_n \times S_n$ act on $X$ by $\displaystyle{ \left( a , b \right) f = a \circ f \circ b }$. Then each orbit is a partition.

For example, in the case when $n=2$, $\displaystyle{ \mid X |= 4 }$ and $\displaystyle{ \mid S |= 4 }$. The identity in $\displaystyle{ S }$ has $4$ fixed points. $\displaystyle{ \left( \left( 1 \ 2 \right) , \left( 1 \ 2 \right) \right) }$ has 2 fixed points. $\displaystyle{ \left( 1 , \left( 1 \ 2 \right) \right) }$ has 2 but $\displaystyle{ \left( \left( 1 \ 2 \right) , 1 \right) }$ has $0$. Thus the number of partitions is $\displaystyle{ \frac{ 4 + 2 + 2 }{ 4 } = 2 }$.

My question is whether there exists a more efficient and general method than enumerating all elements in $S_n \times S_n$ to find their fixed points. For example, can we reduce the enumeration to only elements in $S_n$? Are there any related results?

Answer 1

Here is a general fact:

If a group $G$ acts on a set $X$, and $a,b \in G$ are conjugate elements, then they have the same number of fixed points. In particular, if $a = g^{-1}bg$, then $x \mapsto g \cdot x$ defines a bijection from the fixed-point set of $a$ to the fixed-point set of $b$.

So, instead of enumerating all elements of $G$ when you run a Burnside argument, you only need to enumerate all conjugacy classes of $G$ (and multiply each fixed-point count by the size of the respective conjugacy class).

With that said: the conjugacy classes of $S_n$ are in canonical bijection with unlabeled partitions of $n$, so this doesn't help much for your problem :)

Answer 2

This is a nice idea. One way to do something similar with just one symmetric group instead of a product of two would be to count the equivalence classes of compositions of $n$ under permutations of the summands. The added benefit is that you get the count of partitions already disaggregated according to the number of parts.

Of course, the point made in diracdeltafunk’s answer applies here, too: To do this efficiently, you’d use the conjugacy classes of $S_n$, which are labeled by their cycle type, which is essentially a partition of $n$.