How many ways are there to color a $3 × 3$ grid in the same way if five squares have to be red and four squares have to be blue?

Question

When configurations after rotations and flips are considered the same, how many ways are there to color a $3 × 3$ grid in the same way if five squares have to be red and four squares have to be blue? We can color a $3 × 3$ grid in $$\frac{n^9 + 4n^6 + n^5 + 2n^3}{8}$$ ways using $n$ colors if configurations after rotations and flips are considered the same.

But I couldn't find how many ways are there when the grid has five squares have to be red and four squares have to be blue. How can I calculate this?

Answer 1

Enumerating the symmetries of the grid for the cycle index so that we may apply PET we obtain

• The identity, $a_1^9.$
• Two rotations by $90$ and $270$ degrees which fix the central slot, $2 a_1 a_4^2$
• One rotation by $180$ degrees which also fixes the central slot, $a_1 a_2^4$
• A vertical and a horizontal flip, which fixes the central column / row: $2 a_1^3 a_2^3$
• A flip about one of the two diagonals which are being fixed, $2 a_1^3 a_2^3.$

We get for the cycle index

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

Just to check we get for colorings using at most $N$ colors

$$\frac{1}{8} (N^9 + 4 N^6 + N^5 + 2 N^3)$$

which gives the sequence

$$1, 102, 2862, 34960, 252375, 1284066, 5105212, \ldots$$

which points to OEIS A217331 where these data are confirmed.

Now we use PET to compute the number of colorings with five red squares and four blue ones, essentially performing

$$[R^5 B^4] Z(Q; R+B),$$

which yields (substitution is $a_d = R^d B^d$)

• $[R^5 B^4] (R+B)^9 = {9\choose 5} = 126$
• $[R^5 B^4] 2 (R+B) (R^4 + B^4)^2 = 2 [R^4 B^4] (R^4 + B^4)^2 = 4$
• $[R^5 B^4] (R+B) (R^2 + B^2)^4 = [R^4 B^4] (R^2 + B^2)^4 = [R^2 B^2] (R + B)^4 \\ = {4\choose 2} = 6$
• $[R^5 B^4] 4 (R+B)^3 (R^2 + B^2)^3 \\ = [R^5 B^4] 4 (R^3 + 3 R^2 B + 3 R B^2 + B^3) (R^2 + B^2)^3 \\ = 4 ( {3\choose 1} + 0 + 3 {3\choose 2} + 0) = 48.$

We thus get for our answer $\frac{1}{8} (126 + 4 + 6 + 48) = 23.$