Newsgroups: rec.puzzles
From: tycchow@zermelo.mit.edu (Timothy Y. Chow)
Subject: Re: TicTacToe puzzle
MessageID: <1994Jan11.051946.23698@galois.mit.edu>
Organization: None. This saves me from writing a disclaimer.
References: <2grt08$6qi@salmon.maths.tcd.ie>
Date: Tue, 11 Jan 94 05:19:46 GMT
In article <2grt08$6qi@salmon.maths.tcd.ie>, Nicholas Gray writes:
> How many ways are there of arranging 3 crosses and 3 noughts
> on a 3x3 tictactoe board (excluding rotations and reflections)?
Well, so far in this thread we have three candidates: 228, 212, and 246.
This illustrates how easy it is to get confused trying to take account
of symmetries.
Fortunately, there is a famous theorem of combinatorics that deals exactly
with this kind of problem: Polya's counting theorem. This deserves to be
better known, so let me state it carefully (without proof) and apply it to
the problem at hand. I will assume that the reader knows a little bit (not
much) of the terminology of group theory and in particular of the group of
permutations. (Incidentally, I think Polya's theorem is an excellent way
to motivate the study of group theory.)
First I need to define a "cycle index polynomial." Let S_n be the group of
permutations of n objects, and let H be a subgroup of S_n. The cycle index
polynomial Z_H(x_1, ..., x_n) is defined to be
1 
 > x_1^(c_1[s]) * x_2^(c_2[s]) * ... * x_n^(c_n[s]).
H 
s in H
Here H is the number of elements of H, the sum is over all elements s
in H, and c_i[s] is the number of cycles of length i in the disjoint cycle
decomposition of s. For example, if n = 6 and s is the permutation on the
set {1,2,3,4,5,6} given by s(1) = 3, s(2) = 2, s(3) = 4, s(4) = 1, s(5) = 6
and s(6) = 5, then the disjoint cycle decomposition of s consists of one
cycle of length 1, one cycle of length 2, and one cycle of length 3, so
c_1[s] = c_2[s] = c_3[s] = 1 and c_4[s] = c_5[s] = c_6[s] = 0.
Now suppose we are given a set of n objects and a set of c colors and a
subgroup H of the group of permutations of the n objects. Given c
numbers r_1, r_2, ..., r_c, let N(r_1, r_2, ..., r_c) be the number of
ways of coloring the n objects if we demand that the first color be
used r_1 times, the second color r_2 times, ..., the cth color r_c
times, and if we also do not count two colorings as different if they
are related by an element of the group H. What the Polya counting theorem
does is to tell us how to compute N(r_1, ..., r_c).
In the case of the tictactoe problem, we have nine objects (the spaces
in the grid), three colors (X, O and blank), and we want to know how many
ways there are of coloring the objects such that each color is used exactly
three times (r_1 = r_2 = r_3 = 3), with the proviso that two colorings are
not considered different if they are related by an element of H, where H
is the subgroup of permutations of the nine spaces generated by rotations
and reflections. Note that H = 8 and that H is just a dihedral group.
Now for the Polya counting theorem! It states that

> N(r_1, ..., r_c) * t_1^(r_1) * t_2^(r_2) * ... * t_c^(r_c)

r_1, ..., r_c
= Z_H( t_1+...+t_c, t_1^2+...+t_c^2, ..., t_1^n+...+t_c^n ).
where t_1, ..., t_c are independent indeterminates, and the sum is over
all values of the r_i. This expression looks formidable; what does it tell
us? What it says is that to compute the value of N(r_1, ..., r_c), first
compute the cycle index polynomial of the group H of symmetries. Then
simply substitute t_1 + ... + t_c for x_1, substitute t_1^2 + ... + t_c^2
for x_2, and so on, and expand everything out. Then look for the term
t_1^(r_1) * t_2^(r_2) * ... * t_c^(r_c). The coefficient of this term is
the desired number N(r_1, ..., r_c).
This might not look much better than simply enumerating all possibilities
and sorting out equivalent colorings, but if you work out a couple examples,
you'll see that it is much easier to use Polya's theorem, especially since
computer algebra packages to do the tedious polynomial expansion are a dime
a dozen these days. Furthermore, the expansion has to be done only once,
and you get N(r_1, .., r_c) for *all* values of r_1, ..., r_c simultaneously.
So now let's work out the tictactoe example. First we need to compute
the cycle index polynomial of H. There are eight summands, one for each
element of H. The identity element consists of nine cycles of length 1
each, so it contributes x_1^9. There are two ninetydegree rotations,
which cycle the "edge" spaces and the "corner" spaces and leave the center
invariant, so each of these rotations contributes x_1 * x_4^2. There is
a 180 degree rotation which flips everything in pairs except the center;
it contributes x_1 * x_2^4. Finally, there are four reflections which
each leave three elements invariant and flip three pairs, so each one
contributes x_1^3 * x_2^3. Summing these all up and dividing by H = 8,
we get
Z_H(x_1, ..., x_4) = (x_1^9 + 2*x_1*x_4^2 + x_1*x_2^4 + 4*x_1^3*x_2^3)/8.
Now we just substitute x_1 = t_1 + t_2 + t_3, x_2 = t_1^2 + t_2^2 + t_3^2,
etc., expand, and read off the coefficient of t_1^3 * t_2^3 * t_3^3. Using
Maple, I find that the answer is 228, confirming Nicholas Gray's answer.

Tim Chow
Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
only 1 1/2 tons. Popular Mechanics, March 1949