1
$\begingroup$

I am trying to compute the number of ways of placing 4 blue beads, 3 yellow beads, and 1 green bead on a circular necklace.

My thought: apply Burnside's Theorem. $$ |S| = {8\choose{4}} \cdot 4 = 280. $$ $\mathrm{Fix}(e) = S$. Because there is only one green bead, no rotation can fix $S$. Similarly, the only way for a reflection to fix a configuration is if it fixes the green bead. So no reflection across a line perpendicular to two edges can fix $S$. For reflections across a line through two vertices, there are $2$ ways to choose where to put the green bead (the other vertex gets a yellow bead) and $3$ ways to color the other $6$ beads. So $6$ configurations in total for each reflection. We conclude $$ N = \frac1{16}\left(280 + 4 \cdot 6\right) = 19. $$

Am I correct here? Did I miscalculate anything? Thanks in advance!

$\endgroup$
6
  • $\begingroup$ "3 ways to color the other 6 beads" How did you get this? At this point there are 2 yellow and 4 blue beads left to be arranged over the remaining 6 locations on the necklace. $\endgroup$ Apr 13, 2023 at 9:41
  • $\begingroup$ So there are three pairs of locations that need to be chosen in order for reflection to fix that configuration. Choose one of the three to put the yellow pair and the remaining two pairs get blue. Am I correct here? $\endgroup$ Apr 13, 2023 at 9:43
  • $\begingroup$ Oh yes, I see now. You are correct. $\endgroup$ Apr 13, 2023 at 9:45
  • 1
    $\begingroup$ Your answer of $19$ is correct. Alternate equivalent method: Hold the green bead at the top. There are $\binom{7}{3}=35$ ways to arrange the blue/yellow beads, but $3$ of those are mirror-symmetric. This means there are $\frac{35-3}{2}=16$ asymmetric ones and their mirror images, and $3$ symmetric ones for a total of $19$ unique ones. This is basically Burnside using only a single reflection, a group of order $2$. $\endgroup$ Apr 13, 2023 at 9:52
  • 2
    $\begingroup$ If you allow turning-over / reflections as well as rotations, then I thought you had a bracelet rather than a necklace. Wikipedia is not quite as dogmatic as this, but it does suggest some ambiguity $\endgroup$
    – Henry
    Apr 13, 2023 at 10:02

2 Answers 2

1
$\begingroup$

The Polya Enumeration Theorem is a natural tool for problems like this and verifies that the answer is $19$.

The group of permutations is $D_8$, the dihedral group on $8$ vertices. The cycle index of $D_8$ is $$Z = \frac{1}{16} (x_1^8 + 4 x_1^2 x_2^3 + 5 x_2^4 + 2 x_4^2 + 4 x_8)$$ The figure inventory for three colors blue, green, and yellow is $b+g+y$. On "substitution" of the figure inventory into the cycle index, we have $$Z = \frac{1}{16}[(b+g+y)^8 + 4(b+g+y)^2 (b^2+g^2+y^2)^3 + 5(b^2+g^2+y^2)^4 + 2(b^4+g^4+y^4)^2 + 4(b^8+g^8+y^8)]$$

The coefficient of $b^4 g^1 y^3$ when $Z$ is expanded is $19$, so the number of distinct colorings with $4$ blue, $1$ green, and $3$ yellow beads is $19$.

$\endgroup$
1
  • $\begingroup$ I see! Thank you very much for the verification! $\endgroup$ Apr 13, 2023 at 19:55
1
$\begingroup$

Since there is one green bead, we will use it as our reference point. Relative to the green bead, we can place the four blue beads in $\binom{7}{4}$ ways as we proceed clockwise around the circle. The other three positions must be filled with the yellow beads. Hence, up to rotation, there are $$\binom{7}{4} = 35$$ possible arrangements of the beads on the necklace.

Since we are interested in the number of arrangements up to rotation and reflection, we must consider which of these arrangements are their own reflections. The only way this can occur is if there is a yellow bead opposite the green bead (since there are an odd number of yellow beads and an even number of blue beads) and the remaining two yellow beads are opposite each other relative to the axis through the green bead and the yellow bead opposite to it. There are three ways that this can occur, as shown below.

arrangements_with_bilateral_symmetry

These three arrangements have been counted once. The remaining $35 - 3 = 32$ arrangements have been counted twice, once when we string the beads clockwise and once when we string the same beads in the opposite order clockwise since turning over the necklace will produce the same arrangement as before. Hence, there are $$3 + \frac{\binom{7}{4} - 3}{2} = 3 + 16 = 19$$ distinguishable arrangements up to rotation and reflection. Equivalently, we can add the three arrangements that are their own reflections to the total number of arrangements up to rotation and then divide by $2$ to obtain $$\frac{\binom{7}{4} + 3}{2} = 19$$ distinguishable arrangements up to rotation and reflection.

$\endgroup$

You must log in to answer this question.

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