1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ For clarification, you say "Each bracelet has to contain exactly one bead of an unique color, X, that is not used in the other beads"... Clearly you allow 100000 to be a valid necklace. What about 120000? In 120000, we have multiple beads appearing as the only unique bead of their color, so which was "$X$" in 120000? 1? 2? If it is allowed, we need to be careful not to count X20000 where X=1 differently than X00001 where X=2. $\endgroup$ – JMoravitz Sep 17 '18 at 19:14
  • $\begingroup$ Thanks for trying to clarify my problem. In this problem, X is a not a variable. It is a specific color, X. So for all bracelets, there needs to be one and only one X bead. $\endgroup$ – Jaie Tang Sep 17 '18 at 19:18
  • 1
    $\begingroup$ I don't follow. Are you saying for example if we were to name our colors that our ordinary beads are all ten mundane colors, say (brown, blue, purple, green,...) and our bead of color X is always gold, and so we can always in every instance tell at sight which bead was color X without confusion? $\endgroup$ – JMoravitz Sep 17 '18 at 19:21
  • $\begingroup$ Yeah that's what I mean. X = gold, and 0-9 = (brown, blue, purple, green,...) $\endgroup$ – Jaie Tang Sep 17 '18 at 19:22
  • 1
    $\begingroup$ Alright, on to my second question for clarification. X00000 you say is the same as 0X0000 and 00X000 etc... (i.e. rotations of bracelets are considered equivalent). How about reflections? Is X11222 the same or different than X22211? (if you take off your braclet and flip it upsidedown before putting it back on again) $\endgroup$ – JMoravitz Sep 17 '18 at 19:24
3
$\begingroup$

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.

$\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.