2
$\begingroup$

Find the number of ways to fill a 3*3 grid (with corners indistinguishable) if you have 3 black and 6 white marbles.
Approach till now[Incorrect]:
No. of ways of arranging 3 black marbles or 6 white marbles = $(^9C_3)$ = 84.
Since there are 4 different ways to view the grid hence the answer is $84\over4$=$21$

$\endgroup$
12
  • 1
    $\begingroup$ Where is Part 1 of this question? $\endgroup$
    – apnorton
    Oct 9, 2013 at 21:18
  • $\begingroup$ math.stackexchange.com/questions/520658/… $\endgroup$
    – rnjai
    Oct 9, 2013 at 21:18
  • 1
    $\begingroup$ There we go! Sorry about the confusion. I realized I'd made a mistake and deleted my answer to edit it, but you'd already deleted the question by the time I was finished! It should be fine, now. $\endgroup$ Oct 9, 2013 at 21:45
  • 3
    $\begingroup$ @stevemarvell: It means that if an arrangement can be obtained by rotating the grid from another arrangement, then the two arrangements are indistinguishable. $\endgroup$ Oct 9, 2013 at 21:46
  • 2
    $\begingroup$ But not reflection? $\endgroup$ Oct 9, 2013 at 21:47

3 Answers 3

3
$\begingroup$

In the marked-corner case, this amounts to choosing spots for the three black balls, so there are $\binom93=84$ ways to do it.

Now, the answer to the unmarked-corner case depends on what is allowed.


Case 1: Let's suppose that if one arrangement is a rotation of another, then they are considered to be the same (my initial interpretation). Note that only $4$ of the $84$ arrangements have any rotational symmetry--in particular, those in which one black ball is in the middle slot, and the other two black balls are on opposite sides or corners. Each of those $4$ can be viewed in only two "different-looking" ways without markings, while the other $80$ can all be viewed in $4$ "different-looking" ways without markings. Consequently, if we "unmark" the corners, then there are $$\frac{80}4+\frac{4}{2}=22$$ ways to arrange the marbles, and not $21$.


Case 2: Let's suppose that reflections are also permitted, as well as rotations. The $4$ arrangements mentioned above still each have only two "different-looking" ways that they can be viewed. Let's say that there are $m$ arrangements with neither reflection symmetry nor rotational symmetry. Since the $4$ mentioned above have both kinds of symmetry, then there are $80-m$ arrangements with reflection symmetry, but no rotational symmetry. Those with neither type of symmetry (for example, with black balls at top-left, center, and bottom) can be viewed in $8$ "different-looking" ways, and those with reflection symmetry only (for example, all three black balls in the top row) can be viewed in $4$ "different-looking" ways. Thus, there are $$\frac42+\frac{80-m}4+\frac{m}8=\frac{176-m}8$$ ways to arrange the marbles in this case, so it remains to determine the number $m$.

Note that if no corner has a black ball, then the arrangement necessarily has at least one kind of symmetry. Thus, we need only consider those arrangements (on the marked grid) with a black ball in at least one corner, having no symmetry. Further note that if all three black balls are in corners, then we have reflection symmetry, so we need not consider arrangements with black balls in more than two corners. Let us consider the distinct possibilities:

  1. There are black balls in two opposite corners, such as $a$ and $c$ in the original problem ($2$ ways to do this). To avoid any kind of symmetry, we must place the final black ball in one of the edge slots ($4$ ways to do this). Hence, there are $8$ non-symmetric arrangements with black balls in two opposite corners.
  2. There are black balls in two non-opposite corners ($4$ ways to do this). To avoid any kind of symmetry, we must place the final black ball in one of the edge slots adjacent to one of the previously-placed black balls, but not adjacent to the other ($2$ ways to do this). Hence, there are $8$ non-symmetric arrangements with black balls in two non-opposite corners.
  3. There is a black ball in exactly one corner ($4$ ways to do this), and no black ball in either adjacent edge slot. Note that if both remaining black balls are in edge slots, then we have reflection symmetry along a diagonal, so one of the remaining black balls is in the center, and one must be in one of the other two edge slots. Hence, there are $8$ non-symmetric arrangements with exactly one black ball in a corner, and no black ball in either adjacent edge slot.
  4. There is a black ball in exactly one corner ($4$ ways to do this), and a black ball in at least one of the two adjacent edge slots. To avoid reflection symmetry along a diagonal, we can't have black balls in both adjacent edge slots, so there are $2$ ways to place the adjacent black ball. There are then three available slots in which to place the final black ball, and none of them yield any symmetry. Hence, there are $24$ non-symmetric arrangements with exactly one black ball in a corner, and a black ball in at least one of the two adjacent edge slots.

There are no other non-symmetric arrangements, and the above types are distinct, so $m=8+8+8+24=48,$ and so there are $$\frac{176-m}8=\frac{128}8=16$$ ways to arrange the marbles in the unmarked grid, if both rotations and reflections are allowed.

$\endgroup$
3
$\begingroup$

This can also be solved with the Polya Enumeration Theorem. We just need the cycle structure of the elements of the automorphism group $G$ of your grid. We now compute the cycle index of $G.$

There is the identity, which contributes $a_1^9.$

There are two reflections about a vertical/horizontal axis through the center, which contribute $2\times a_1^3 a_2^3.$

There are two reflections about the two diagonals, which contribute $2\times a_1^3 a_2^3.$

Finally, there are three rotations. One of these, the rotation by 180 degrees, contributes $a_1 a_2^4.$ The two rotations by 90 degrees contribute $a_1 a_4^2.$

It follows that the desired cycle index is $$Z(G) = \frac{1}{8} (a_1^9 + 4 a_1^3 a_2^3 + a_1 a_2^4 + 2 a_1 a_4^2).$$

Hence the substituted cycle index becomes $$Z(G)(B+W) = 1/8\, \left( B+W \right) ^{9}+1/2\, \left( B+W \right) ^{3} \left( {B}^{2}+{W}^{2} \right) ^{3}\\+1/8\, \left( B+W \right) \left( {B}^{2}+{W}^{2} \right) ^{4}+1/4\, \left( B+W \right) \left( {B}^{4}+{W}^{4} \right) ^{2}.$$

Expansion yields $$Z(G)(B+W) = {B}^{9}+{W}^{9}+3\,{B}^{8}W+8\,{B}^{7}{W}^{2}+16\,{B}^{6}{W}^{3}+23\,{B}^{5}{W}^{4}+ 23\,{B}^{4}{W}^{5}\\+16\,{B}^{3}{W}^{6}+8\,{B}^{2}{W}^{7}+3\,B{W}^{8}.$$

It follows that the desired quantity is $$[B^3 W^6] Z(G)(B+W) = 16.$$ The above generating function also produces the count of all other black/white distributions for this grid. E.g. the coefficient on $B^8 W$ is equal to three because the white marble can be in three positions, the center, the center of one of the four sides, or at a corner.

The above cycle index can also be used to calculate the total number of colorings when there are $N$ different colors of marbles, where not all of them must be used, i.e. $$Z(G)(C_1+C_2+\cdots+C_N)_{C_1=1, C_2=1, \cdots C_N=1}.$$ This gives the formula $$\frac{1}{8} (N^9 + 4 N^6 + N^5 + 2 N^3)$$ which yields $$ 1, 102, 2862, 34960, 252375, 1284066, \ldots$$ This sequence even has an entry at the OEIS.

There is a similar calculation at this MSE link.

$\endgroup$
2
$\begingroup$

I approached this on paper with the following method:

There are three ways to choose the first ball: centre, corner and edge

If the we start with the centre then then there are two places for the next ball: corner and edge. In either case, you can place the third ball in any of the places down an empty edge or next to the second ball, but there are two repeats, so we have six.

If we place the first ball on a corner, we naturally exclude the centre and can choose any one of four places for the next ball.

In the adjacent case, this generates six possibilities. Two further cases for the near corner. One more for the far edge. All the opposite corner ones are covered.

This leaves one for the three edges.

$$6+6+2+1+1 = 16$$

I know it's not mathsy and I wish I could have done some interesting inclusion/exclusion, but I can't :)

$\endgroup$
3
  • $\begingroup$ +1: Very nice! Lack of "mathsiness" notwithstanding. ;-) $\endgroup$ Oct 10, 2013 at 4:02
  • 1
    $\begingroup$ By the way, just so you know, there are only a few ways that people will get notifications that you've been trying to interact with them: [1] you've commented on their post, whether question or answer (so Rnjai Lamba was notified of all your comments above, and you were notified of my comments); [2] you and the other person are the only two people to comment on a particular post, regardless of whose post it is; [3] you've posted an answer to another person's question (again, Rnjai Lamba has been alerted); (cont'd) $\endgroup$ Oct 10, 2013 at 4:08
  • 1
    $\begingroup$ [4] you post a comment with (for example) @CameronBuie in a comment stream that the other user has participated in (be aware that you can only "tag" one user at a time in this fashion); [5] they happen upon your comment in passing (this would be how I've found all of your comments thus far, because I was interested in the progression of this post). It's a lot to remember, I know. (Took me some time to learn, and I still forget to "tag" people periodically!) $\endgroup$ Oct 10, 2013 at 4:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .