4
$\begingroup$

How many number of bracelets of length $n$ with black-white beads?

I'm trying to find a formula for counting the number of such bracelets. What i've done so far is to think of the bracelets as binary strings with periods. I've noted that the total number of length $n$ bracelets is $2^n$ and that $2^n=\displaystyle\sum_{d|n}B_d$, where $B_d$ is a bracelet with period $d$. By Mobius Inversion, I have that $B_n=\displaystyle \sum_{d|n}\mu(n/d)2^d$. So $c_n= \displaystyle \frac{1}{n}\sum_{d|n}\mu(n/d)2^d$ gives the number. But when I test it for $n=5$, I get $c_5=6$ when i'm expecting $8$. (i.e. $00000,00001,00011,01001,00111,01101,01111,11111$ as distinct necklaces).

$\endgroup$
  • $\begingroup$ Can you please explain what counts as a bracelet? $\endgroup$ – Bram28 Mar 15 '18 at 2:40
  • $\begingroup$ @Bram28 I am trying to describe it as a binary string with $m$ 1's and $n-m$ 0's and two bracelets are the same if I can obtain the other by shifting like $101=110$ $\endgroup$ – user265675 Mar 15 '18 at 2:43
  • $\begingroup$ Do you treat bracelets and necklaces as the same? Does this question help? What exact numerical calculations are you doing when you attempted the calculation for $n=5$? $\endgroup$ – JMoravitz Mar 15 '18 at 2:47
  • $\begingroup$ It seems like you're double counting. If you have a bracelet with 8 black beads, don't you also count it as bracelet with 4 black beads, 2 black beads and 1 black bead? $\endgroup$ – saulspatz Mar 15 '18 at 2:55
  • $\begingroup$ This is oeis.org/A000031 $\endgroup$ – Dan Uznanski Jun 5 '19 at 16:07
5
$\begingroup$

To avoid possible double counting and similar problems it is useful to reduce all sequences equivalent by cyclic permutation to a "primitive form". From all identical (by rotation) sequences the smallest one (if considered as a binary number) is chosen as the primitive form. Another requirement imposed onto the primitive form is that it cannot be reduced to repeated sequence of a smaller length (for example $0101$ is not primitive because it can be reduced to two $01$).

As an illustration the primitive sequences of length 4 are: $$ 0001,0011,0111. $$

Let $A_n$ be the number of primitive sequences of length $n$. Each of the sequences can be cyclically shifted by up to $(n-1)$ bits to obtain a new unique arrangement. By construction no primitive sequence can be obtained from itself or from another one by such a cyclic shift. Thus we have: $$ 2^n=\sum_{d|n}d A_d. $$

By Möbius inversion one obtains: $$ A_n=\frac{1}{n}\sum_{d|n}\mu\left(\frac{n}{d}\right)2^d. $$ This is however not yet the number we are looking for. So far only the primitive sequences of length $n$ were counted. To obtain the number of all sequences of length $n$ the primitive sequences of smaller lengths dividing $n$ (periodically completed to the length $n$) shall be added: $$ C_n=\sum_{d|n}A_d=\sum_{d|n}\frac{1}{d}\sum_{t|d}\mu\left(\frac{d}{t}\right)2^t=\frac1n\sum_{d|n}\varphi\left(\frac{n}{d}\right)2^d, $$ where $\varphi(n)$ is the Euler's totient function.

Referred to your example: $$ C_5=A_1+A_5=2+6=8. $$ By inspection $A_1=2$ counts the sequences $00000$ and $11111$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy