3
$\begingroup$

First of all, I am aware that these types of questions are very common and are around the internet in all shapes and sizes. However, in this case I was just really wondering if I'm doing the right thing, as the 'standard' approach wouldn't work here as the size of the problem is too big. Therefore, I thought of some ways to finalize my answer and I'm not sure if I'm missing any steps in my process.

How many non-equivalent 20-bead necklaces can be made if we use 3 different colors? How many can be made with every color appearing at least 3 times?

Let's assume we use the colors Blue, Green and Red, denoted by $b,g,r$ respectively. We will first calculate how many necklaces can be made at all, with no restrictions on the amount of colors appearing each time. The group of necklace operations (turning it bead per bead) is isomorphic to $C_{20}$ or $\mathbb{Z}/20\mathbb{Z}$. Therefore, we can find the terms of the Cycle Index:

  • $\phi(1)=1$ so there's $1$ permutation of order $20; z_1^{20}$

  • $\phi(2) = 1$ so there's $1$ permutation of order $10; z_2^{10}$

  • $\phi(4) = 2; \ 2z_4^5$

  • $\phi(5)=4;\ 4z_5^4$

  • $\phi(10)=4; \ 4z_{10}^2$

  • $\phi(20) = 8; \ 8z_{20}$

where $\phi$ denotes the Euler Phi function. Combining this gives the Cycle Index:

$$Z(z_1,z_2,z_4,z_5,z_{10},z_{20})=\frac{1}{20}\big(z_1^{20}+z_2^{10}+2z_4^5+4z_5^4+4z_{10}^2+8z_{20}\big)$$

Filling in $3$ for each of the $z_i$ gives the CFB-formula, which will lead to all possible 20-bead necklaces using any of the 3 colors. This gives

$$|O|=174\ 342\ 216$$

Now we will look at all the necklaces having each color used at least 3 times. This is the same as looking at all the necklaces that have at least once color used less than 3 times. The latter can then be subtracted from the total number of necklaces possible to get the desired answer.

Edit: this was my initial approach but I forgot about terms where only 2 colors were used at all (and thus not all colors were used more than 3 times). This made me have a direct approach again:

For the term $z_1^{20}$ we are interested in coefficients of the terms $b^3g^ir^{17-i}$ where $i=3,\dots,14$ and $b^4g^ir^{16-i}$ where $i=3,\dots,13$ up until $b^{14}g^3r^3$. The coefficients of these terms are $\binom{20}{3}\binom{17}{i}, \binom{20}{4}\binom{16}{i}\dots \binom{20}{14}\binom{6}{3}$ respectively. From the summation we get:

$$\sum_{n=3}^{14}\bigg[\binom{20}{n}\sum_{i=3}^{17-n}\binom{20-n}{i}\bigg]=3\ 3 02\ 869\ 446$$

For the term $z_2^{10}$ we look at the coefficients of the terms $b^4g^{2i}r^{16-2i}$ where $i=2,\dots,6$ and $b^6g^{2i}r^{14-2i}$ where $i=2,\dots,5$, up until $b^{12}g^4r^4$. Using the same method as before, we get:

$$\sum_{n=2}^{6}\bigg[\binom{10}{n}\sum_{i=2}^{8-n}\binom{10-n}{i}\bigg]=40\ 950$$

For the term $z_4^5$ we can apply the same as before, but not only with even numbers, but with any exponent that's a multiple of 4. Our summation will be:

$$2*\sum_{n=1}^{3}\bigg[\binom{5}{n}\sum_{i=1}^{4-n}\binom{5-n}{i}\bigg]=300$$

The only possibilities for $z_5^4$ are $b^5g^5r^{10},b^5g^{10}r^5$ and $b^{10}g^5r^5$. Our summation will be shorter:

$$4*\bigg[\binom{4}{1}\binom{3}{1}+\binom{4}{1}\binom{3}{2}+\binom{4}{2}\binom{2}{1}\bigg]=144$$

The remaining terms $z_{10}^2$ and $z_{20}$ will not contribute to our counting problem as all the terms $b^ig^jr^k$ will have $i,j,k\geq10$ or either of the exponents being $0$, which means there are no cases in which all three colors are used at all, so in particular they won't be used 3 or more times.

Combining all the coefficients for all the terms using all the colors at least 3 times, we find:

$$|N|=\frac{1}{20}\big(3\ 3 02\ 869\ 446 + 40\ 950 + 300 + 144 \big) = 165\ 145\ 542 $$

$\endgroup$
1
$\begingroup$

It is easier to do this using the principle of inclusion exclusion. Take all $S_0:=174, 342, 216$ necklaces, the for each color subtract the necklaces where that color appears at most twice, then for each pair of colors add back in the doubly subtract necklaces where those two colors appear at most twice.

I do not think the cycle enumerator $Z$ is useful here. You just need to directly look at the necklaces fixed by each symmetry, with these color constraints.

Necklaces with at most $2$ blue beads.

  • There are $2^{20}+20\times 2^{19}+\binom{20}2\times 2^{18}$ necklaces fixed by the identity.

  • There are $2^{10}+10\times 2^{9}$ necklaces fixed by rotation by $10$. The $2^{10}$ accounts for green blue necklaces, and $10\times 2^{9}$ counts necklaces with two blues which are opposite each other.

  • There are $2^{5}$ necklaces fixed by rotation by $5$ and $15$. Note that there must be zero blues.

  • There are $2^{4}$ necklaces fixed by rotation by $4,8,12,16$.

  • There are $2^{2}$ necklaces fixed by rotation by $2,6,14,18$.

  • There are $2^1$ necklaces fixed by all other rotations.

Total: $$S_1=\frac1{20}(2^{20}+20\times 2^{19}+\binom{20}2\times 2^{18}+2^{10}+10\times 2^{9}+2\times 2^5+4\times 2^4+4\times 2^2+8\times 2^1).$$

Necklaces with at most $2$ blue beads and at most $2$ red beads.

  • There are $1+20+\binom{20}2+20\times(1+19+\binom{19}2)+\binom{20}2\times(1+18+\binom{18}2)$ necklaces fixed by the identity.

  • There are $1+10+10+10\times 9$ necklaces fixed by rotation by $10$. The summands count necklaces for which (# red, # blue) = $(0,0),(1,0),(0,1),(1,1)$ in that order.

  • There is $1$ necklaces fixed by rotation by $5$ and $15$. Note that there must be zero blues.

  • There is $1$ necklaces fixed by rotation by $4,8,12,16$.

  • There is $1$ necklaces fixed by rotation by $2,6,14,18$.

  • There is $1$ necklaces fixed by all other rotations.

Total: $$S_2=\frac1{20}\left( \begin{array}{c} 1+20+\binom{20}2+20\times(1+19+\binom{19}2)+\binom{20}2\times(1+18+\binom{18}2)+ \\ 1+10+10+10\times 9+ \\ 2\cdot 1+4\cdot 1+4\cdot 1+8\cdot 1 \end{array} \right)$$.

Finally, the answer is $$ S_0-\binom31S_1+\binom32S_2. $$

$\endgroup$
  • $\begingroup$ I will look into this tomorrow. I had considered inclusion-exclusion but could not figure out how to precisely use the ''at least 3 of each color'' property. Thank you in advance for the elaborate answer $\endgroup$ – Marc Mar 30 at 0:49
  • $\begingroup$ Again thank you for your elaborate answer, this seems to be a little less work as the computations are easier and more straightforward. To me my method seemed more natural in the context of Pólya counting problems (this assignment was from that chapter), as that is the usual approach for these problems. I computed both of our answers and they match, so I assume that both methods are correct! Thanks for the extra insight. $\endgroup$ – Marc Mar 30 at 20:36
0
$\begingroup$

As you have 3 different options for each bead in the necklace then there are "3 to the power of 20" different possible necklaces that you can make.

$\endgroup$
  • 1
    $\begingroup$ Maybe I should have been more clear; I'm talking about nonequivalent necklaces. Consider the case of a 4-bead necklace: R-B-G-B is the same as B-R-B-G because you can 'turn' the necklace one bead over, as it is a circle. In the counting problem, those are not counted as two different necklaces and thus $3^{20}$ will count way too many necklaces. $\endgroup$ – Marc Mar 29 at 22:36
0
$\begingroup$

If you want to find the number of distinct necklaces I would consider the $D_{20}$ dihedral group rather than the $C_{20}$ because you can obtain the same necklace not only by rotating it but also by flipping it along some diagonal. I would then try to use Burnside's Lemma to count the different number of orbits (the different number of necklaces) you can get, that is,

$$\dfrac{1}{|G|}\sum_{g\in G}|fix(g)|$$

$\endgroup$
  • $\begingroup$ Isn't flipping in this case the same as rotating a set amount of times? If not... then I guess the question implied that only rotating was possible. I also can't imagine that they would want me to use the dihedral group as it would take even more work to do the second part of the question... $\endgroup$ – Marc Mar 29 at 22:59
  • $\begingroup$ No, it is not the same. Consider for example a square. You can fix two vertices and interchange the other two using a diagonal flip. You do get equivalent squares, but you cannot get the square resulting from that flip applying any number of rotations to the original one. The group of symmetries of a polygon with $n$ sides is $D_n$, not $C_n$. $\endgroup$ – Elementarium Mar 29 at 23:06
  • $\begingroup$ Okay well that seems obvious. But what if we were to pretend you could only rotate the necklace, was this approach right? $\endgroup$ – Marc Mar 29 at 23:08
  • $\begingroup$ Actually, I have never used your approach to solve this kind of problem so I cannot tell you whether it is right or not. Maybe another user can give more insight into it. However, if you only work with $C_20$, I would highly consider using Burnside's Lemma. Sorry I cannot help more! $\endgroup$ – Elementarium Mar 29 at 23:17
  • $\begingroup$ No problem, thanks for at least taking the time to look into it! In fact, this is a generalization of the Burnside Lemma! (cited CFB in my post). If you fill in $3$ in all the $z_i$ you will get exactly what that Lemma says. The second part goes into more detail with restrictions $\endgroup$ – Marc Mar 30 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.