cp's OEIS Frontend

A000358 Number of binary necklaces of length n with no subsequence 00, excluding the necklace "0".

%I A000358 #143 Jan 05 2025 19:51:31
%S A000358 1,2,2,3,3,5,5,8,10,15,19,31,41,64,94,143,211,329,493,766,1170,1811,
%T A000358 2787,4341,6713,10462,16274,25415,39651,62075,97109,152288,238838,
%U A000358 375167,589527,927555,1459961,2300348,3626242,5721045,9030451,14264309,22542397,35646312,56393862,89264835,141358275
%N A000358 Number of binary necklaces of length n with no subsequence 00, excluding the necklace "0".
%C A000358 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 A000358 Moebius transform is A006206. - _Michael Somos_, Jun 02 2019
%D A000358 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 499.
%D A000358 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 A000358 Alois P. Heinz, <a href="/A000358/b000358.txt">Table of n, a(n) for n = 1..1000</a>
%H A000358 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 A000358 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 A000358 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 A000358 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 A000358 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 A000358 Daryl DeFord, <a href="https://web.archive.org/web/2024*/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 A000358 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 A000358 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 A000358 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 A000358 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 A000358 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 A000358 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=119">Encyclopedia of Combinatorial Structures 119</a>
%H A000358 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 A000358 F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A000358 F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H A000358 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 A000358 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 A000358 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A000358 a(n) = (1/n) * Sum_{ d divides n } totient(n/d) [ Fib(d-1)+Fib(d+1) ].
%F A000358 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 A000358 a(n) ~ ((1+sqrt(5))/2)^n / n. - _Vaclav Kotesovec_, Sep 12 2014
%F A000358 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 A000358 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 A000358 Binary necklaces are: 1; 01, 11; 011, 111; 0101, 0111, 1111; 01010, 01011, 01111. - _Michael Somos_, Jun 02 2019
%p A000358 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 A000358 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 A000358 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 A000358 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 A000358 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 A000358 a[ n_] := If[ n < 1, 0, DivisorSum[n, EulerPhi[n/#] LucasL[#] &]/n]; (* _Michael Somos_, Jun 02 2019 *)
%o A000358 (PARI)
%o A000358 N=66;  x='x+O('x^N);
%o A000358 B(x)=x*(1+x);
%o A000358 A=sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k))));
%o A000358 Vec(A)
%o A000358 /* _Joerg Arndt_, Aug 06 2012 */
%o A000358 (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 A000358 (Python)
%o A000358 from sympy import totient, lucas, divisors
%o A000358 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 A000358 Cf. A006206, A032190, A093305, A280218, A280218.
%Y A000358 Column k=0 of A320341.
%K A000358 nonn,easy
%O A000358 1,2
%A A000358 _Frank Ruskey_