Consider a set $X$ of $9$ dots arranged in a $3 \times 3$ grid. Let $H$ be the group generated by the permutations on the rows of $X$ and by the permutations on the columns of $X$.
I am asked:
- How many elements are in $H$?
- What cycle types appear in $H$?
- How many elements in $H$ belong to each cycle type?
- If the $9$ elements in $X$ are colored $3$ each red, white and blue, how many ways can we color $X$, where two colorings are the same if we can move from one coloring to another through operations in $H$?
I have only a few ideas:
-
The group $H$ will be something like $S_3 \times S_3$, because we can permute rows and columns, so that should give me 36 elements in $H$.
-
This clearly looks like I'm supposed to apply Burnside's Lemma. The group acting will be $H$. But I'm not too sure about the rest. I need to count the number of fixed points for every element in $H$.
Thanks.
Best Answer
Welcome to MSE!
You're exactly right that this is a job for Burnside's Lemma. In fact, as is mentioned in the comments, steps $1$, $2$, and $3$ are more or less guiding you towards the use of Burnside's Lemma.
For $1$, you already found the right group. $H = S_3 \times S_3$ works (though you might want to justify to yourself that permuting rows then permuting columns is really the same thing as permuting columns then rows). You also correctly see that $|H| = 36$. So this is a strong start!
For $2$, it sounds like there's a lot of computation you need to do, but notice that, as far as cycle types are concerned, there's really only a few things you can do. Each element of $S_3$ is either the identity, a transposition, or a $3$-cycle. This means each element of $S_3 \times S_3$ is a product of such things. Since there's row/column symmetry as well, you can actually break this down into the following cases. Here $1$ is the identity, $\tau$ is a transposition, and $\sigma$ is a $3$-cycle:
You should convince yourself that every element of $S_3 \times S_3$ has the same cycle structure as one of these. Then you can compute the cycle structure by using, say, $\tau = (1 \ 2)$ and $\sigma = (1 \ 2 \ 3)$ as concrete examples.
For $3$, you want to try to see how many group elements fall into each of the $6$ categories above. Keep in mind the answers should sum to $36$, since that's how many total group elements there are in $H$.
Finally, for $4$, we apply Burnside's Lemma. For each of the $6$ categories above, how many fixed points are there? That is, how many colorings stay the same after you apply a permutation from that category? Here you'll again want to work with the concrete example $\tau = (1 \ 2)$ and $\sigma = (1 \ 2 \ 3)$. Remember every element in a cycle (where now we're viewing $H$ as a subgroup of $S_9$ acting on all of $X$) has to get the same color! So we expect $3^{\text{number of cycles}}$ many fixed points.
Now what does Burnside's Lemma tell us?
So the answer to your problem will be
$$\frac{1}{36} \sum_g 3^{\text{number of cycles in $g$}}$$
But the $6$ categories we identified all have the same number of cycles. And we figured out in part $3$ how many $g$ belong to each category. So we can split this sum up based on which category we're in (call them $C_1, \ldots, C_6$) and find:
$$ \frac{1}{36} \left ( \sum_{C_1} 3^{\text{number of cycles in $(1,1)$}} + \sum_{C_2} 3^{\text{number of cycles in $(1, \tau)$}} + \ldots + \sum_{C_6} 3^{\text{number of cycles in $(\sigma, \sigma)$}} \right ) $$
But we know that the number of cycles is the same in each of these sums, so we can turn our repeated addition into multiplication. We find the number of distinct colorings is
$$ \frac{1}{36} \left ( |C_1| 3^{\text{number of cycles in $(1,1)$}} + |C_2| 3^{\text{number of cycles in $(1, \tau)$}} + \ldots + |C_6| 3^{\text{number of cycles in $(\sigma, \sigma)$}} \right ) $$
where you'll know $|C_i|$ from part $3$ and "number of cycles in $-$" from playing around with the categories you found in part $2$.
As an aside, you can also get a computer algebra system like sage to do most of this heavy lifting (such as computing cycle decompositions, etc.) for you. See here for some relevant documentation.
I hope this helps ^_^