|
%I M0317 #109 Jun 17 2021 08:07:07
%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://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&view=article&id=44&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(n)*phi^(n/d))). - _David Broadhurst_
%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
%O 1,5
%A _N. J. A. Sloane_ and _Frank Ruskey_
|
