Exercise 7.2 in Algebraic Combinatorics by Stanley

Question

This is exercise 2 in chapter 7 of Algebraic Combinatorics by Stanley.

For part (a), I first found the entire automorphism group. By labeling the root 1, and then numbering off the remaining vertices row by row from left to right, i.e. the right edge in the middle row would be vertex number 3. Then, the automorphism group $G$ has elements (where I don't name 1-cycles) $$\{\text{id}, (2, 3)(4, 6)(5, 7), \, (2, 3)(4, 7)(5, 6), \, (2, 3)(4, 6, 5, 7), \, (2, 3)(4, 7, 5, 6), \, (6, 7), \, (4, 5), \, (6, 7)(4, 5)\}$$ Clearly $|G| = 8$, so the cycle index polynomial should be $$Z_G(z_1, z_2, \dots, z_6) = \frac{1}{8}(z_1^6 + 2z_2^3 + 2z_2z_4 + 2z_2z_1^4 + z_2^2 z_1^2).$$ Now, we directly get the answer for part (b) by plugging in $z_i = n$, for $i \in [6]$. Then when $n = 2$, the number of non-automorphic colorings using $n$ colors should be $(64 + 16 + 8 + 64 + 16)/8 = 21$. However, since the root, vertex number 1, always gets mapped to itself, then there should be an even number of non-automorphic colorings, as there are two choices for coloring the root.

So, where did I go wrong? Is my cycle index polynomial wrong, or is my reasoning for there being an even number of non-automorphic colorings incorrect?

Answer 1

Your cycle index polynomial is wrong because there are in fact 7 vertices, not 6. You have omitted a single 1-cycle from each term of the polynomial, and thus there are actually 42 non-automorphic colorings with 2 colors rather than 21.

Your reasoning is correct; in fact, the existence of a common fixed point indicates that $z_1$ should divide $Z_G$.