A308706 -id:A308706 - cp's OEIS frontend

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

N. J. A. Sloane

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

			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

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

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

Similar to A000011, but counts primitive necklaces.
A000048 (oriented), A308706 (chiral), A179781 (achiral).
Cf. A054199.

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;

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

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

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)

A179781 a(n) = AP(n) is the total number of aperiodic k-palindromes of n, 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 7, 12, 14, 27, 31, 54, 63, 119, 123, 240, 255, 490, 511, 990, 1015, 2015, 2047, 4020, 4092, 8127, 8176, 16254, 16383, 32607, 32767, 65280, 65503, 130815, 131061, 261576, 262143, 523775, 524223, 1047540, 1048575, 2096003, 2097151, 4192254

Offset: 1

John P. McSorley, Jul 26 2010

nonn

A k-composition of n is an ordered collection of k positive integers (parts) which sum to n.
A k-composition is aperiodic (primitive) if its period is k, or if it is not the concatenation of a smaller composition.
A k-palindrome of n is a k-composition of n which is a palindrome.
This sequence is AP(n), the total number of aperiodic k-palindromes of n, 1 <= k <= n.
For example AP(6)=5 because the number n=6
has 1 aperiodic 1-palindrome, namely 6 itself;
has 1 aperiodic 3-palindrome, namely 141;
has 2 aperiodic 4-palindromes, namely 2112 and 1221;
has 1 aperiodic 5-palindrome, namely 11211.
This gives a total of 1+1+2+1=5 aperiodic palindromes of 6.
Number of achiral set partitions of a primitive cycle of n elements having up to two different elements. - Robert A. Russell, Jun 19 2019

			For a(7)=7, the achiral set partitions are 0000001, 0000011, 0000101, 0000111, 0001001, 0010011, and 0010101. - _Robert A. Russell_, Jun 19 2019

John P. McSorley, Counting k-compositions of n with palindromic and related structures. Preprint, 2010.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Hunki Baek, Sejeong Bang, Dongseok Kim, Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014.

Row sums of A179519.

A000048 (oriented), A000046 (unoriented), A308706 (chiral), A016116 (not primitive). - Robert A. Russell, Jun 19 2019

a[n_] := DivisorSum[n, MoebiusMu[n/#] * 2^Floor[#/2]&];
Array[a, 44] (* Jean-François Alcover, Nov 04 2017 *)

a(n) = sumdiv(n, d, moebius(n/d) * 2^(d\2)); \\ Michel Marcus, Dec 09 2014

a(n) = Sum_{d | n} moebius(n/d)*2^(floor(d/2)) (see Baek et al. page 9). - Michel Marcus, Dec 09 2014
a(n) = 2*A000046(n) - A000048(n) = A000048(n) - 2*A308706(n) = A000046(n) - A308706(n). - Robert A. Russell, Jun 19 2019
A016116(n) =  Sum_{d|n} a(d). - Robert A. Russell, Jun 19 2019
G.f.: Sum_{k>=1} mu(k)*x^k*(1 + 2*x^k)/(1 - x^(2*k)). - Andrew Howroyd, Sep 27 2019

More terms from Michel Marcus, Dec 09 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula