Polya's Enumeration : Where am I going wrong?

Question

If we write a 9 digit binary number as a $3\times3$ matrix, for example $101110101$ would be written as, $$\begin{bmatrix}1 & 0 & 1\\\ 1 & 1 & 0\\\ 1 & 0 & 1 \end{bmatrix}$$ We can take general representation for any 9 digit binary string as follows, $$I = \begin{bmatrix}I_{00} & I_{01} & I_{02}\\\ I_{10} & I_{11} & I_{12}\\\ I_{20} & I_{21} & I_{22} \end{bmatrix}$$ Now, If I put every number represented by permutations of the indices into the same set, then how many such sets would I have?
To give an example, we apply permutation $\pi_{1,0,2}$ on $I$ $$\pi_{1,0,2}(I) = \begin{bmatrix}I_{11} & I_{10} & I_{12}\\\ I_{01} & I_{00} & I_{02}\\\ I_{21} & I_{20} & I_{22} \end{bmatrix}$$ A more specific example would be $111100001$ becomes $001010111$ by permutation (1,0,2). So we have to essentially divide these $2^9$ numbers into $x$ sets, what is $x$

---

So this question has been answered here Finding equivalence classes under permutation symmetry. Now I wanted to answer this question using Polya's Enumeration. And I figured out the generating function to be $$\frac{x_1^3+3x_1x_2+2x_3}{6}$$ I am not clear as to what should I put the value of $x_i$ to be? It is definitely not 2, but then what?

Answer 1

You have the wrong cycle index. If we analyze the structure of the group in terms of its effects on the 3 by 3 array, there are

• $1$ permutation that leaves all $9$ elements fixed,
• $3$ permutations that have $4$ cycles of length $2$ and leave $1$ element fixed, and
• $2$ permutations that have $3$ cycles of length $3$.

So the cycle index is $$Z = \frac{1}{6} (x_1^9 + 3 x_1 x_2^4 + 3 x_3^3)$$ The figure inventory, since there are $2$ binary digits, is $x+y$. If we "substitute" the figure inventory into the cycle index, the result is $$f(x,y) = \frac{1}{6} [ (x+y)^9 + 3(x+y)(x^2 + y^2)^4 + 2 (x^3+y^3)^3 ] $$ The significance of $f$ is that if we want to know the number of distinct arrays with $3$ zeroes and $6$ ones, for example, it is the coefficient of $x^3 y^6$ when $f$ is expanded. But if we want to know the count of all the possibilities, we can simply let $x=y=1$, with the result $$f(1,1) = \frac{1}{6}[2^9 + 3(2)2^4 = 2(2^3)] = \boxed{104}$$