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, 928772649, 1808669170, 3524337789, 6872471442

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 John Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5(4) (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 17(1-2) (2023), 111-139.

Karyn McLellan, Periodic coefficients and random Fibonacci sequences, Elect. J. Comb. 20(4) (2013), #P32.

Michael Francesco Salzmann, Volker Kahlenberg, Hannes Krüger, and Tim Netzer, Glass bead games: enumeration of possible polytypes based on two stacking vectors and applications to the iron-ore sinter phases SFCA and SFCA-I, Found. Crystal. 82(3) (2026). See pp. 4-5, 8.

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

Prog

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

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