Unique bracelets from 6 beads, where 1 bead is a fixed color

combinationscombinatoricsnecklace-and-bracelets

I'm trying to calculate the number of unique bracelets of length $6$ that can be made from $11$ differently colored beads.

However there is one important key detail! Each bracelet has to contain exactly one bead of an unique color, $X$ (e.g. gold), that is not used in the other beads. The remaining $5$ other beads can have any of the $10$ differently colored beads ($0$-$9$ (e.g. blue, brown, grey, white, etc…) can be repeated and used as many times as possible as the length permits.

Therefore the beads generated would be include for example:

  • $X00000$
  • $X00001$
  • $0X0001$
  • $00X001$
  • $X00002$
  • …etc

My initial attempt:

I reasoned that this bracelet problem can actually be solved through calculating necklaces.

  1. Calculating the number of necklaces for $n=5$, $k=10$ yields $20008$ unique necklaces starting from:

    • $00000$
    • $00001$
    • $00002$
    • etc.
  2. Then to generate unique bracelets from these necklaces, I have three options to place the $X$ bead for each .

    • Ex.

    • Original Necklace = $00001$

    • Unique Bracelets Generated = $X00001$, $0X0001$, $00X001$
  3. Then I would remove any non-unique bracelets. From my thoughts, the only duplicate bracelets would be those generated from necklaces with only a single color. For this example, I would remove $10$ (number of colors) * $2$ (duplicate sets) = $20$ bracelets.

    • Ex.
    • Original Necklace = $000000$
    • Unique Bracelets Generated = $X00000$
    • (not $0X0000$ or $00X000$ since they are the same as $X00000$)
  4. Therefore from this reasoning, I'm guessing my solution would be simply $20008*3 – 20$ unique bracelets = $60014$ bracelets.

My questions are:

  1. Is this a feasible or correct way of thinking about the problem?

  2. Is this the correct answer?

  3. Is there a better method to solve this problem?

Best Answer

We focus our attention on counting length 6 sequences with available entries $\{0,1,2,\dots,9,X\}$.

Simply fix the far left entry of the sequence to be $X$. As there is only ever the one entry with an $X$, this will allow us to treat all rotationally equivalent arrangements the same.

$X~\underline{~}~\underline{~}~\underline{~}~\underline{~}~\underline{~}$

Now... let us ignore the $X$ again and look solely at the five remaining positions. If we were not interested in worrying about reflective symmetry we would find that there are simply $10^5$ possible sequences that can be filled in these remaining positions. As we are concerning ourselves with reflective symmetry however, more care needs to be applied.

We ask ourselves, how many sequences of 5 digits exist unique up to reflection? To count this, we might say that every sequence was counted differently twice: once as $abcde$ and again as $edcba$, so we would have $\frac{10^5}{2}$ such unique sequences however this ignores palindromes.

So, to correct the count, let us first take our $10^5$ sequences, remove the $10^3$ palindromes, divide the result in half to remove duplicates, and then add back in the palindromes.

This gives us a total of $(10^5-10^3)\cdot\frac{1}{2}+10^3=50500$ unique up to reflection sequences of length five. Appending an $X$ at the front of each of these sequences gives us a unique up to reflection and unique up to rotation bracelet.


Side note: Since we were given that every bracelet has exactly one bead $X$, this made things considerably easier for us. We were always able to rotate any bracelet until our $X$ bead was at the far left. Further, when considering reflections, we only ever needed to consider reflecting across the axis containing $X$ since reflection across any other axis would move the $X$ bead from the "left half" to the "right half" of the bracelet or vice versa.


As for what went wrong with your attempt, there were many leaps in logic that I did not understand so I cannot pinpoint everything that you did wrong. One thing that stood out to me was your section:

Then to generate unique bracelets from these necklaces, I have three options to place the X bead for each. Ex. Original Necklace = 00001

Unique Bracelets Generated = X00001, 0X0001, 00X001

If we were to generate a necklace ahead of time and try to place our X bead within it, some will have 3 options for where to place X as in your example giving 3 bracelets formed from this necklace, but many others will not.

For example if your original necklace was 00000 then every place where you would insert X would result in the same bracelet giving only one bracelet formed from this necklace.

For another example if your original necklace was 12345 then every place where you would insert X would result in a different bracelet giving six different bracelets formed using this necklace.

Related Question