How many ways are there of arranging 3 crosses and 3 noughts on a 3x3 tictactoe board (excluding rotations...

[ Editor: the answer is 228.  The questioner's own program gave 228; Takayuki Nakao's
program first gave 212, which he then withdrew: "Oops!  I made VERY
easy mistakes in my program!  The right answer is 228." ]

There are 9!/((3!)^3)=1680 ways to play three X's, three O's, and
three blanks in nine squares.  However, this counts rotations and
reflections as different.

Label the squares as follows:

123
456
789

No pattern is symmetrical under rotation.  To see this, note that a
180-degree rotation interchanges pairs of squares, and leaves the
center unchanged.  Thus it can only leave the three X's unchanged if
there is an X in the center, and it can only leave the three O's
unchanged if there is an O in the center.

Reflection in a vertical line interchanges the pairs 1-3, 4-6, and 7-9,
and leaves 2, 5, and 8 unchanged.  Thus the pairs 1-3, 4-6, and 7-9
must each be two identical symbols; with three X's, three O's, and
three blanks, one pair of each must be used; this can be done in six
ways.  The last three symbols can be placed in the remaining spaces in
six ways, for a total of 36 arrangements which are symmetric about a
vertical line.  (Rotations of these 36 are symmetric about a vertical
line.)

Likewise, reflection in the 1-5-9 diagonal interchanges the pairs 2-4,
3-7, and 6-8, leaving the other three unchanged, so there are 36
arrangements which are symmetric about this diagonal.  No arrangement
can be symmetric about both a vertical line and a diagonal, because the
above relations show that 1, 3, 7, and 9 would all have to be the same.

Thus there are 72 arrangements which can be rotated to give four
different patterns, but not reflected.  These 72 use up 4*72=288 of the
1680 above, leaving 1392.  All other arrangements can be rotated or
reflected to give eight different patterns, so there are 1392/8=174
such arrangements, for a grand total of 72+174=246.

-- David Grabiner <grabiner@math.harvard.edu>

[ Editor: the horizontal line and the 3-5-7 diagonal also give 36
symmetric arrangements each, so there are 144 symmetric arrangements in
36 classes of four, and (1680-144)/8 = 192 other classes: 36+192 = 228. ]

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 tic-tac-toe 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 tic-tac-toe 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 ninety-degree
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 <tycchow@math.mit.edu>