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

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

Offset

0,5

Comments

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

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

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)

Example

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

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

Crossrefs

Similar to A000011, but counts primitive necklaces.

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

Cf. A054199.

Sequence in context: A306912 A212607 A056366 * A293641 A293553 A131132

Adjacent sequences: A000043 A000044 A000045 * A000047 A000048 A000049

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved