|
|
A006206
|
|
Number of aperiodic binary necklaces of length n with no subsequence 00, excluding the necklace "0".
(Formerly M0317)
|
|
25
|
|
|
1, 1, 1, 1, 2, 2, 4, 5, 8, 11, 18, 25, 40, 58, 90, 135, 210, 316, 492, 750, 1164, 1791, 2786, 4305, 6710, 10420, 16264, 25350, 39650, 61967, 97108, 152145, 238818, 374955, 589520, 927200, 1459960, 2299854, 3626200, 5720274, 9030450, 14263078
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
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
|
|
REFERENCES
|
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 499.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
James Spahlinger, Table of n, a(n) for n = 1..5000
Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
Joerg Arndt, Matters Computational (The Fxtbook), p. 710.
Kam Cheong Au, Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series, arXiv:2007.03957 [math.NT], 2020. See 2nd line of Table 1 (p. 6).
Michael Baake, Joachim Hermisson, and Peter Pleasants, The torus parametrization of quasiperiodic LI-classes, J. Phys. A 30(9) (1997), 3029-3056.
Latham Boyle and Paul J. Steinhardt, Self-Similar One-Dimensional Quasilattices, arXiv:1608.08220 [math-ph], 2016.
D. J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.
D. J. Broadhurst and D. Kreimer, Association of multiple zeta values with positive knots via Feynman diagrams up to 9 loops, arXiv:hep-th/9609128, 1996.
D. J. Broadhurst and D. Kreimer, Association of multiple zeta values with positive knots via Feynman diagrams up to 9 loops, Phys. Lett B., 393 (1997), 403-412.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. 3 (2000), #00.1.5.
M. Conder, S. Du, R. Nedela, and M. Skoviera, Regular maps with nilpotent automorphism group, 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 ..."]
Bau-Sen Du, The Minimal Number of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem, Bull. Austral. Math. Soc. 31 (1985), 89-103. Corrigendum: 32 (1985), 159.
Bau-Sen Du, The Minimal Number of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem, arXiv:0706.2297 [math.DS], 2007.
Bau-Sen Du, A Simple Method Which Generates Infinitely Many Congruence Identities, Fib. Quart. 27 (1989), 116-124.
Bau-Sen Du, A Simple Method Which Generates Infinitely Many Congruence Identities, arXiv:0706.2421 [math.NT], 2007.
Larry Ericksen, Primality Testing and Prime Constellations, Šiauliai Mathematical Seminar, 3(11), 2008; mentions this sequence.
R. J. Mathar, Hardy-Littlewood constants embedded into infinite products over all positive integers, arXiv:0903.2514 [math.NT], 2009-2011; sequence gamma_{1,j}^(A).
A. Pakapongpun and T. Ward, Functorial Orbit counting, J. Integer Seqs. 12 (2009), #09.2.4; example 21.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs. 4 (2001), #01.2.1.
Index entries for sequences related to Lyndon words
|
|
FORMULA
|
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 + ...
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.
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).
a(n) = round((1/n) * Sum_{d|n} mu(n)*phi^(n/d))). - David Broadhurst
G.f.: Sum_{n >= 1} -mu(n) * log(1 - x^n - x^(2*n))/n.
a(n) = (1/n) * Sum_{d|n} mu(d) * A001610(n/d - 1), n > 1. - R. J. Mathar, Mar 07 2009
For n > 2, a(n) = A060280(n) = A031367(n)/n.
|
|
EXAMPLE
|
Necklaces are: 1, 10, 110, 1110; 11110, 11010, 111110, 111010, ...
|
|
MAPLE
|
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:
|
|
MATHEMATICA
|
a[n_] := Total[(MoebiusMu[n/#]*(Fibonacci[#+1] + Fibonacci[#-1]) & ) /@ Divisors[n]]/n;
(* 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 *)
|
|
PROG
|
(PARI) a(n)=if(n<1, 0, sumdiv(n, d, moebius(n/d)*(fibonacci(d-1)+fibonacci(d+1)))/n)
(Haskell)
a006206 n = sum (map f $ a027750_row n) `div` n where
f d = a008683 (n `div` d) * (a000045 (d - 1) + a000045 (d + 1))
-- Reinhard Zumkeller, Jun 01 2013
(Sage)
z = PowerSeriesRing(ZZ, 'z').gen().O(30)
r = (1 - (z + z**2))
F = -z*r.derivative()/r
[sum(moebius(n//d)*F[d] for d in divisors(n))//n for n in range(1, 24)] # F. Chapoton, Apr 24 2020
|
|
CROSSREFS
|
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.
Cf. A001461 (partial sums), A000045, A008683, A027750.
Cf. A125951 and A113788 for similar sequences.
Sequence in context: A013979 A107458 A274142 * A060280 A095719 A153952
Adjacent sequences: A006203 A006204 A006205 * A006207 A006208 A006209
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane and Frank Ruskey
|
|
STATUS
|
approved
|
|
|
|