4
$\begingroup$

I have a hard question about a way how many different necklaces can be made.

Suppose that we have the following restrictions:

  1. We have 3 groups of beads:
    • 4 triangle beads
    • 6 square beads
    • 8 circle beads

All the beads in one group are completely identical. This means that if you put two triangle beads next to each other and then switch their positions this counts as one necklace because the beads are identical

  1. Necklaces are identical if they are identical under symmetric operations just as rotate them (𝑟) or turning them around (𝑠).

So if we have a necklace ordered in one way and we rotate it 180 deg or just flip a side this is count as one necklace.

  1. We need to use all the 18 beads in each and every new necklace. We can not create a necklace from 17, 16 or less than 18 beads.

I read all the topics here but could not find a question about a group of identical beads. I also read Burnside lemma and Pólya_enumeration_theorem and Necklace_(combinatorics) in wikipedia, but could not find a way how to solve this and what is the correct answer.

From Burnside lemma, I found that the answer should be 57, but is this correct?

I used directly the formula from Burnside lemma, but it does not seem quite right for me, because I do not take into account that the three groups are with different numbers of beads.

$$\frac{1}{24} * (n^6 + 3 * n^4 + 12 * n^3 + 8 * n^2)$$

where n is 3 from three groups.

$$\frac{1}{24} * (3^6 + 3 * 3^4 + 12 * 3^3 + 8 * 3^2) = 57$$

However, as I said earlier despide the fact that the result looks some kind realisting I am not sure that this is the right answer, because I do not use in the formula that we have 4 triangle, 6 square and 8 circle beads.

It looks like Pólya enumeration theorem weighted version is the thing that I need. However, I am not sure how to get to the right answer

Thanks in advance.

$\endgroup$
7
  • $\begingroup$ Welcome to MSE! Pls show your work for arriving at $57$ so someone can check its correctness. You can do that by editing your question and e.g. putting your work at the end. $\endgroup$
    – antkam
    May 6 '20 at 20:53
  • $\begingroup$ Thanks @antkam, for the answer. I modified the questions and added the formula that I used and a short description why I think that despide the fact that the result looks like a good number I think that this is not quite right. $\endgroup$ May 7 '20 at 5:54
  • $\begingroup$ See here: math.stackexchange.com/questions/600/… $\endgroup$ May 7 '20 at 16:19
  • $\begingroup$ Does this answer your question? Circular permutations with indistinguishable objects $\endgroup$ May 7 '20 at 16:19
  • 1
    $\begingroup$ I think you should be using the word "bracelet" and not "necklace". The answer in the link provided by @Vepir gives an answer to your problem for necklaces, which means objects with a cyclic symmetry group, when you want a dihedral symmetry group. This being said you should be able to follow the same line of argument to find the formula you need. $\endgroup$ May 11 '20 at 20:04
0
+100
$\begingroup$

I manage to answer the question and this is the process that I followed:

I consider the 18-bead necklace in the first part of the problem. Here are the eighteen rotations expressed in cycle form where we assume that the slots are numbered from 1 to 18 in clockwise order. The first is the identity (e: no rotation) and the second is the generator g—a rotation by a single position which, when repeated, generates all the elements of the group:

$e = g^0 \text{ = (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15) (16) (17) (18)}$

$g^1 \text{ = (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18) }$

$g^2 \text{= (1 3 5 7 9 11 13 15 17) (2 4 6 8 10 12 14 16 18)}$

$g^3 \text{= (1 4 7 10 13 16) (2 5 8 11 14 17) (3 6 9 12 15 18)}$

$g^4 \text{= (1 5 9 13 17 3 7 11 15) (2 6 10 14 18 4 8 12 16)}$

$g^5 \text{= (1 6 11 16 3 8 13 18 5 10 15 2 7 12 17 4 9 14)}$

$g^6 \text{= (1 7 13) (2 8 14) (3 9 15) (4 10 16) (5 11 17) (6 12 18)}$

$g^7 \text{= (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18)} $

$g^8 \text{= (1 9 17 7 15 5 13 3 11) (2 10 18 8 16 6 14 4 12)} $

$g^9 \text{= (1 10) (2 11) (3 12) (4 13) (5 14) (6 15) (7 16) (8 17) (9 18)} $

$g^{10} \text{= (1 11 3 13 5 15 7 17 9) (2 12 4 14 6 16 8 18 10)} $

$g^{11} \text{= (1 12 5 16 9 2 13 6 17 10 3 14 7 18 11 4 15 8)} $

$g^{12} \text{= (1 13 7) (2 14 8) (3 15 9) (4 16 10) (5 17 11) (6 18 12)} $

$g^{13} \text{= (1 14 9 4 17 12 7 2 15 10 5 18 13 8 3 16 11 6)} $

$g^{14} \text{= (1 15 11 7 3 17 13 9 5) (2 16 12 8 4 18 14 1 6)} $

$g^{15} \text{= (1 16 13 10 7 4) (2 17 14 11 8 5) (3 18 15 12 9 6)} $

$g^{16} \text{= (1 17 15 13 11 9 7 5 3) (2 18 16 14 12 10 8 6 4)} $

$g^{17} \text{= (1 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2)} $

After that I found the GCD for all cycle form's with and group them in a table:

| Cycle length | Permutations | GCD with 18 |

| 1 | $g^0$ | GCD(0, 18)=18 |

| 2 | $g^9$ | GCD(9, 18)=9 |

| 3 | $g^6$, $g^{12}$ | GCD(6, 18)=GCD(12, 18)=6 |

| 6 | $g^3$, $g^{15}$ | GCD(3, 18)=GCD(15, 18)=3 |

| 9 | $g^2$, $g^4$, $g^8$, $g^{10}$, $g^{14}$, $g^{16}$ | GCD(2, 18)=GCD(4, 18)=GCD(8, 18)=GCD(10, 18)=GCD(14, 18)=GCD(16, 18)=2 |

| 18 | $g^1$, $g^5$, $g^7$, $g^{11}$, $g^{13}$, $g^{17}$ | GCD(1, 18)=GCD(5, 18)=GCD(7, 18)=GCD(11, 18)=GCD(13, 18)=GCD(17, 18)=1 |

We have 18 permutations for rotation and lets name cycle 1 with $f_1$, cycle 2 with $f_2$ .. cycle n with $f_n$

Than the formula for Cycling index is:

$$\frac{f_1^{18} + f_2^9 + 2f_3^6 + 2f_6^3 + 6f_9^2 + 6f_{18}^1}{18}$$

If we solve all the possible necklaces with three colors the result should be (for the moment we do not solve for the three colors with 4, 6 and 8 beads in respective groups):

$$\frac{3^{18} + 3^9 + 2*3^6 + 2*3^3 + 6*3^2 + 6*3^1}{18} = \text{21 524 542}$$

From here because turn around is allowed we need to add and the necklace(bracelet if we follow the right terms) is with even beads we should add the symethric turn arounds.

$$\frac{f_1^{18} + f_2^9 + 2f_3^6 + 2f_6^3 + 6f_9^2 + 6f_{18}^1 + 9f_1^2f_2^8 + 9f_2^9}{2 * 18}$$

and again for three colors without including the different weight:

$$\frac{3^{18} + 3^9 + 2*3^6 + 2*3^3 + 6*3^2 + 6*3^1 + 9 * 3^8 + 9 * 3^9}{2 * 18} = \text{10 781 954}$$

For the moment we have all the possible necklaces and bracelets with three colors. However, in order to find the necklaces and bracelets with three colors (4 reds, 6 greens and 8 blues) we need to replace:

$$f_1 = (x + y + z)$$

$$f_2 = (x^2 + y^2 + z^2)$$

$$f_3 = (x^3 + y^3 + z^3)$$

$$f_6 = (x^6 + y^6 + z^6)$$

$$f_9 = (x^9 + y^9 + z^9)$$

$$f_{18} = (x^{18} + y^{18} + z^{18})$$

and if we replace in the formula it becomes:

$$\frac{(x + y + z)^{18} + (x^2 + y^2 + z^2)^9 + 2(x^3 + y^3 + z^3)^6 + 2(x^6 + y^6 + z^6)^3 + 6(x^9 + y^9 + z^9)^2 + 6(x^{18} + y^{18} + z^{18}) + 9(x + y + z)^2(x^2 + y^2 + z^2)^8 + 9(x^2 + y^2 + z^2)^9}{36}$$

Then we need to find which expressions can expand to $x^4y^6z^8$.

After then by using multinominal coeficient I managed to calculate the following results

9 189 180

1260

11 340

11 340

Then I sum all of them and divide them to 36. This gives me the answer of 255 920 which is the answer of the question. We can create 255 920 bracelets with 4 red 6 green and 8 blue beads.

$\endgroup$

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.