A group orbit/Burnside's lemma question 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.
 A: 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:

*

*$(1, 1)$

*$(1, \tau)$

*$(1, \sigma)$

*$(\tau, \tau)$

*$(\tau, \sigma)$

*$(\sigma, \sigma)$
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?

The number of orbits (which is what you're looking for) is the average number of fixed points

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 ^_^
A: Maybe I can help with some data.  I would not attack this problem with
pen and paper but use a CAS to assist as was suggested already. A very
similar   problem   appeared   at    MSE   at   the   following   MSE
link   where   the
symmetric group was paired with the  cyclic one instead of the another
instance of the  symmetric group.  The latter post  computes the cycle
index, which answers  your question about the number  of elements, the
cycle  types and  the number  of elements  of each  cycle type.   More
importantly,  it also  explains  the algorithm  to  compute the  cycle
index.  I  have implemented  this algorithm in  Maple for  $n\times m$
boards. We get  for the 3x3 case the following  cycle index, which you
may use to check your work:
$$Z(P_{3,3}) = 1/36\,{a_{{1}}}^{9}+1/6\,{a_{{1}}}^{3}{a_{{2}}}^{3}
+1/4\,a_{{1}}{a_{{2}}}^{4}+2/9\,{a_{{3}}}^{3}
+1/3\,a_{{3}}a_{{6}}.$$
This says  that e.g.  there  are twelve  instances of cycle  type $a_3
a_6.$ Once  we have the cycle  index we may use  the Polya Enumeration
Theorem (PET) to compute the  number of non-isomorphic colorings. This
is the  same as Burnside which  requires the colors to  be constant on
each  cycle, yielding  the  substitution  $a_d =  R^d  +  W^d +  B^d$,
corresponding to a red, a white and a blue cycle respectively. Here is
an excerpt from the substituted cycle index for a 3x3 board:
$$\cdots+6\,{B}^{3}{R}^{6}+17\,{B}^{3}{R}^{5}W+
43\,{B}^{3}{R}^{4}{W}^{2}
\\ +54\,{B}^{3}{R}^{3}{W}^{3}+43\,{B}^{3}{R}^{2}{W}^{4}
+17\,{B}^{3}R{W}^{5}+6\,{B}^{3}{W}^{6}+\cdots$$
This  means that  there are  $54$ colorings  using three  instances of
three  different  colors,  which  you  can again  use  to  check  your
work. The  Maple code  for the case  of an $n\times  m$ board  goes as
follows:

pet_cycleind_symm :=
proc(n)
option remember;
local l;
    
    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
        pot := op(1, v);

        subs1 :=
        [seq(polyvars[k]=polyvars[k]^pot,
             k=1..nops(polyvars))];

        subs2 := [v=subs(subs1, poly)];

        res := subs(subs2, res);
    od;

    res;
end;


pet_cycleind_mat :=
proc(n, m)
option remember;
local rowind, colind, cind, term_a, term_b, v_a, v_b,
    len_a, len_b, inst_a, inst_b, p;

    cind := 0;

    if n=1 then
        return pet_cycleind_symm(m);
    else
        rowind := pet_cycleind_symm(n);
    fi;

    if m=1 then
        return pet_cycleind_symm(n);
    else
        colind := pet_cycleind_symm(m);
    fi;

    for term_a in rowind do
        for term_b in colind do
            p := 1;
            for v_a in indets(term_a) do
                len_a := op(1, v_a);
                inst_a := degree(term_a, v_a);

                for v_b in indets(term_b) do
                    len_b := op(1, v_b);
                    inst_b := degree(term_b, v_b);

                    p := p*a[lcm(len_a, len_b)]
                    ^(gcd(len_a, len_b)*inst_a*inst_b);
                od;
            od;

            cind := cind +
            lcoeff(term_a)*lcoeff(term_b)*p;
        od;
    od;

    cind;
end;

colors_ABC :=
proc(n, m)
option remember;
local cind;

    cind := pet_cycleind_mat(n, m);

    expand(pet_varinto_cind(A+B+C, cind));
end;

We can  easily compute  the cycle  index for e.g.  a 4x4  board, which
gives
$$Z(P_{4,4}) = {\frac {{a_{{1}}}^{16}}{576}}
+1/48\,{a_{{1}}}^{8}{a_{{2}}}^{4}+1/36\,{a_{{1}}}^{4}{a_{{3}}}^{4}
\\ +{\frac {17\,{a_{{2}}}^{8}}{192}}+
{\frac {13\,{a_{{4}}}^{4}}{48}}+1/16\,{a_{{1}}}^{4}{a_{{2}}}^{6}
+1/6\,{a_{{1}}}^{2}{a_{{3}}}^{2}a_{{2}}a_{{6}}
\\ +1/9\,{a_{{3}}}^{5}a_{{1}}+1/12\,{a_{{2}}}^{2}{a_{{6}}}^{2}
+1/6\,a_{{4}}a_{{12}}.$$
Remark. I  just noticed  that this problem  (two instances  of the
symmetric  group)  appeared  verbatim   at  the  following  MSE  link
II.
