A000046 Number of primitive n-bead necklaces (turning over is allowed) where complements are equivalent.

1, 1, 1, 1, 2, 3, 5, 8, 14, 21, 39, 62, 112, 189, 352, 607, 1144, 2055, 3885, 7154, 13602, 25472, 48670, 92204, 176770, 337590, 649341, 1246840, 2404872, 4636389, 8964143, 17334800, 33587072, 65107998, 126387975, 245492232, 477349348, 928772649, 1808669170, 3524337789, 6872471442

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Also, number of "twills" (Grünbaum and Shephard). - N. J. A. Sloane, Oct 21 2015

Examples

			For a(7)=8, there are seven achiral set partitions (0000001, 0000011, 0000101, 0000111, 0001001, 0010011, 0010101) and one chiral pair (0001011-0001101). - _Robert A. Russell_, Jun 19 2019
		

References

• B. Grünbaum and G. C. Shephard, The geometry of fabrics, pp. 77-98 of F. C. Holroyd and R. J. Wilson, editors, Geometrical Combinatorics. Pitman, Boston, 1984.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Christian G. Bower, Table of n, a(n) for n = 0..1000
• E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
• J. E. Iglesias, A formula for the number of closest packings of equal spheres having a given repeat period, Z. Krist. 155 (1981) 121-127, Table 1.
• Sara Jensen, Sequence knitting, J. Math. Arts (2023).
• Karyn McLellan, Periodic coefficients and random Fibonacci sequences, Electronic Journal of Combinatorics, 20(4), 2013, #P32.
• Index entries for sequences related to necklaces

Crossrefs

Similar to A000011, but counts primitive necklaces.

A000048 (oriented), A308706 (chiral), A179781 (achiral).

Cf. A054199.

Programs

Maple

with(numtheory); A000046 := proc(n) local s,d; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+mobius(d)*A000011(n/d); od; RETURN(s); fi; end;

Mathematica

a11[0] = 1; a11[n_] := 2^Floor[n/2]/2 + Sum[EulerPhi[2*d]*2^(n/d), {d, Divisors[n]}]/n/4; a[0] = 1; a[n_] := Sum[MoebiusMu[d]*a11[n/d], {d, Divisors[n]}]; Table[a[n], {n, 0, 36}] (* Jean-François Alcover, Jul 10 2012, from formula *)
Join[{1}, Table[(DivisorSum[NestWhile[#/2 &, n, EvenQ], MoebiusMu[#] 2^(n/#) &]/(2 n) + DivisorSum[n, MoebiusMu[n/#] 2^Floor[#/2] &])/2, {n, 1, 40}]] (* Robert A. Russell, Jun 19 2019 *)

PARI

apply( {A000046(n)=if(n, sumdiv(n, d, moebius(d)*A000011(n/d)), 1)}, [0..40]) \\ M. F. Hasler, May 27 2025

Formula

a(n) = Sum_{ d divides n } mu(d)*A000011(n/d).

From Robert A. Russell, Jun 19 2019: (Start)

a(n) = ((1/(2n))Sum_{odd d|n} mu(d)*2^(n/d) + Sum_{d|n} mu(n/d)*2^floor(d/2)) / 2.

a(n) = A000048(n) - A308706(n) = (A000048(n) + A179781(n))/2 = A308706(n) + A179781(n).

A000011(n) = Sum_{d|n} a(d). (End)