A circular necklace contains n beads. Each bead is black or white. How many different necklaces can be made with n beads?

There is no clasp to identify a specific point on the chain, and a flipped over necklace is still the same necklace.
_____________________________

To get you started:

With 1 bead, the necklace can be either 1 black or 1 white bead.

With 2 beads, the necklace can be either 2 black, 2 white, or 1 black-1 white

With 3 beads, the necklace can be either 3 black, 3 white, 2 black-1 white, 2 white-1 black, etc...

# Beads  Number of Necklaces
   1          2
   2          3
   3          4
   4          6
   5          8
   6         13

The derivation of a solution is beyond me.  Apparently mathematicians have figured this out, so an internet search helps.

Fortunately, SK has provided a list of the first few and so this can be treated like a Sequences problem, and a search of the online handbook of integer sequences (http://www.research.att.com/~njas/sequences/) brings up a formula involving the Euler Phi function.  PlanetMath.org/encyclopedia has an article on the Euler Phi function that aids in its calculation.

The formula for the sequence as given in the online handbook is
Sum_{ d divides n } phi(d)*2^(n/d)/(2*n) + either 2^((n-1)/2) if n odd
              or 2^(n/2-1)+2^(n/2-2) if n even.

And the formula for the phi function of d is

 d * Product{all primes p that divide d} (1 - 1/p)

so for example phi(2000) = 2000 * (1-1/2) * (1-1/5) = 800.

The following program implements these algorithms:

 1000   for N=1 to 47
 1010    Tot=0
 1020    for D=1 to N
 1030       if N@D=0 then
 1040         :Tot=Tot+fnPhi(D)*2^(N//D)//(2*N)
 1050    next
 1060    if N@2=0 then
 1070      :Tot=Tot+2^(N//2-1)+2^(N//2-2)
 1080     :else
 1090      :Tot=Tot+2^((N-1)//2)
 1100    print N,Tot
 1110   next
 1999   end
 2000   ' Phi function defined ----
 2010   fnPhi(X)
 2020   local Temp,Dvsr,Answ,Lmt
 2030   Temp=X:Lmt=(X)
 2040   Answ=X
 2050   Dvsr=1
 2060   while Dvsr<Lmt
 2070    Dvsr=nxtprm(Dvsr)
 2080    if Temp@Dvsr=0 then
 2090      :Answ=Answ*(Dvsr-1)//Dvsr
 2100      :while Temp@Dvsr=0
 2110         :Temp=Temp//Dvsr
 2120      :wend
 2140   wend
 2150   return(Answ)

which leads to

 1       2
 2       3
 3       4
 4       6
 5       8
 6       13
 7       18
 8       30
 9       46
 10      78
 11      126
 12      224
 13      380
 14      687
 15      1224
 16      2250
 17      4112
 18      7685
 19      14310
 20      27012
 21      50964
 22      96909
 23      184410
 24      352698
 25      675188
 26      1296858
 27      2493726
 28      4806078
 29      9272780
 30      17920860
 31      34669602
 32      67159050
 33      130216124
 34      252745368
 35      490984488
 36      954637558
 37      1857545300
 38      3617214681
 39      7048675960
 40      13744694928
 41      26818405352
 42      52359294790
 43      102282248574
 44      199914398490
 45      390941662712
 46      764884036743
 47      1497215711538

and this continues as:

 48      2932043766538
 49      5744404057034
 50      11259024569838
 51      22076502318624
 52      43303893547956
 53      84973644983780
 54      166800088109829
 55      327534652572024
 56      643371579062292
 57      1264168584899532
 58      2484745029278898
 59      4885261149611790
 60      9607680019329456
 61      18900353608280300
 62      37191017905571379
 63      73201367519380268
 64      144115191330636810
 65      283796066967422192
 66      558992251165454994
 67      1101298162244236182
 68      2170205198153526576
 69      4277505889344524468
 70      8432797316853883164
 71      16628051030379615882
 72      32794211738611821312
 73      64689951888851602952
 74      127631526668052321918
 75      251859545890487146472
 76      497091208931087393202
 77      981270957754284704684
 78      1937381121593132140708
 79      3825714619583392442706
 80      7555786373422938025200
 81      14925010119798638898462
 82      29485995602019485259228
 83      58261485284831754566694
 84      115135792347575114543648
 85      227562507225975302929472
 86      449832863119068367872573
 87      889324740874730204724120
 88      1758437555816391076574364
 89      3477359660931581722277912
 90      6877444662723140842510068
 91      13603736695478923656694872
 92      26911739984517947581815054
 93      53244732872559842956478532
 94      105356599088223771924108747

and in each instance each successive value is almost twice the preceding value, the more so as the numbers get larger.

Posted by Charlie on 2004-08-18 15:04:00