Newsgroups: rec.puzzles From: tycchow@zermelo.mit.edu (Timothy Y. Chow) Subject: Re: TicTacToe puzzle Message-ID: <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 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 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