2
$\begingroup$

Im using the formula from here:

https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_bracelets

to calculate the number of unique bracelets, accepting all rotation/mirroring as identical, for a given length n with a given character set of length k

One thing this formula doesnt include, and I cant work out how to add, is what if c number of positions within n have a fixed value? Eg if k = [A, B, C, D, E] and n = 5, how would the bracelet formula be updated to indicate the maximum number of unique bracelets possible with the character "A" (or any other of the characters from set k) fixed at 1 position?

edit perhaps this doesnt exactly make sense, since all rotation/translation is considered equivalent, but what im saying is that the function that creates these bracelets will always put "A" into the first index, and then randomly assign characters from k to all other indexs of n

initially i thought i could just do n-c (c being the number of fixed points), but this is incorrect, it appears the number of unique bracelets that can be generated for n with c=1 is more than n-1

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Your edited question effectively says that you want to count the bracelets that contain at least one 'A'. This is the number of bracelets that you can form with $k$ letters minus the number of bracelets that you can form with the $k-1$ letters excluding 'A'; in the notation of the Wikipedia article: $B_k(n)-B_{k-1}(n)$.

$\endgroup$
8
  • $\begingroup$ Would this hold true if the fixed A was in any position of the bracelets? What about if multiple A's were in fixed positions? Or if some of the fixed characters were Bs or Cs? Would it just be $B_k(n)-B_{k-c}(n)$ - with $c$ being the number of fixed positions? $\endgroup$
    – Matthew
    Aug 30, 2018 at 3:59
  • $\begingroup$ Eg if $n$ was 5, $k$ contained $[A, B, C, D]$, and position 1 was fixed to A and position 4 was fixed to B, would it simply be $B_4(5)-B_{3}(5)$? $\endgroup$
    – Matthew
    Aug 30, 2018 at 4:01
  • $\begingroup$ OK I ran some tests and it appears that if im only fixing one of the characters from $k$, then $B_k(n)-B_{k-c}(n)$, with $c$ being any number of the same fixed character, then that does indeed tell me the correct number of unique bracelets possible. However, if i fix several different characters, then that formula is no longer accurate, I end up getting more unique bracelets than it would seem to indicate $\endgroup$
    – Matthew
    Aug 30, 2018 at 4:35
  • $\begingroup$ @MatthewPrasinov: I'm not sure I'm following you. If you fix more characters, you should have fewer, not more bracelets; whereas in $B_k(n)-B_{k-c}(n)$, the greater $c$, i.e. the more characters you fix, the less you're subtracting, i.e. the more you're leaving, until for $c=k$ you're not subtracting anything and just ending up with $B_k(n)$, which surely can't be right? $\endgroup$
    – joriki
    Aug 30, 2018 at 5:47
  • $\begingroup$ @MatthewPrasinov: I also don't understand your question "Would this hold true if the fixed A was in any position of the bracelets?". I don't see how you intend to distinguish between the positions. The whole point of necklaces and bracelets is that there's no distinction between the positions. If you're talking about the generating process again, as in the edited question,then yes, since we don't distinguish between the positions, it's irrelevant whether the generating process spuriously does. $\endgroup$
    – joriki
    Aug 30, 2018 at 5:50

You must log in to answer this question.

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