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

1, 2, 2, 3, 3, 5, 5, 8, 10, 15, 19, 31, 41, 64, 94, 143, 211, 329, 493, 766, 1170, 1811, 2787, 4341, 6713, 10462, 16274, 25415, 39651, 62075, 97109, 152288, 238838, 375167, 589527, 927555, 1459961, 2300348, 3626242, 5721045, 9030451, 14264309, 22542397, 35646312, 56393862, 89264835, 141358275

Offset: 1

Author

Frank Ruskey

Keywords

• nonn
• easy

Comments

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

Moebius transform is A006206. - Michael Somos, Jun 02 2019

Examples

			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
Binary necklaces are: 1; 01, 11; 011, 111; 0101, 0111, 1111; 01010, 01011, 01111. - _Michael Somos_, Jun 02 2019
		

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 499.
• 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.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
• A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, and Marko Petkovsek, Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings, 2014.
• A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, and Marko Petkovsek, Vertex and Edge Orbits of Fibonacci and Lucas Cubes, Ann. Comb. 20 (2016), 209-229.
• M. Assis, J. L. Jacobsen, I. Jensen, J.-M. Maillard, and B. M. McCoy, Integrability vs non-integrability: Hard hexagons and hard squares compared, arXiv preprint 1406.5566 [math-ph], 2014.
• M. Assis, J. L. Jacobsen, I. Jensen, J.-M. Maillard, and B. M. McCoy, Integrability versus non-integrability: Hard hexagons and hard squares compared, J. Phys. A: Math. Theor. 47 (2014) 445001 (53pp.).
• Daryl DeFord, Enumerating distinct chessboard tilings, Fibonacci Quart. 52 (2014), 102-116; see formula (5.3) in Theorem 5.2, p. 111.
• P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
• P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
• Benjamin Hackl and Helmut Prodinger, The Necklace Process: A Generating Function Approach, arXiv:1801.09934 [math.PR], 2018. [The paper mentions this sequence, but the authors mean sequence A032190(n) = a(n) - 1.]
• Benjamin Hackl and Helmut Prodinger, The Necklace Process: A Generating Function Approach, Statistics and Probability Letters 142 (2018), 57-61. [The paper mentions this sequence, but the authors mean sequence A032190(n) = a(n) - 1.]
• P. Hadjicostas, Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence, J. Integer Sequences 19 (2016), #16.8.2.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 119
• Tom Roby, Dynamical algebraic combinatorics and homomesy: An action-packed introduction, AlCoVE: an Algebraic Combinatorics Virtual Expedition (2020).
• F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
• F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
• C. J. Turner, A. A. Michailidis, D. A. Abanin, M. Serbyn, and Z. Papić, Quantum scarred eigenstates in a Rydberg atom chain: entanglement, breakdown of thermalization, and stability to perturbations, arXiv:1806.10933 [cond-mat.quant-gas], 2018.
• L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.
• Index entries for sequences related to necklaces

Crossrefs

Cf. A006206, A032190, A093305, A280218, A280218.

Column k=0 of A320341.

Programs

Maple

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;
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);

Mathematica

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 *)
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 *)
Table[1/n * Sum[EulerPhi[n/d] Total@ Map[Fibonacci, d + # & /@ {-1, 1}], {d, Divisors@ n}], {n, 47}] (* Michael De Vlieger, Dec 28 2016 *)
a[ n_] := If[ n < 1, 0, DivisorSum[n, EulerPhi[n/#] LucasL[#] &]/n]; (* Michael Somos, Jun 02 2019 *)

PARI

N=66;  x='x+O('x^N);
B(x)=x*(1+x);
A=sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k))));
Vec(A)
/* Joerg Arndt, Aug 06 2012 */

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 */

Python

from sympy import totient, lucas, divisors
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

Formula

a(n) = (1/n) * Sum_{ d divides n } totient(n/d) [ Fib(d-1)+Fib(d+1) ].

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

a(n) ~ ((1+sqrt(5))/2)^n / n. - Vaclav Kotesovec, Sep 12 2014

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