login
Number of n-bead two-color bracelets with 00 prohibited.
4

%I #59 Oct 09 2018 21:13:44

%S 2,2,3,3,5,5,8,9,14,16,26,31,49,64,99,133,209,291,455,657,1022,1510,

%T 2359,3545,5536,8442,13201,20319,31836,49353,77436,120711,189674,

%U 296854,467160,733363,1155647,1818594,2869378,4524081,7146483

%N Number of n-bead two-color bracelets with 00 prohibited.

%C Bracelets can be turned over; turning the seventh example gives a different necklace but the same bracelet.

%C 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

%C 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

%H Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar, Marko Petkovšek, <a href="http://arxiv.org/abs/1407.4962">Vertex and edge orbits of Fibonacci and Lucas cubes</a>, arXiv:1407.4962 [math.CO], 2014. See Table 4.

%H A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, et al., <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/Fib-Luc-orbits-August-11-2014.pdf">Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings</a>, 2014.

%H M. Assis, J. L. Jacobsen, I. Jensen, J.-M. Maillard and B. M. McCoy, <a href="http://arxiv.org/abs/1306.6389">Hard hexagon partition function for complex fugacity</a>, arXiv preprint arXiv:1306.6389 [math-ph], 2013.

%H M. Assis, J. L. Jacobsen, I. Jensen, J.-M. Maillard and B. M. McCoy, <a href="http://arxiv.org/abs/1406.5566">Integrability vs non-integrability: Hard hexagons and hard squares compared</a>, arXiv preprint 1406.5566 [math-ph], 2014.

%H C. J. Turner, A. A. Michailidis, D. A. Abanin, M. Serbyn, Z. Papić, <a href="https://arxiv.org/abs/1806.10933">Quantum scarred eigenstates in a Rydberg atom chain: entanglement, breakdown of thermalization, and stability to perturbations</a>, arXiv:1806.10933 [cond-mat.quant-gas], 2018.

%F 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

%F a(n) = [A000358(n)+Fib(floor(n/2)+2)]/2. - _Petros Hadjicostas_, Jan 04 2017

%F 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).

%e a(9) = 9 because of 111111111, 011111111, 010111111, 011011111, 011101111, 010101111, 010110111, 011011011, 010101011.

%t 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 *)

%t 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 *)

%Y Cf. A000358.

%K nonn

%O 2,1

%A _Colin Mallows_, May 29 2007

%E a(10) corrected and added more terms (from a(14) inclusive) by _Washington Bomfim_, Aug 24 2008