%I #142 Sep 23 2023 15:12:37
%S 1,2,2,3,3,5,5,8,10,15,19,31,41,64,94,143,211,329,493,766,1170,1811,
%T 2787,4341,6713,10462,16274,25415,39651,62075,97109,152288,238838,
%U 375167,589527,927555,1459961,2300348,3626242,5721045,9030451,14264309,22542397,35646312,56393862,89264835,141358275
%N Number of binary necklaces of length n with no subsequence 00, excluding the necklace "0".
%C a(n) is also the number of inequivalent compositions of n into parts 1 and 2 where two compositions are considered to be equivalent if one is a cyclic rotation of the other. a(6)=5 because we have: 2+2+2, 2+2+1+1, 2+1+2+1, 2+1+1+1+1, 1+1+1+1+1+1. - _Geoffrey Critzer_, Feb 01 2014
%C Moebius transform is A006206. - _Michael Somos_, Jun 02 2019
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 499.
%D T. Helleseth and A. Kholosha, Bent functions and their connections to combinatorics, in Surveys in Combinatorics 2013, edited by Simon R. Blackburn, Stefanie Gerke, Mark Wildon, Camb. Univ. Press, 2013.
%H Alois P. Heinz, <a href="/A000358/b000358.txt">Table of n, a(n) for n = 1..1000</a>
%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2009.02669">Symbolic dynamical scales: modes, orbitals, and transversals</a>, arXiv:2009.02669 [math.DS], 2020.
%H A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, and Marko Petkovsek, <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 A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, and Marko Petkovsek, <a href="https://doi.org/10.1007/s00026-016-0318-9">Vertex and Edge Orbits of Fibonacci and Lucas Cubes</a>, Ann. Comb. 20 (2016), 209-229.
%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 M. Assis, J. L. Jacobsen, I. Jensen, J.-M. Maillard, and B. M. McCoy, <a href="https://doi.org/10.1088/1751-8113/47/44/445001">Integrability versus non-integrability: Hard hexagons and hard squares compared</a>, J. Phys. A: Math. Theor. 47 (2014) 445001 (53pp.).
%H Daryl DeFord, <a href="https://www.fq.math.ca/Papers1/52-5/DeFord.pdf">Enumerating distinct chessboard tilings</a>, Fibonacci Quart. 52 (2014), 102-116; see formula (5.3) in Theorem 5.2, p. 111.
%H P. Flajolet and M. Soria, <a href="http://algo.inria.fr/flajolet/Publications/cycle2.ps.gz">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H P. Flajolet and M. Soria, <a href="http://dx.doi.org/10.1137/0404006">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H Benjamin Hackl and Helmut Prodinger, <a href="https://arxiv.org/abs/1801.09934">The Necklace Process: A Generating Function Approach</a>, arXiv:1801.09934 [math.PR], 2018. [The paper mentions this sequence, but the authors mean sequence A032190(n) = a(n) - 1.]
%H Benjamin Hackl and Helmut Prodinger, <a href="https://doi.org/10.1016/j.spl.2018.06.010">The Necklace Process: A Generating Function Approach</a>, Statistics and Probability Letters 142 (2018), 57-61. [The paper mentions this sequence, but the authors mean sequence A032190(n) = a(n) - 1.]
%H P. Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence</a>, J. Integer Sequences 19 (2016), #16.8.2.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=119">Encyclopedia of Combinatorial Structures 119</a>
%H Tom Roby, <a href="http://www.math.uwaterloo.ca/~opecheni/alcoveRobyDACtalk.pdf">Dynamical algebraic combinatorics and homomesy: An action-packed introduction</a>, AlCoVE: an Algebraic Combinatorics Virtual Expedition (2020).
%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H C. J. Turner, A. A. Michailidis, D. A. Abanin, M. Serbyn, and 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.
%H L. Zhang and P. Hadjicostas, <a href="http://appliedprobability.org/data/files/TMS%20articles/40_2_3.pdf">On sequences of independent Bernoulli trials avoiding the pattern '11..1'</a>, Math. Scientist, 40 (2015), 89-96.
%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F a(n) = (1/n) * Sum_{ d divides n } totient(n/d) [ Fib(d-1)+Fib(d+1) ].
%F G.f.: Sum_{k>=1} phi(k)/k * log( 1/(1-B(x^k)) ) where B(x)=x*(1+x). - _Joerg Arndt_, Aug 06 2012
%F a(n) ~ ((1+sqrt(5))/2)^n / n. - _Vaclav Kotesovec_, Sep 12 2014
%F a(n) = Sum_{0 <= i <= ceiling((n-1)/2)} [ (1/(n - i)) * Sum_{d|gcd(i, n-i)} phi(d) * binomial((n - i)/d, i/d) ]. (This is DeFord's formula for the number of distinct Lucas tilings of a 1 X n bracelet up to symmetry, even though in the paper he refers to sequence A032192(n) = a(n) - 1.) - _Petros Hadjicostas_, Jun 07 2019
%e G.f. = x + 2*x^2 + 2*x^3 + 3*x^4 + 3*x^5 + 5*x^6 + 5*x^7 + 8*x^8 + 10*x^9 + ... - _Michael Somos_, Jun 02 2019
%e Binary necklaces are: 1; 01, 11; 011, 111; 0101, 0111, 1111; 01010, 01011, 01111. - _Michael Somos_, Jun 02 2019
%p A000358 := proc(n) local sum; sum := 0; for d in divisors(n) do sum := sum + phi(n/d)*(fibonacci(d+1)+fibonacci(d-1)) od; RETURN(sum/n); end;
%p with(combstruct); spec := {A=Union(zero,Cycle(one),Cycle(Prod(zero,Sequence(one,card>0)))),one=Atom,zero=Atom}; seq(count([A,spec,unlabeled],size=i),i=1..30);
%t nn=48;Drop[Map[Total,Transpose[Map[PadRight[#,nn]&,Table[ CoefficientList[ Series[CycleIndex[CyclicGroup[n],s]/.Table[s[i]->x^i+x^(2i),{i,1,n}],{x,0,nn}],x],{n,0,nn}]]]],1] (* _Geoffrey Critzer_, Feb 01 2014 *)
%t max = 50; B[x_] := x*(1+x); A = Sum[EulerPhi[k]/k*Log[1/(1-B[x^k])], {k, 1, max}]/x + O[x]^max; CoefficientList[A, x] (* _Jean-François Alcover_, Feb 08 2016, after _Joerg Arndt_ *)
%t Table[1/n * Sum[EulerPhi[n/d] Total@ Map[Fibonacci, d + # & /@ {-1, 1}], {d, Divisors@ n}], {n, 47}] (* _Michael De Vlieger_, Dec 28 2016 *)
%t a[ n_] := If[ n < 1, 0, DivisorSum[n, EulerPhi[n/#] LucasL[#] &]/n]; (* _Michael Somos_, Jun 02 2019 *)
%o (PARI)
%o N=66; x='x+O('x^N);
%o B(x)=x*(1+x);
%o A=sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k))));
%o Vec(A)
%o /* _Joerg Arndt_, Aug 06 2012 */
%o (PARI) {a(n) = if( n<1, 0, sumdiv(n, d, eulerphi(n/d) * (fibonacci(d+1) + fibonacci(d-1)))/n)}; /* _Michael Somos_, Jun 02 2019 */
%o (Python)
%o from sympy import totient, lucas, divisors
%o def A000358(n): return (n&1^1)+sum(totient(n//k)*(lucas(k)-((k&1^1)<<1)) for k in divisors(n,generator=True))//n # _Chai Wah Wu_, Sep 23 2023
%Y Cf. A006206, A032190, A093305, A280218, A280218.
%Y Column k=0 of A320341.
%K nonn,easy
%O 1,2
%A _Frank Ruskey_