login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Number of aperiodic binary necklaces of length n with no subsequence 00, excluding the necklace "0".
(Formerly M0317)
29

%I M0317 #114 Jan 05 2025 19:51:33

%S 1,1,1,1,2,2,4,5,8,11,18,25,40,58,90,135,210,316,492,750,1164,1791,

%T 2786,4305,6710,10420,16264,25350,39650,61967,97108,152145,238818,

%U 374955,589520,927200,1459960,2299854,3626200,5720274,9030450,14263078

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

%C Bau-Sen Du (1985/1989)'s Table 1 has this sequence, denoted A_{n,1}, as the second column. - _Jonathan Vos Post_, Jun 18 2007

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 499.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H James Spahlinger, <a href="/A006206/b006206.txt">Table of n, a(n) for n = 1..5000</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 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 710.

%H Kam Cheong Au, <a href="https://arxiv.org/abs/2007.03957">Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series</a>, arXiv:2007.03957 [math.NT], 2020. See 2nd line of Table 1 (p. 6).

%H Michael Baake, Joachim Hermisson, and Peter Pleasants, <a href="http://dx.doi.org/10.1088/0305-4470/30/9/016">The torus parametrization of quasiperiodic LI-classes</a>, J. Phys. A 30(9) (1997), 3029-3056.

%H Latham Boyle and Paul J. Steinhardt, <a href="https://arxiv.org/abs/1608.08220">Self-Similar One-Dimensional Quasilattices</a>, arXiv:1608.08220 [math-ph], 2016.

%H D. J. Broadhurst, <a href="http://arXiv.org/abs/hep-th/9604128">On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory</a>, arXiv:hep-th/9604128, 1996.

%H D. J. Broadhurst and D. Kreimer, <a href="http://arXiv.org/abs/hep-th/9609128">Association of multiple zeta values with positive knots via Feynman diagrams up to 9 loops</a>, arXiv:hep-th/9609128, 1996.

%H D. J. Broadhurst and D. Kreimer, <a href="https://doi.org/10.1016/S0370-2693(96)01623-1">Association of multiple zeta values with positive knots via Feynman diagrams up to 9 loops</a>, Phys. Lett B., 393 (1997), 403-412.

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. 3 (2000), #00.1.5.

%H M. Conder, S. Du, R. Nedela, and M. Skoviera, <a href="https://doi.org/10.1007/s10801-016-0692-8">Regular maps with nilpotent automorphism group</a>, Journal of Algebraic Combinatorics, 44(4) (2016), 863-874. ["... We note that the sequence h_n above agrees in all but the first term with the sequence A006206 in ..."]

%H Bau-Sen Du, <a href="https://doi.org/10.1017/S0004972700002306">The Minimal Number of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem</a>, Bull. Austral. Math. Soc. 31 (1985), 89-103. <a href="https://doi.org/10.1017/S0004972700009837">Corrigendum</a>: 32 (1985), 159.

%H Bau-Sen Du, <a href="http://arXiv.org/abs/0706.2297">The Minimal Number of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem</a>, arXiv:0706.2297 [math.DS], 2007.

%H Bau-Sen Du, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/27-2/du.pdf">A Simple Method Which Generates Infinitely Many Congruence Identities</a>, Fib. Quart. 27 (1989), 116-124.

%H Bau-Sen Du, <a href="http://arXiv.org/abs/0706.2421">A Simple Method Which Generates Infinitely Many Congruence Identities</a>, arXiv:0706.2421 [math.NT], 2007.

%H Larry Ericksen, <a href="http://siauliaims.su.lt/index.php?option=com_content&amp;view=article&amp;id=44&amp;Itemid=9">Primality Testing and Prime Constellations</a>, Šiauliai Mathematical Seminar, 3(11), 2008; mentions this sequence.

%H R. J. Mathar, <a href="http://arxiv.org/abs/0903.2514">Hardy-Littlewood constants embedded into infinite products over all positive integers</a>, arXiv:0903.2514 [math.NT], 2009-2011; sequence gamma_{1,j}^(A).

%H A. Pakapongpun and T. Ward, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ward/ward17.html">Functorial Orbit counting</a>, J. Integer Seqs. 12 (2009), #09.2.4; example 21.

%H Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs. 4 (2001), #01.2.1.

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>

%F Euler transform is Fibonacci(n+1): 1/((1 - x) * (1 - x^2) * (1 - x^3) * (1 - x^4) * (1 - x^5)^2 * (1 - x^6)^2 * ...) = 1/(Product_{n >= 1} (1 - x^n)^a(n)) = 1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 8*x^5 + ...

%F Coefficients of power series of natural logarithm of the infinite product Product_{n>=1} (1 - x^n - x^(2*n))^(-mu(n)/n), where mu(n) is the Moebius function. This is related to Fibonacci sequence since 1/(1 - x^n - x^(2*n)) expands to a power series whose terms are Fibonacci numbers.

%F a(n) = (1/n) * Sum_{d|n} mu(n/d) * (Fibonacci(d-1) + Fibonacci(d+1)) = (1/n) * Sum_{d|n} mu(n/d) * Lucas(d). Hence Lucas(n) = Sum_{d|n} d*a(d).

%F a(n) = round((1/n) * Sum_{d|n} mu(d)*phi^(n/d)), n > 2. - _David Broadhurst_ [Formula corrected by _Jason Yuen_, Dec 29 2024]

%F G.f.: Sum_{n >= 1} -mu(n) * log(1 - x^n - x^(2*n))/n.

%F a(n) = (1/n) * Sum_{d|n} mu(d) * A001610(n/d - 1), n > 1. - _R. J. Mathar_, Mar 07 2009

%F For n > 2, a(n) = A060280(n) = A031367(n)/n.

%e Necklaces are: 1, 10, 110, 1110; 11110, 11010, 111110, 111010, ...

%p with(numtheory): with(combinat):

%p A006206 := proc(n) local sum; sum := 0; for d in divisors(n) do sum := sum + mobius(n/d)*(fibonacci(d+1)+fibonacci(d-1)) end do; sum/n; end proc:

%t a[n_] := Total[(MoebiusMu[n/#]*(Fibonacci[#+1] + Fibonacci[#-1]) & ) /@ Divisors[n]]/n;

%t (* or *) a[n_] := Sum[LucasL[k]*MoebiusMu[n/k], {k, Divisors[n]}]/n; Table[a[n], {n,100}] (* _Jean-François Alcover_, Jul 19 2011, after given formulas *)

%o (PARI) a(n)=if(n<1,0,sumdiv(n,d,moebius(n/d)*(fibonacci(d-1)+fibonacci(d+1)))/n)

%o (Haskell)

%o a006206 n = sum (map f $ a027750_row n) `div` n where

%o f d = a008683 (n `div` d) * (a000045 (d - 1) + a000045 (d + 1))

%o -- _Reinhard Zumkeller_, Jun 01 2013

%o (Sage)

%o z = PowerSeriesRing(ZZ, 'z').gen().O(30)

%o r = (1 - (z + z**2))

%o F = -z*r.derivative()/r

%o [sum(moebius(n//d)*F[d] for d in divisors(n))//n for n in range(1, 24)] # _F. Chapoton_, Apr 24 2020

%Y Cf. A006207 (A_{n,2}), A006208 (A_{n,3}), A006209 (A_{n,4}), A130628 (A_{n,5}), A208092 (A_{n,6}), A006210 (D_{n,2}), A006211 (D_{n,3}), A094392.

%Y Cf. A001461 (partial sums), A000045, A008683, A027750.

%Y Cf. A125951 and A113788 for similar sequences.

%K nonn,easy,nice,changed

%O 1,5

%A _N. J. A. Sloane_ and _Frank Ruskey_