|
|
A129526
|
|
Number of n-bead two-color bracelets with 00 prohibited.
|
|
4
|
|
|
2, 2, 3, 3, 5, 5, 8, 9, 14, 16, 26, 31, 49, 64, 99, 133, 209, 291, 455, 657, 1022, 1510, 2359, 3545, 5536, 8442, 13201, 20319, 31836, 49353, 77436, 120711, 189674, 296854, 467160, 733363, 1155647, 1818594, 2869378, 4524081, 7146483
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
COMMENTS
|
Bracelets can be turned over; turning the seventh example gives a different necklace but the same bracelet.
a(n) is also the number of inequivalent compositions of n into parts 1 and 2 where two compositions are considered equivalent if one can be obtained from the other by a cyclic rotation and/or reversing of the summands. a(7) = 5 because we have: 2+2+2+1, 2+2+1+1+1, 2+1+2+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1. - Geoffrey Critzer, Feb 01 2014
a(n) is also the average of sequence A000358(n) and Fib(floor(n/2)+2). The expression (1+x)*(1+x^2)/(1-x^2-x^4) (due to H. Kociemba) is the g.f. of Fib(floor(n/2)+2). Even though the offset of a(n) is set at n = 2, the formula is true even for n=1 because a(1) = 1 = (1+1)/2 (since the sequence 1 on a circle does not allow the pattern 00 when it is allowed to wrap around itself on the circle, while the sequence 0 does). - Petros Hadjicostas, Jan 04 2017
|
|
LINKS
|
|
|
FORMULA
|
G.f.: [Sum_{n>=1} phi(n)*log(1- x^n*(1+x^n))/n + ((1+x)*(1+x^2))/(-1+x^2+x^4)]/(-2). - Herbert Kociemba, Dec 04 2016
a(n) = [Fib(floor(n/2)+2)+(1/n) * sum_{d divides n} phi(n/d)*(Fib(d-1)+Fib(d+1))]/2. - Petros Hadjicostas, Jan 04 2017 (with help from Lingyun Zhang).
|
|
EXAMPLE
|
a(9) = 9 because of 111111111, 011111111, 010111111, 011011111, 011101111, 010101111, 010110111, 011011011, 010101011.
|
|
MATHEMATICA
|
nn=48; Drop[Map[Total, Transpose[Map[PadRight[#, nn]&, Table[CoefficientList[Series[CycleIndex[DihedralGroup[n], s]/.Table[s[i]->x^i+x^(2i), {i, 1, n}], {x, 0, nn}], x], {n, 0, nn}]]]], 2] (* Geoffrey Critzer, Feb 01 2014 *)
mx:=50; CoefficientList[Series[(Sum[(EulerPhi[n] Log[1- x^n (1+x^n)])/n, {n, 1, mx}]+((1+x) (1+x^2))/(-1+x^2+x^4))/(-2), {x, 0, mx}], x] (* Herbert Kociemba, Dec 04 2016 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(10) corrected and added more terms (from a(14) inclusive) by Washington Bomfim, Aug 24 2008
|
|
STATUS
|
approved
|
|
|
|