What we have here is an instance of Power Group Enumeration as
described by Harary and Palmer, Graphical Enumeration. The algorithm
is documented at the following MSE-link
I. We require the
cycle index $Z(Q_n)$ of the action on the edges of the permutations of
the two parts of the graph, possibly combined with a horizontal
reflection. This is the slot permutation group. We distribute edges
of one of $k$ colors into these slots, and the group acting on them is
the symmetric group with cycle index $Z(S_k)$. The cycle index
$Z(Q_n)$ was computed at the following MSE-link
II. We have e.g.
$$Z(Q_3) = {\frac {{a_{{1}}}^{9}}{72}}
+1/6\,{a_{{1}}}^{3}{a_{{2}}}^{3}
+1/8\,a_{{1}}{a_{{2}}}^{4}+1/4\,a_{{1}}{a_{{4}}}^{2}
+1/9\,{a_{{3}}}^{3}+1/3\,a_{{3}}a_{{6}}.$$
and
$$Z(Q_4) = {\frac {{a_{{1}}}^{16}}{1152}}
+{\frac {{a_{{1}}}^{8}{a_{{2}}}^{4}}{96}}
+{\frac {5\,{a_{{1}}}^{4}{a_{{2}}}^{6}}{96}}
+{\frac {{a_{{1}}}^{4}{a_{{3}}}^{4}}{72}}
+{\frac {17\,{a_{{2}}}^{8}}{384}}
\\ +1/12\,{a_{{1}}}^{2}a_{{2}}{a_{{3}}}^{2}a_{{6}}
+1/8\,{a_{{1}}}^{2}a_{{2}}{a_{{4}}}^{3}
+1/18\,a_{{1}}{a_{{3}}}^{5}
+1/6\,a_{{1}}a_{{3}}{a_{{6}}}^{2}
\\ +1/24\,{a_{{2}}}^{2}{a_{{6}}}^{2}
+{\frac {19\,{a_{{4}}}^{4}}{96}}
+1/12\,a_{{4}}a_{{12}}+1/8\,{a_{{8}}}^{2}.$$
With these ingredients we are ready to run the PGE algorihm. We
get for two swappable types of edges the sequence
$$1, 4, 13, 104, 1507, 64203, 8426875, 3671999389, 5366787092478,
\\ 26433809041087192, 441089058039611200394,
25113998661290096278734134, \ldots$$
and for three types
$$1, 6, 84, 7946, 5413511, 25231086540, 800871112032930,
\\ 177544715836044855636, 281653040526999655665449719,
\\ 3266495639384107667257990172349726,
\\ 282129919925994006382238965837655927175534,
\\ 184379837924757642947198903200667422197524750679153,
\ldots $$
The Maple code for this is quite compact and shown below.
with(combinat);
pet_cycleind_symm :=
proc(n)
local l;
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, term, res,
cmb, len, l1, l2, cycs, uidx, vidx,
u, v, inst1;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
for t2 in sind do
res := 1;
for u in indets(t1) do
l1 := op(1, u);
for v in indets(t2) do
l2 := op(1, v);
len := lcm(l1, l2);
res := res *
a[len]^(degree(t1, u)*degree(t2, v)
*l1*l2/len);
od;
od;
cindA := cindA + lcoeff(t1)*lcoeff(t2)*res;
od;
od;
cindB := 0;
for term in sind do
res := 1;
# edges on different cycles of different sizes
for cmb in choose(indets(term), 2) do
u := op(1, cmb); v := op(2, cmb);
l1 := 2*op(1, u); l2 := 2*op(1, v);
res := res *
a[lcm(l1, l2)]^((l1*l2/2/lcm(l1, l2))*
degree(term, u)*degree(term, v));
od;
# edges on different cycles of the same size
for u in indets(term) do
l1 := 2*op(1, u); inst1 := degree(term, u);
# a[l1]^(1/2*inst1*(inst1-1)*l1*l1/2/l1)
res := res *
a[l1]^(1/2*inst1*(inst1-1)*l1/2);
od;
# edges on identical cycles of some size
for u in indets(term) do
l1 := 2*op(1, u); inst1 := degree(term, u);
if type(l1/2, even) then
# a[l1]^((l1/2)^2/l1);
res := res *
(a[l1]^(l1/4))^inst1;
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(((l1/2)^2-l1/2)/l1)
res := res *
(a[l1/2]*a[l1]^(l1/4-1/2))^inst1;
fi;
od;
cindB := cindB + lcoeff(term)*res;
od;
(cindA+cindB)/2;
end;
knn_swap_edge_cols :=
proc(n,k)
option remember;
local idx_slots, idx_cols, res, term_a, term_b,
v_a, v_b, inst_a, inst_b, len_a, len_b, p, q;
if n = 1 then
idx_slots := [a[1]];
else
idx_slots := pet_cycleind_knn(n);
fi;
if k = 1 then
idx_cols := [a[1]];
else
idx_cols := pet_cycleind_symm(k);
fi;
res := 0;
for term_a in idx_slots do
for term_b in idx_cols do
p := 1;
for v_a in indets(term_a) do
len_a := op(1, v_a);
inst_a := degree(term_a, v_a);
q := 0;
for v_b in indets(term_b) do
len_b := op(1, v_b);
inst_b := degree(term_b, v_b);
if len_a mod len_b = 0 then
q := q + len_b*inst_b;
fi;
od;
p := p*q^inst_a;
od;
res := res +
lcoeff(term_a)*lcoeff(term_b)*p;
od;
od;
res;
end;
For the triangle case, the symmetry group will still be $D_3$ (of six elements), and not of that a hexagon. The reason is you cannot bring the vertex to an edge. With that in mind, we consider $D_3$ acting on $X$, all possible colorings of vertices and edges with $n$ colors, so $|X| = n^6$ (before considering symmetries). Applying Burnside's theorem, we have the number of orbits $|X/D_3|$ to be
$$|X/D_3| = \frac{1}{|D_3|} \sum_{g\in D_3} |Fix(g)|,$$
where $Fix(g)$ is set of colorings fixed by $g$. Now we analyze this a bit, with $D_3 = \{1,r,r^2 , f_1,f_2,f_3\}$, where $r^i$ are the rotations and $f_j$ are the flips. Then
$|Fix(1)| = n^6$;
$|Fix(r)| = |Fix(r^2)| = n^2$ (one color choice for the vertices, and another color choice for the edges);
$|Fix(f_j)|=n^4$ (one color choice for the vertex where the line of symmetry goes through, one color choice for the edge where the line of symmetry goes across, one color choice for the pair of vertices across the line of symmetry, and one color choice for the pair of edges across the line of symmetry).
Hence $|X/D_3| = \frac{1}{6}(n^6+ 2n^2 + 3n^4)=\frac{1}{6}n^2(n^4+2+3n^2)=\frac{1}{6}n^2(n^2+2)(n^2+1)$. Here I factor it to see that indeed we get an integer as $n^2(n^2+2)(n^2+1)$ is a multiple of 6.
For the square case you similarly consider the symmetry of a square $D_4$ with eight element, and not of an octagon for the same reason that we cannot bring a vertex onto an edge.
Best Answer
This can be done using Power Group Enumeration, where we cover the cycles of the slot permutation group with cycles of the group acting on the colors. We require the cycle indices of the two groups. We get for the slots (symmetries of the square) that they are:
This yields the the cycle index
$$Z(Q) = \frac{1}{8} (a_1^4 + 2 a_1^2 a_2 + 3 a_2^2 + 2 a_4).$$
The cycle index for the colors is by inspection
$$Z(C) = \frac{1}{4} (b_1^5 + 2 b_1^3 b_2 + b_1 b_2^2).$$
Examining all the pairs we get a contribution of
Adding everything up and averaging over $32$ we have at last
$$\bbox[5px,border:2px solid #00A000]{49}$$
colorings. As for this being an exam problem, the amount of computation required and the order of the values that appear presumably makes it possible to do it in about fifteen minutes supposing the author is sure of their arithmetic.
Remark on the PGE algorithm. The heart of the PGE algorithm is to compute the number of orbits by Burnside's lemma which says to average the number of assignments fixed by the elements of the power group. But this number is easy to compute. Suppose we have a permutation $\alpha$ from the slot permutation group $Q$ and a permutation $\beta$ from $C$. If we place the appropriate number of complete, directed and consecutive copies of a cycle from $\beta$ on a cycle from $\alpha$ then this assignment is fixed under the power group action for $(\alpha,\beta)$ , and this is possible iff the length of the cycle from $\beta$ divides the length of the cycle from $\alpha$ . The process yields as many assignments as the length of the cycle from $\beta$.
For example, with the pair $a_1^2 a_2$ and $b_1^3 b_2$ we can cover an instance of $a_1$ with instances of $b_1$ of which there are three, producing $3^2.$ The cycle $a_2$ can be covered with instances of $b_1$ or instances of $b_2$, producing $3+2.$ (There is only one instance of $b_2$.)