A179781 -id:A179781 - 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)

A179519 'AP(n,k)' triangle read by rows. AP(n,k) is the number of aperiodic k-palindromes of n.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 1, 0, 1, 2, 1, 0, 1, 0, 3, 0, 3, 0, 0, 1, 0, 3, 2, 3, 2, 1, 0, 1, 0, 3, 0, 6, 0, 4, 0, 0, 1, 0, 4, 4, 5, 4, 4, 4, 1, 0, 1, 0, 5, 0, 10, 0, 10, 0, 5, 0, 0, 1, 0, 4, 4, 10, 8, 10, 8, 4, 4, 1, 0

Offset: 1

John P. McSorley, Jul 17 2010

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.
Let AP(n,k) denote the number of aperiodic k-palindromes of n.
This sequence is the 'AP(n,k)' triangle read by rows.
The g.f. of this triangular array follows easily from A. Howroyd's formula for this sequence and P. Deleham's g.f. for sequence A051159. If T(n,k) = A051159(n,k), then g.f. = Sum_{n,k>=1} AP(n,k)*x^n*y^k = Sum_{n,k>=1} Sum_{d|gcd(n,k)} mu(d)*T(n/d-1,k/d-1)*x^n*y^k. Letting m = n/d and s = k/d, we get g.f. = Sum_{d>=1} mu(d)*Sum_{m,s>=1} T(m-1,s-1)*(x^d)^m*(y^d)^s. But P. Deleham's formula for sequence A051159 implies Sum_{m,s>=1} T(m-1,s-1)*x^m*y^s = x*y*(1+x+x*y)/(1-x^2-x^2*y^2). Thus, Sum_{n,k>=1} AP(n,k)*x^n*y^k = Sum_{d>=1} mu(d)*f(x^d,y^d), where f(x,y) = x*y*(1+x+x*y)/(1-x^2-x^2*y^2). - Petros Hadjicostas, Nov 04 2017

			The triangle begins
  1
  1,0
  1,0,0
  1,0,1,0
  1,0,2,0,0
  1,0,1,2,1,0
  1,0,3,0,3,0,0
  1,0,3,2,3,2,1,0
  1,0,3,0,6,0,4,0,0
  1,0,4,4,5,4,4,4,1,0
For example, row 8 is 1,0,3,2,3,2,1,0.
We have AP(8,3)=3 because there are 3 aperiodic 3-palindromes of 8, namely: 161, 242, and 323.
We have AP(8,4)=2 because there are 2 aperiodic 4-palindromes of 8, namely: 3113 and 1331.

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

If we count the aperiodic k-palindromes of n up to cyclic equivalence, APE(n, k), we get sequence A179317.

The row sums of this triangle give sequence A179781. - John P. McSorley, Jul 26 2010

T[n_, k_] := Sum[MoebiusMu[d]*QBinomial[n/d-1, k/d-1, -1], {d, Divisors[ GCD[n, k]]}]; Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 30 2017, after Andrew Howroyd *)

\\ here p(n,k)=A051159(n-1,k-1) is number of k-palindromes of n.
p(n, k) = if(n%2==1&&k%2==0, 0, binomial((n-1)\2, (k-1)\2));
T(n, k) = sumdiv(gcd(n,k), d, moebius(d) * p(n/d, k/d));
for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ Andrew Howroyd, Oct 07 2017

T(n,k) = Sum_{d|gcd(n,k)} mu(d) * A051159(n/d-1, k/d-1). - Andrew Howroyd, Oct 07 2017

G.f.: Sum_{n>=1} mu(n)*f(x^n,y^n), where f(x,y) = x*y*(1+x+x*y)/(1-x^2-x^2*y^2). - Petros Hadjicostas, Nov 04 2017

Terms a(56) and beyond from Andrew Howroyd, Oct 07 2017

A181135 a(n) = ADP(n) is the total number of aperiodic k-double-palindromes of n, where 2 <= k <= n.

Original entry on oeis.org

0, 0, 2, 4, 12, 16, 42, 60, 112, 168, 310, 432, 756, 1106, 1722, 2640, 4080, 6062, 9198, 13860, 20300, 31062, 45034, 68340, 98208, 149940, 212576, 325080, 458724, 700128, 983010, 1501440, 2096096, 3202800, 4456074, 6800976, 9437148, 14398958, 19920474

Offset: 1

John P. McSorley, Oct 05 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, i.e., if it is not the concatenation of at least two smaller compositions. A palindrome is a word which is the same when written backwards.
A k-double-palindrome of n is a k-composition of n which is the concatenation of two palindromes, PP'=P|P', where both |P|, |P'|>=1. For example 1123532=11|23532 is a 7-double-palindrome of 17 since both 11 and 23532 are palindromes. It is also aperiodic, so it is an aperiodic 7-double-palindrome of 17. See sequence A181111.
The n-th term of this sequence is ADP(n), the total number of aperiodic k-double-palindromes of n, where 2 <= k <= n.
For example ADP(6)=16 because there are 16 aperiodic k-double-palindromes of 6 for k=2,3,4,5, or 6. They are:
(with k=2) 15=1|5, 51=5|1, 24=2|4, 42=4|2,
(with k=3) 114=11|4, 411=4|11,
(with k=4) 1113=111|3, 3111=3|111, 1311=131|1, 1131=1|131, 1122=11|22, and 2211=22|11,
(with k=5) 11112=1111|2, 21111=2|1111, 12111=121|11, 11121=11|121.

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

Row sums of A181111 (number of aperiodic k-double-palindromes of n).

Cf. A179781, A180322.

a(n) = { sumdiv(n, d, moebius(n/d) * (n * if(d%2, 1, 3/2) * 2^((d-1)\2) - 2^(d\2) )) } \\ Andrew Howroyd, Sep 27 2019

a(n) = A180322(n) - A179781(n). - Andrew Howroyd, Sep 27 2019

a(8) corrected and a(11) and beyond from Andrew Howroyd, Sep 27 2019

A308706 Number of chiral pairs of set partitions of a primitive cycle of n elements having exactly two different elements.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 2, 7, 12, 31, 58, 126, 233, 484, 904, 1800, 3395, 6643, 12612, 24457, 46655, 90157, 172750, 333498, 641214, 1238664, 2388618, 4620006, 8931536, 17302033, 33521792, 65042495, 126257160, 245361171, 477087772, 928510506, 1808145395, 3523813566

Offset: 0

Robert A. Russell, Jun 18 2019

nonn

			For a(7)=1, the chiral pair is 0001011-0001101.  For a(8)=2, the chiral pairs are 00001011-00001101 and 00010011-00011001.

Cf. A000048 (oriented), A000046 (unoriented), A179781 (achiral), A059053 (not primitive).

Join[{0}, Table[(DivisorSum[NestWhile[#/2 &, n, EvenQ], MoebiusMu[#] 2^(n/#) &]/(2 n) - DivisorSum[n, MoebiusMu[n/#] 2^Floor[#/2] &])/2, {n, 1, 40}]]

a(n) = if (n, (sumdiv(n, d, if (d%2, moebius(d)*2^(n/d)))/(2*n) - sumdiv(n, d, moebius(n/d)*2^(d\2)))/2, 0); \\ Michel Marcus, Jun 27 2019; corrected Jun 12 2022

a(n) = ((1/(2n)) * Sum_{odd d|n} mu(d)*2^(n/d) - Sum_{d|n} mu(n/d)*2^floor(d/2)) / 2, where mu is the Möbius function at A008683.
a(n) = A000048(n) - A000046(n) = (A000048(n) - A179781(n))/2 = A000046(n) - A179781(n).
A059053(n) = Sum_{d|n} a(d).

A180750 a(n) = DP(n) is the total number of k-double-palindromes of n, where 2 <= k <= n.

Original entry on oeis.org

0, 1, 3, 6, 13, 21, 43, 68, 116, 185, 311, 464, 757, 1157, 1741, 2720, 4081, 6214, 9199, 14078, 20353, 31405, 45035, 68930, 98224, 150761, 212706, 326362, 458725, 702209, 983011, 1504400, 2096441, 3207137, 4456139, 6808172, 9437149, 14408669, 19921297, 30393800

Offset: 1

John P. McSorley, Sep 19 2010

A k-composition of n is an ordered collection of k positive integers (parts) which sum to n. A palindrome is a word which is the same when written backwards. A k-double-palindrome of n (see sequence A180653) is a k-composition of n which is the concatenation of two palindromes, PP' = P|P', where both |P|, |P'| >= 1.
For example, 1123532 = 11|23532 is a 7-double-palindrome of 17 since both 11 and 23532 are palindromes.
The n-th term of this sequence is DP(n), the total number of k-double-palindromes of n, where 2 <= k <= n.
For example, DP(6)=21 because there are 21 k-double-palindromes of 6 for k=2,3,4,5, or 6. They are:
(with k=2) 15=1|5, 51=5|1, 24=2|4, 42=4|2, 33=3|3,
(with k=3) 114=11|4, 411=4|11, 222=2|22,
(with k=4) 1113=111|3, 3111=3|111, 1311=131|1, 1131=1|131, and 1122=11|22, 2211=22|11, 1212=121|2, 2121=2|121,
(with k=5) 11112=1111|2, 21111=2|1111, 12111=121|11, 11121=11|121,
(with k=6) 111111=1|11111.

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

a(n) is the sum of the n-th row of the triangle sequence A180653 (number of k-double-palindromes of n).

The n-th term of sequence A016116 is the total number of k-palindromes (single palindromes) of n.

a(n) = A180249(n) - A179781(n). - Petros Hadjicostas, Nov 03 2017

G.f.: Sum_{n>=1} phi^{(-1)}(n)*f(x^n) - Sum_{n>=1} mu(n)*g(x^n), where phi^{(-1)}(n) = A023900(n) is the Dirichlet inverse of Euler's totient function, mu(n) = A008683(n) is the Mobius function, f(x) = x*(x+1)*(2*x+1)/(1-2*x^2)^2, and g(x) = x*(1+2*x)/(1-2*x^2). - Petros Hadjicostas, Nov 06 2017

a(11)-a(18) from Donovan Johnson, Oct 22 2010

a(11)-a(18) corrected by and a(19)-a(40) from Petros Hadjicostas and Andrew Howroyd, Nov 03 2017

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

A179519 'AP(n,k)' triangle read by rows. AP(n,k) is the number of aperiodic k-palindromes of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A181135 a(n) = ADP(n) is the total number of aperiodic k-double-palindromes of n, where 2 <= k <= n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A308706 Number of chiral pairs of set partitions of a primitive cycle of n elements having exactly two different elements.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A180750 a(n) = DP(n) is the total number of k-double-palindromes of n, where 2 <= k <= n.

Views

Author

Keywords

Comments

References

Crossrefs

Formula

Extensions