k-ary bracelets with conserved/fixed indexes

123 Views Asked by At

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

1

There are 1 best solutions below

8
On

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