How many ways are there to color the $H$-shaped tree with $3$ colors such that each color is used exactly twice?

Question

How many ways are there to color this graph with the following constraints? We have three colors: blue, red, green, and we require that the number of nodes of color green is 2, and blue 2, and red 2 - the same number.

And here is my attempt:

Automorphisms: $$(1)(2)(3)(4)(5)(6)$$ $$(34)(1)(2)(5)(6)$$ $$(56)(1)(2)(3)(4) $$ $$(34)(56)(1)(2)$$ $$(12)(35)(46)$$ $$(12)(36)(45)$$

Cycle index of group: $$Z_G(x_1,...,x_6) =\frac16 (x_1^6 + 2x_2^3 + 2x_2x_1^4 + x_2^2x_1^2) $$ And using Pólya theorem we get generating function: $$U_D(g,r,b) = Z_G(g+r+b, g^2+r^2+b^2, ...,g^6+r^6+b^6) = \\ \frac16 ((g+r+b)^6 + 2(g^2+r^2+b^2)^3 + 2(g^2+r^2+b^2)(g+r+b)^4 + (g^2+r^2+b^2)^2(g+r+b)^2)$$

And coefficient with $r^2g^2b^2$ is $\frac16 (90 + 12 +0 + 0 ) = 17$

Is it solution correct?

Answer 1

I have little to add here, except maybe a verbal description of the automorphisms as they contribute to the cycle index $Z(G)$ of the automorphism group $G$. Let's do the enumeration one more time.

First, there is the identity, contributing $a_1^6$. There is a flip of the left fork, which gives $a_2 a_1^4.$ Same for the right fork, $a_2 a_1^4.$ With both forks flipped we get $a_1^2 a_2^2.$ Now do a flip about the vertical axis passing through the midpoint of the central bridge, yielding $a_2^3.$ Combine this flip with a single flip of one of the forks to get $2 a_2 a_4.$ Finally, there is the major flip combined with a flip of both forks for a contribution of $a_2^3.$

$$Z(G) = \frac{1}{8} (a_1^6 + 2 a_1^4 a_2 + a_1^2 a_2^2 + 2 a_2^3 + 2 a_2 a_4).$$

Doing the substitution we obtain $$Z(G)(R+B+G) = 1/8\, \left( R+B+G \right) ^{6}+1/4\, \left( R+B+G \right) ^{4} \left( {B}^{2}+{G}^{2}+{R}^{2} \right)\\ +1/8\, \left( R+B+G \right) ^{2} \left( {B}^{2}+{G}^{2}+{R}^{2} \right) ^{2}+1/4\, \left( {B}^{2}+{G}^{ 2}+{R}^{2} \right) ^{3}\\+1/4\, \left( {B}^{2}+{G}^{2}+{R}^{2} \right) \left( {B}^{4}+{G}^{4}+{R}^{4} \right).$$

This expands to $${B}^{6}+2\,{B}^{5}G+2\,{B}^{5}R+5\,{B}^{4}{G}^{2}+7\,{B}^{4}GR+5\,{B}^{ 4}{R}^{2}+5\,{B}^{3}{G}^{3}+12\,{B}^{3}{G}^{2}R\\+12\,{B}^{3}G{R}^{2}+5\, {B}^{3}{R}^{3}+5\,{B}^{2}{G}^{4}+12\,{B}^{2}{G}^{3}R+18\,{B}^{2}{G}^{2} {R}^{2}+12\,{B}^{2}G{R}^{3}\\+5\,{B}^{2}{R}^{4}+2\,B{G}^{5}+7\,B{G}^{4}R+ 12\,B{G}^{3}{R}^{2}+12\,B{G}^{2}{R}^{3}+7\,BG{R}^{4}+2\,B{R}^{5}\\+{G}^{6 }+2\,{G}^{5}R+5\,{G}^{4}{R}^{2}+5\,{G}^{3}{R}^{3}+5\,{G}^{2}{R}^{4}+2\, G{R}^{5}+{R}^{6}.$$

The result is that $$[R^2 G^2 B^2] Z(G) = 18.$$

This cycle index produces the following sequence when $N$ colors are used: $$1, 21, 171, 820, 2850, 8001, 19306, 41616, 82215, 151525,\ldots$$ which is $$\frac{1}{8} (N^6 + 2 N^5 + N^4 + 2 N^3 + 2 N^2).$$

The following Maple code was used to aid in this computation.

with(numtheory);
with(group):
with(combinat):


hgraph_cycleind := 
1/8*(a[1]^6 + 2*a[1]^4*a[2] + a[1]^2*a[2]^2 + 2*a[2]^3+ 2*a[2]*a[4] );

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;

v :=
proc(n)
        option remember;
        local p, k, gf;

        p := add(cat(q, k), k=1..n);
        gf := expand(pet_varinto_cind(p, hgraph_cycleind));

        subs({seq(cat(q, k)=1, k=1..n)}, gf);
end;

By way of a sanity check the coefficient on $R^5 G$ which is two seems correct, because there are only two colorings distinguished by whether the singleton ends up on a fork or on the bridge. Similarly the coefficient on $R^4 G^2$ is five, which corresponds to the two green elements on the same fork, on different forks, on the bridge, one on the bridge with the other on a fork one adjacent to it and one on the bridge with the other one on a fork not adjacent to it.