A000013 -id:A000013 - cp's OEIS frontend

A000029 Number of necklaces with n beads of 2 colors, allowing turning over (these are also called bracelets).

1, 2, 3, 4, 6, 8, 13, 18, 30, 46, 78, 126, 224, 380, 687, 1224, 2250, 4112, 7685, 14310, 27012, 50964, 96909, 184410, 352698, 675188, 1296858, 2493726, 4806078, 9272780, 17920860, 34669602, 67159050, 130216124, 252745368, 490984488, 954637558, 1857545300

Offset: 0

N. J. A. Sloane

"Necklaces with turning over allowed" are usually called bracelets. - Joerg Arndt, Jun 10 2016

			For n=2, the three bracelets are AA, AB, and BB. For n=3, the four bracelets are AAA, AAB, ABB, and BBB. - _Robert A. Russell_, Sep 24 2018

J. L. Fisher, Application-Oriented Algebra (1977), ISBN 0-7002-2504-8, circa p. 215.
Martin Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pages 245-246.
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).
N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

N. J. A. Sloane, Table of n, a(n) for n = 0..300
Hoda Abbasizanjani and Oliver Kullmann, Classification of minimally unsatisfiable 2-CNFs, arXiv:2003.03639 [cs.DM], 2020.
Joerg Arndt, Matters Computational (The Fxtbook), p. 151
Henry Bottomley, Illustration of initial terms
Emanuele Brugnoli, Enumerating the Walecki-Type Hamiltonian Cycle Systems, Journal of Combinatorial Designs, Volume 25, Issue 11, November 2017, pp. 481-493.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Vladimir Dotsenko and Irvin Roy Hentzel, On the conjecture of Kashuba and Mathieu about free Jordan algebras, arXiv:2507.00437 [math.RA], 2025. See p. 14.
S. N. Ethier and J. Lee, Parrondo games with spatial dependence, arXiv preprint arXiv:1202.2609 [math.PR], 2012. - From _N. J. A. Sloane_, Jun 10 2012
S. N. Ethier and J. Lee, Parrondo games with spatial dependence II, Fluctuation and Noise Letters 11 (4) (2012), 1250030.
S. N. Ethier, Counting toroidal binary arrays, arXiv preprint arXiv:1301.2352 [math.CO], 2013.
S. N. Ethier, Counting toroidal binary arrays, Journal of Integer Sequences 16 (2013), Article 13.4.7.
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Jurij Kovič, Regular polygonal systems, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 157-171.
Jia Liu, L. Lalouat, E. Drouard, and R. Orobtchouk, Binary coded patterns for photon control using necklace problem concept, Optics Express Vol. 24, Issue 2, pp. 1133-1142 (2016).
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Zhe Sun, T. Suenaga, P. Sarkar, S. Sato, M. Kotani, and H. Isobe, Stereoisomerism, crystal structures, and dynamics of belt-shaped cyclonaphthylenes, Proc. Nat. Acad. Sci. USA, vol. 113 no. 29, pp. 8109-8114, doi: 10.1073/pnas.1606530113.
James Tilley, Stan Wagon, and Eric Weisstein, A Catalog of Facially Complete Graphs, arXiv:2409.11249 [math.CO], 2024. See p. 11.
A. M. Uludag, A. Zeytin and M. Durmus, Binary Quadratic Forms as Dessins, 2012. - From _N. J. A. Sloane_, Dec 31 2012
Eric Weisstein's World of Mathematics, Necklace
Eric Weisstein's World of Mathematics, e
Index entries for "core" sequences
Index entries for sequences related to bracelets
Index entries for sequences related to necklaces

Row sums of triangle in A052307, second column of A081720, column 2 of A051137.
Cf. A000011, A000013, A000031 (turning over not allowed), A001371 (primitive necklaces), A059076, A164090.
Cf. A000031, A051137.

with(numtheory): A000029 := proc(n) local d,s; if n = 0 then return 1 else if n mod 2 = 1 then s := 2^((n-1)/2) else s := 2^(n/2-2)+2^(n/2-1) fi; for d in divisors(n) do s := s+phi(d)*2^(n/d)/(2*n) od; return s; fi end:

a[0] := 1; a[n_] := Fold[#1 + EulerPhi[#2]2^(n/#2)/(2n) &, If[OddQ[n], 2^((n - 1)/2), 2^(n/2 - 1) + 2^(n/2 - 2)], Divisors[n]]
mx=40;CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-2*x^n]/n,{n,mx}]+(1+x)^2/(1-2*x^2))/2,{x,0,mx}],x] (* Herbert Kociemba, Nov 02 2016 *)
a[0] = 1; a[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#)&]/(2*n); Array[a, 36, 0] (* Jean-François Alcover, Nov 05 2017 *)

a(n)=if(n<1,!n,(n%2+3)/4*2^(n\2)+sumdiv(n,d,eulerphi(n/d)*2^d)/2/n)

from sympy import divisors, totient
def a(n):
    return 1 if n<1 else ((2**(n//2+1) if n%2 else 3*2**(n//2-1)) + sum(totient(n//d)*2**d for d in divisors(n))//n)//2
print([a(n) for n in range(51)]) # Indranil Ghosh, Apr 23 2017

a(n) = Sum_{d divides n} phi(d)*2^(n/d)/(2*n) + either 2^((n - 1)/2) if n odd or 2^(n/2 - 1) + 2^(n/2 - 2) if n even.
G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n + (1 + x)^2/(1 - 2*x^2))/2. - Herbert Kociemba, Nov 02 2016
Equals (A000031 + A164090) / 2 = A000031 - A059076 = A059076 + A164090. - Robert A. Russell, Sep 24 2018
From Richard L. Ollerton, May 04 2021: (Start)
a(0) = 1; a(n) = Sum_{k=1..n} 2^gcd(n,k)/(2*n) + either 2^((n - 1)/2) if n odd or 2^(n/2 - 1) + 2^(n/2 - 2) if n even.
a(0) = 1; a(n) = A000031(n)/2 + (2^floor((n+1)/2) + 2^ceiling((n+1)/2))/4. See A051137. (End)

More terms from Christian G. Bower

A063776 Number of subsets of {1,2,...,n} which sum to 0 modulo n.

Original entry on oeis.org

2, 2, 4, 4, 8, 12, 20, 32, 60, 104, 188, 344, 632, 1172, 2192, 4096, 7712, 14572, 27596, 52432, 99880, 190652, 364724, 699072, 1342184, 2581112, 4971068, 9586984, 18512792, 35791472, 69273668, 134217728, 260301176, 505290272, 981706832

Offset: 1

Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 16 2001

From Gus Wiseman, Sep 14 2019: (Start)
Also the number of subsets of {1..n} that are empty or contain n and have integer mean. If the subsets are not required to contain n, we get A327475. For example, the a(1) = 2 through a(6) = 12 subsets are:
  {}   {}   {}       {}       {}           {}
  {1}  {2}  {3}      {4}      {5}          {6}
            {1,3}    {2,4}    {1,5}        {2,6}
            {1,2,3}  {2,3,4}  {3,5}        {4,6}
                              {1,3,5}      {1,2,6}
                              {3,4,5}      {1,5,6}
                              {1,2,4,5}    {2,4,6}
                              {1,2,3,4,5}  {4,5,6}
                                           {1,2,3,6}
                                           {1,4,5,6}
                                           {2,3,5,6}
                                           {2,3,4,5,6}
(End)

			G.f. = 2*x + 2*x^2 + 4*x^3 + 4*x^4 + 8*x^5 + 12*x^6 + 20*x^7 + 32*x^8 + 60*x^9 + ...

Seiichi Manyama, Table of n, a(n) for n = 1..3333 (first 200 terms from T. D. Noe)
T. Amdeberhan, M. Can and V. Moll, Broken bracelets, Molien series, paraffin wax and the elliptic curve 48a4, SIAM Journal of Discrete Math., v.25, 2011, p. 1843. See equation (1.2).
Juhani Karhumäki, S. Puzynina, M. Rao, and M. A. Whiteland, On cardinalities of k-abelian equivalence classes, arXiv preprint arXiv:1605.03319 [math.CO], 2016.
N. Kitchloo and L. Pachter, An interesting result about subset sums, preprint (pdf file), 1993.
N. Kitchloo and L. Pachter, An interesting result about subset sums, preprint (pdf file), 1993.

The superdiagonal of A068009.
Cf. A000010, A000013, A051293, A053633, A053634, A053636, A054539, A082550.
Cf. A000016, A065795, A327475, A327481.

a063776 n = a053636 n `div` n  -- Reinhard Zumkeller, Sep 13 2013

Table[a = Select[ Divisors[n], OddQ[ # ] &]; Apply[Plus, 2^(n/a)*EulerPhi[a]]/n, {n, 1, 35}]
a[ n_] := If[ n < 1, 0, 1/n Sum[ Mod[ d, 2] EulerPhi[ d] 2^(n / d), {d, Divisors[ n]}]]; (* Michael Somos, May 09 2013 *)
Table[Length[Select[Subsets[Range[n]],#=={}||MemberQ[#,n]&&IntegerQ[Mean[#]]&]],{n,0,10}] (* Gus Wiseman, Sep 14 2019 *)

{a(n) = if( n<1, 0, 1 / n * sumdiv( n, d, (d % 2) * eulerphi(d) * 2^(n / d)))}; /* Michael Somos, May 09 2013 */

a(n) = sumdiv(n, d, (d%2)* 2^(n/d)*eulerphi(d))/n; \\ Michel Marcus, Feb 10 2016

from sympy import totient, divisors
def A063776(n): return (sum(totient(d)<>(~n&n-1).bit_length(),generator=True))<<1)//n # Chai Wah Wu, Feb 21 2023

a(n) = (1/n) * Sum_{d divides n and d is odd} 2^(n/d) * phi(d).
a(n) = (1/n) * A053636(n). - Michael Somos, May 09 2013
a(n) = 2 * A000016(n).
For odd n, a(n) = A000031(n).
G.f.: -Sum_{m >= 0} (phi(2*m + 1)/(2*m + 1)) * log(1 - 2*x^(2*m + 1)). - Petros Hadjicostas, Jul 13 2019
a(n) = A082550(n) + 1. - Gus Wiseman, Sep 14 2019

More terms from Vladeta Jovovic, Aug 20 2001

A152175 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 18, 13, 3, 1, 1, 9, 43, 50, 20, 3, 1, 1, 19, 126, 221, 136, 36, 4, 1, 1, 29, 339, 866, 773, 296, 52, 4, 1, 1, 55, 946, 3437, 4281, 2303, 596, 78, 5, 1, 1, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 1, 1, 179, 7254, 51075, 115100, 110462, 52376, 13299, 1873, 147, 6, 1

Offset: 1

Vladeta Jovovic, Nov 27 2008

Number of n-bead necklace structures using exactly k different colored beads. Turning over the necklace is not allowed. Permuting the colors does not change the structure. - Andrew Howroyd, Apr 06 2017

			Triangle begins with T(1,1):
  1;
  1,   1;
  1,   1,     1;
  1,   3,     2,      1;
  1,   3,     5,      2,      1;
  1,   7,    18,     13,      3,      1;
  1,   9,    43,     50,     20,      3,      1;
  1,  19,   126,    221,    136,     36,      4,      1;
  1,  29,   339,    866,    773,    296,     52,      4,     1;
  1,  55,   946,   3437,   4281,   2303,    596,     78,     5,    1;
  1,  93,  2591,  13250,  22430,  16317,   5817,   1080,   105   , 5,   1;
  1, 179,  7254,  51075, 115100, 110462,  52376,  13299,  1873,  147,   6, 1;
  1, 315, 20125, 194810, 577577, 717024, 439648, 146124, 27654, 3025, 187, 6, 1;
  ...
For T(4,2)=3, the set partitions are AAAB, AABB, and ABAB.
For T(4,3)=2, the set partitions are AABC and ABAC.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Andrew Howroyd, Table of n, a(n) for n = 1..1275
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Tilman Piesk, Partition related number triangles

Columns 2-6 are A056295, A056296, A056297, A056298, A056299.
Row sums are A084423.
Partial row sums include A000013, A002076, A056292, A056293, A056294.
Cf. A075195, A087854, A008277 (set partitions), A284949 (up to reflection), A152176 (up to rotation and reflection).
A(1,n,k) in formula is the Stirling subset number A008277.
A(2,n,k) in formula is A293181; A(3,n,k) in formula is A294201.

(* Using recursion formula from Gilbert and Riordan:*)
Adn[d_, n_] := Adn[d, n] = Which[0==n, 1, 1==n, DivisorSum[d, x^# &],
  1==d, Sum[StirlingS2[n, k] x^k, {k, 0, n}],
  True, Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n - 1], x] x]];
Table[CoefficientList[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/(x n), x],
   {n, 1, 10}] // Flatten (* Robert A. Russell, Feb 23 2018 *)
Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d,Adnk[d,n-1,k-#] &], Boole[n==0 && k==0]]
Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/n,{n,1,12},{k,1,n}] // Flatten (* Robert A. Russell, Oct 16 2018 *)

\\ see A056391 for Polya enumeration functions
T(n,k) = NonequivalentStructsExactly(CyclicPerms(n), k); \\ Andrew Howroyd, Oct 14 2017

R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
{ my(A=R(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

T(n,k) = (1/n)*Sum_{d|n} phi(d)*A(d,n/d,k), where A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)). - Robert A. Russell, Oct 16 2018

A002076 Number of equivalence classes of base-3 necklaces of length n, where necklaces are considered equivalent under both rotations and permutations of the symbols.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 26, 53, 146, 369, 1002, 2685, 7434, 20441, 57046, 159451, 448686, 1266081, 3588002, 10195277, 29058526, 83018783, 237740670, 682196949, 1961331314, 5648590737, 16294052602, 47071590147, 136171497650, 394427456121, 1143839943618, 3320824711205

Offset: 0

N. J. A. Sloane

Number of set partitions of an oriented cycle of length n with 3 or fewer subsets. - Robert A. Russell, Nov 05 2018

			E.g., a(2) = 2 as there are two equivalence classes of the 9 strings {00,01,02,10,11,12,20,21,22}: {00,11,22} form one equivalence class and {01,02,10,12,20,21} form the other. To see that (for example) 01 and 02 are equivalent, rotate 01 to 10 and then subtract 1 mod 3 from each element in 10 to get 02.
For a(6)=26, there are 18 achiral patterns (AAAAAA, AAAAAB, AAAABB, AAABAB, AAABBB, AABAAB, AABABB, ABABAB, AAAABC, AAABAC, AAABCB, AABAAC, AABBCC, AABCBC, AABCCB, ABABAC, ABACBC, ABCABC) and 8 chiral patterns in four pairs (AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, AABACC-AABBAC). - _Robert A. Russell_, Nov 05 2018

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

Vincenzo Librandi, Table of n, a(n) for n = 0..500
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Marko Riedel, Necklaces with swappable colors by Power Group Enumeration
Marko Riedel, Maple code for any necklace size, any number of swappable colors, by Power Group Enumeration.
N. J. A. Sloane, Maple code for this and related sequences
Index entries for sequences related to necklaces

Cf. A000013, A000048, A002075.

Cf. A056353 (unoriented), A320743 (chiral), A182522 (achiral).

Adn[d_, n_] := Module[{ c, t1, t2}, t2 = 0; For[c = 1, c <= d, c++, If[Mod[d, c] == 0 , t2 = t2 + (x^c/c)*(E^(c*z) - 1)]]; t1 = E^t2; t1 = Series[t1, {z, 0, n+1}]; Coefficient[t1, z, n]*n!]; Pn[n_] := Module[{ d, e, t1}, t1 = 0; For[d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*Adn[d, n/d]/n]]; t1/(1 - x)]; Pnq[n_, q_] := Module[{t1}, t1 = Series[Pn[n], {x, 0, q+1}] ; Coefficient[t1, x, q]]; a[n_] := Pnq[n, 3]; Print[1]; Table[Print[an = a[n]]; an, {n, 1, 28}] (* Jean-François Alcover, Oct 04 2013, after N. J. A. Sloane's Maple code *)
(* This Mathematica program uses Gilbert and Riordan's recurrence formula, which they recommend for calculations: *)
Adn[d_, n_] := Adn[d, n] = If[1==n, DivisorSum[d, x^# &],
  Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n-1], x] x]];
Join[{1},Table[SeriesCoefficient[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &] /(n (1 - x)), {x, 0, 3}], {n,40}]]  (* Robert A. Russell, Feb 24 2018 *)
From Robert A. Russell, May 29 2018: (Start)
Join[{1},Table[(1/n) DivisorSum[n, EulerPhi[#] Which[Divisible[#, 6], 3 StirlingS2[n/#+2, 3] - 9 StirlingS2[n/#+1, 3] + 6 StirlingS2[n/#, 3], Divisible[#, 3], 2 StirlingS2[n/#+2, 3] - 7 StirlingS2[n/#+1, 3] + 6 StirlingS2[n/#, 3], Divisible[#, 2], 2 StirlingS2[n/#+2, 3] - 6 StirlingS2[n/#+1, 3] + 4 StirlingS2[n/#, 3], True, StirlingS2[n/#+2, 3] - 4 StirlingS2[n/#+1, 3] + 4 StirlingS2[n/#, 3]] &], {n,40}]] (* or *)
mx = 40; CoefficientList[Series[1 - Sum[(EulerPhi[d] / d) Which[
  Divisible[d, 6], Log[1 - 3x^d], Divisible[d, 3], (Log[1 - 3x^d] +
  Log[1 - x^d]) / 2, Divisible[d, 2], 2 Log[1 - 3x^d] / 3, True, (Log[1 - 3x^d] + 3 Log[1 - x^d]) / 6], {d, 1, mx}], {x, 0, mx}], x]
(End)
(* Adnk(n,d,k) is coefficient of x^k in A(d,n)(x) from Gilbert & Riordan *)
Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d,Adnk[d,n-1,k-#]&], Boole[n==0 && k==0]]
k=3; Join[{1},Table[Sum[DivisorSum[n,EulerPhi[#] Adnk[#,n/#,j] &],{j,k}]/n,{n,40}]] (* Robert A. Russell, Nov 05 2018 *)

Reference gives formula.
From Robert A. Russell, May 29 2018: (Start)
For n>0, a(n) = (1/n) * Sum_{d|n} phi(d) * ([d==0 mod 6] * (3*S2(n/d+2, 3) - 9*S2(n/d+1, 3) + 6*S2(n/d, 3)) + [d==3 mod 6] * (2*S2(n/d+2, 3) - 7*S2(n/d+1, 3) + 6*S2(n/d, 3)) + [d==2 mod 6 | d==4 mod 6] * (2*S2(n/d+2, 3) - 6*S2(n/d+1, 3) + 4*S2(n/d, 3)) + [d==1 mod 6 | d=5 mod 6] * (S2(n/d+2, 3) - 4*S2(n/d+1, 3) + 4*S2(n/d, 3))), where S2(n,k) is the Stirling subset number, A008277.
G.f.: 1 - Sum_{d>0} (phi(d) / d) * ([d==0 mod 6] * log(1-3x^d) +
  [d==3 mod 6] * (log(1-3x^d) + log(1-x^d)) / 2 +
  [d==2 mod 6 | d==4 mod 6] * 2*log(1-3x^d) / 3 +
  [d==1 mod 6 | d=5 mod 6] * (log(1-3x^d) + 3*log(1-x^d)) / 6).
(End)

Better description and more terms from Mark Weston (mweston(AT)uvic.ca), Oct 06 2001

a(0)=1 prepended by Robert A. Russell, Nov 05 2018

A056292 Number of n-bead necklace structures using a maximum of four different colored beads.

Original entry on oeis.org

1, 2, 3, 7, 11, 39, 103, 367, 1235, 4439, 15935, 58509, 215251, 799697, 2983217, 11187567, 42109451, 159082753, 602809327, 2290684251, 8726308317, 33318661277, 127479700199, 488672302909, 1876500180291, 7217308815887, 27799998949873, 107228568948547

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Marko Riedel, Necklaces with swappable colors by Power Group Enumeration
Marko Riedel, Maple code for any necklace size, any number of swappable colors, by Power Group Enumeration.
N. J. A. Sloane, Maple code for this and related sequences

Cf. A000013, A001868.

Adn[d_, n_] := Module[{ c, t1, t2}, t2 = 0; For[c = 1, c <= d, c++, If[Mod[d, c] == 0 , t2 = t2 + (x^c/c)*(E^(c*z) - 1)]]; t1 = E^t2; t1 = Series[t1, {z, 0, n+1}]; Coefficient[t1, z, n]*n!]; Pn[n_] := Module[{ d, e, t1}, t1 = 0; For[d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*Adn[d, n/d]/n]]; t1/(1 - x)]; Pnq[n_, q_] := Module[{t1}, t1 = Series[Pn[n], {x, 0, q+1}] ; Coefficient[t1, x, q]]; a[n_] := Pnq[n, 4]; Table[Print[an = a[n]]; an, {n, 1, 25}] (* Jean-François Alcover, Oct 04 2013, after N. J. A. Sloane's Maple code *)
(* This program uses Gilbert and Riordan's recurrence formula, which they recommend for calculations: *)
Adn[d_, n_] := Adn[d, n] = If[1==n, DivisorSum[d, x^# &],
  Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n-1], x] x]];
Table[SeriesCoefficient[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]
/(n (1 - x)), {x, 0, 4}], {n, 1, 40}] (* Robert A. Russell, Feb 24 2018 *)
From Robert A. Russell, May 29 2018: (Start)
Table[(1/n) DivisorSum[n, EulerPhi[#] Which[Divisible[#,12], 4 StirlingS2[n/#+3,4] - 24 StirlingS2[n/#+2,4] + 44 StirlingS2[n/#+1,4] - 24 StirlingS2[n/#,4], Divisible[#,6], 3 StirlingS2[n/#+3,4] - 18 StirlingS2[n/#+2,4] + 33 StirlingS2[n/#+1,4] - 18 StirlingS2[n/#,4], Divisible[#,4], 3 StirlingS2[n/#+3,4] - 19 StirlingS2[n/#+2,4] + 38 StirlingS2[n/#+1,4] - 24 StirlingS2[n/#,4], Divisible[#,3], 2 StirlingS2[n/#+3,4] - 13 StirlingS2[n/#+2,4] + 26 StirlingS2[n/#+1,4] - 15 StirlingS2[n/#,4], Divisible[#,2], 2 StirlingS2[n/#+3,4] - 13 StirlingS2[n/#+2,4] + 27 StirlingS2[n/#+1,4] - 18 StirlingS2[n/#,4], True, StirlingS2[n/#+3,4] - 8 StirlingS2[n/#+2,4] + 20 StirlingS2[n/#+1,4] - 15 StirlingS2[n/#,4]] &],{n, 1, 40}]
mx = 40; Drop[CoefficientList[Series[1 - Sum[(EulerPhi[d] / d) Which[
  Divisible[d, 12], Log[1 - 4x^d], Divisible[d, 6],
  3 Log[1 - 4x^d] / 4, Divisible[d, 4] ,
  (2 Log[1 - 4x^d] + Log[1 - x^d]) / 3, Divisible[d, 3],
  (3 Log[1 - 4x^d] + 2 Log[1 - 2x^d]) / 8,
  Divisible[d, 2], (5 Log[1 - 4x^d] + 4 Log[1 - x^d]) / 12,
  True, (Log[1 - 4x^d] + 6 Log[1 - 2x^d] + 8 Log[1 - x^d]) / 24], {d, 1, mx}], {x, 0, mx}], x], 1]
(End)

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
From Robert A. Russell, May 29 2018: (Start)
a(n) = (1/n) * Sum_{d|n} phi(d) * ([d==0 mod 12] * (4*S2(n/d+3, 4) - 24*S2(n/d+2, 4) + 44*S2(n/d+1, 4) - 24*S2(n/d, 4)) + [d==6 mod 12] * (3*S2(n/d+3, 4) - 18*S2(n/d+2, 4) + 33*S2(n/d+1, 4) - 18*S2(n/d, 4)) + [d==4 mod 12 | d==8 mod 12] * (3*S2(n/d+3, 4) - 19*S2(n/d+2, 4) + 38*S2(n/d+1, 4) - 24*S2(n/d, 4)) + [d==3 mod 12 | d=9 mod 12] * (2*S2(n/d+3, 4) - 13*S2(n/d+2, 4) + 26*S2(n/d+1, 4) - 15*S2(n/d, 4)) + [d==2 mod 12 | d=10 mod 12] * (2*S2(n/d+3, 4) - 13*S2(n/d+2, 4) + 27*S2[n/d+1,4) - 18*S2(n/d, 4)) + [d mod 12 in {1,5,7,11}] * (S2(n/d+3, 4) - 8*S2(n/d+2, 4) + 20*S2(n/d+1, 4) - 15*S2(n/d, 4))), where S2(n, k) is the Stirling subset number, A008277.
G.f.: 1 - Sum_{d>0} (phi(d) / d) * ([d==0 mod 12] * log(1-4x^d) + [d==6 mod 12] * 3*log(1-4x^d) / 4 + [d==4 mod 12 | d==8 mod 12] * (2*log(1-4x^d) + log(1-x^d)) / 3 + [d==3 mod 12 | d=9 mod 12] * (3*log(1-4x^d) + 2*log(1-2x^d)) / 8 + [d==2 mod 12 | d=10 mod 12] * (5*log(1-4x^d) + 4*log(1-x^d)) / 12 + [d mod 12 in {1,5,7,11}] * (log(1-4x^d) + 6*log(1-2x^d) + 8*log(1-x^d)) / 24).
(End)

A059053 Number of chiral pairs of necklaces with n beads and two colors (color complements being equivalent); i.e., turning the necklace over neither leaves it unchanged nor simply swaps the colors.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 2, 7, 12, 31, 58, 126, 234, 484, 906, 1800, 3402, 6643, 12624, 24458, 46686, 90157, 172810, 333498, 641340, 1238671, 2388852, 4620006, 8932032, 17302033, 33522698, 65042526, 126258960, 245361172, 477091232

Offset: 0

Henry Bottomley, Dec 21 2000

nonn

Number of chiral pairs of set partitions of a cycle of n elements using exactly two different elements. - Robert A. Russell, Oct 02 2018

			For a(7) = 1, the chiral pair is AAABABB-AAABBAB.
For a(8) = 2, the chiral pairs are AAAABABB-AAAABBAB and AAABAABB-AAABBAAB.

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Illustration of initial terms
Index entries for sequences related to necklaces

Column 2 of A320647 and A320742.

Cf. A056295 (oriented), A056357 (unoriented), A052551(n-2) (achiral).

Prepend[Table[DivisorSum[n, EulerPhi[#] StirlingS2[n/# + If[Divisible[#,2],1,0], 2] &] / (2n) - StirlingS2[1+Floor[n/2],2] / 2, {n, 1, 40}],0] (* Robert A. Russell, Oct 02 2018 *)

a(n) = {if(n<1, 0, (sumdiv(n, k, eulerphi(2*k) * 2^(n/k)) / (2*n) - 2^(n\2))/2)}; \\ Andrew Howroyd, Nov 03 2019

a(n) = A000013(n) - A000011(n) = A000011(n) - A016116(n) = (A000013(n) - A016116(n))/2.
From Robert A. Russell, Oct 02 2018: (Start)
a(n) = (A056295(n)-A052551(n-2)) / 2 = A056295(n) - A056357(n) = A056357(n) - A052551(n-2).
a(n) = -S2(1+floor(n/2),2) + (1/2n) * Sum_{d|n} phi(d) * S2(n/d+[2|d],2), where S2 is a Stirling subset number A008277.
G.f.: -x(1+2x)/(2-4x^2) - Sum_{d>0} phi(d) * log(1-2x^d) / (2d*(2-[2|d])).
(End)

Name clarified by Robert A. Russell, Oct 02 2018

A056293 Number of n-bead necklace structures using a maximum of five different colored beads.

Original entry on oeis.org

1, 2, 3, 7, 12, 42, 123, 503, 2008, 8720, 38365, 173609, 792828, 3662924, 17034381, 79703081, 374624254, 1767883444, 8370666417, 39751072847, 189262621864, 903220058756, 4319518316899, 20697040198889, 99343899144822, 477609477924308, 2299585449279713

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Vincenzo Librandi, Table of n, a(n) for n = 1..500
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
N. J. A. Sloane, Maple code for this and related sequences

Cf. A000013, A001869.

Adn[d_, n_] := Module[{ c, t1, t2}, t2 = 0; For[c = 1, c <= d, c++, If[Mod[d, c] == 0 , t2 = t2 + (x^c/c)*(E^(c*z) - 1)]]; t1 = E^t2; t1 = Series[t1, {z, 0, n+1}]; Coefficient[t1, z, n]*n!]; Pn[n_] := Module[{ d, e, t1}, t1 = 0; For[d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*Adn[d, n/d]/n]]; t1/(1 - x)]; Pnq[n_, q_] := Module[{t1}, t1 = Series[Pn[n], {x, 0, q+1}] ; Coefficient[t1, x, q]]; a[n_] := Pnq[n, 5]; Table[Print[an = a[n]]; an, {n, 1, 24}] (* Jean-François Alcover, Oct 04 2013, after N. J. A. Sloane's Maple code *)
(* this Mathematica program uses Gilbert and Riordan's recurrence formula, which they recommend for calculations: *)
Adn[d_, n_] := Adn[d, n] = If[1==n, DivisorSum[d, x^# &],
  Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n-1], x] x]];
Table[SeriesCoefficient[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]
/(n (1 - x)), {x, 0, 5}], {n, 1, 40}] (* Robert A. Russell, Feb 24 2018 *)
From Robert A. Russell, May 29 2018: (Start)
Table[(1/n) DivisorSum[n, EulerPhi[#] Which[Divisible[#, 60], 5 StirlingS2[n/#+4, 5] - 50 StirlingS2[n/#+3, 5] + 175 StirlingS2[n/#+2, 5] - 250 StirlingS2[n/#+1, 5] + 120 StirlingS2[n/#, 5], Divisible[#, 30], 4 StirlingS2[n/#+4, 5] - 41 StirlingS2[n/#+3, 5] + 149 StirlingS2[n/#+2, 5] - 226 StirlingS2[n/#+1, 5] + 120 StirlingS2[n/#, 5], Divisible[#, 20], 4 StirlingS2[n/#+4, 5] - 42 StirlingS2[n/#+3, 5] + 156 StirlingS2[n/#+2, 5] - 238 StirlingS2[n/#+1, 5] + 120 StirlingS2[n/#, 5], Divisible[#, 15], 3 StirlingS2[n/#+4, 5] - 33 StirlingS2[n/#+3, 5] + 129 StirlingS2[n/#+2, 5] - 210 StirlingS2[n/#+1, 5] + 120 StirlingS2[n/#, 5], Divisible[#, 12], 4 StirlingS2[n/#+4, 5] - 40 StirlingS2[n/#+3, 5] + 140 StirlingS2[n/#+2, 5] - 200 StirlingS2[n/#+1, 5] + 96 StirlingS2[n/#, 5], Divisible[#, 10], 3 StirlingS2[n/#+4, 5] - 33 StirlingS2[n/#+3, 5] + 130 StirlingS2[n/#+2, 5] - 214 StirlingS2[n/#+1, 5] + 120 StirlingS2[n/#, 5], Divisible[#, 6], 3 StirlingS2[n/#+4, 5] - 31 StirlingS2[n/#+3, 5] + 114 StirlingS2[n/#+2, 5] - 176 StirlingS2[n/#+1, 5] + 96 StirlingS2[n/#, 5], Divisible[#, 5], 2 StirlingS2[n/#+4, 5] - 23 StirlingS2[n/#+3, 5] + 95 StirlingS2[n/#+2, 5] - 165 StirlingS2[n/#+1, 5] + 100 StirlingS2[n/#, 5], Divisible[#, 4], 3 StirlingS2[n/#+4, 5] - 32 StirlingS2[n/#+3, 5] + 121 StirlingS2[n/#+2, 5] - 188 StirlingS2[n/#+1, 5] + 96 StirlingS2[n/#, 5], Divisible[#, 3], 2 StirlingS2[n/#+4, 5] - 23 StirlingS2[n/#+3, 5] + 94 StirlingS2[n/#+2, 5] - 160 StirlingS2[n/#+1, 5] + 96 StirlingS2[n/#, 5], Divisible[#, 2], 2 StirlingS2[n/#+4, 5] - 23 StirlingS2[n/#+3, 5] + 95 StirlingS2[n/#+2, 5] - 164 StirlingS2[n/#+1, 5] + 96 StirlingS2[n/#, 5], True, StirlingS2[n/#+4, 5] - 13 StirlingS2[n/#+3, 5] + 60 StirlingS2[n/#+2, 5] - 115 StirlingS2[n/#+1, 5] + 76 StirlingS2[n/#, 5]] &], {n, 1, 40}]
mx = 40; Drop[CoefficientList[Series[1-Sum[(EulerPhi[d] / d) Which[ Divisible[d, 60], Log[1-5x^d], Divisible[d, 30], (3 Log[1-5x^d] + Log[1-x^d]) / 4, Divisible[d, 20], (2 Log[1-5x^d] + Log[1-2x^d]) / 3, Divisible[d, 15], (3 Log[1-5x^d] + 2 Log[1-3x^d] + 3 Log[1-x^d]) / 8, Divisible[d, 12], 4 Log[1-5x^d] / 5, Divisible[d, 10], (5 Log[1-5x^d] + 4 Log[1-2x^d] + 3 Log[1-x^d]) / 12, Divisible[d, 6], (11 Log[1-5x^d] + 5 Log[1-x^d]) / 20, Divisible[d, 5], (5 Log[1-5x^d] + 2 Log[1-3x^d] + 4 Log[1-2x^d] + 9 Log[1-x^d]) / 24, Divisible[d, 4], (7 Log[1-5x^d] + 5 Log[1-2x^d]) / 15, Divisible[d, 3], (7 Log[1-5x^d] + 10 Log[1-3x^d] + 15 Log[1-x^d]) / 40, Divisible[d, 2], (13 Log[1-5x^d] + 20 Log[1-2x^d] + 15 Log[1-x^d]) / 60, True, (Log[1-5x^d] + 10 Log[1-3x^d] + 20 Log[1-2x^d] + 45 Log[1-x^d]) / 120], {d, 1, mx}], {x, 0, mx}], x], 1]
(End)

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
From Robert A. Russell, May 29 2018: (Start)
a(n) = (1/n) * Sum_{d|n} phi(d) * ([d==0 mod 60] * (5*S2(n/d + 4, 5) - 50*S2(n/d + 3, 5) + 175*S2(n/d + 2, 5) - 250*S2(n/d + 1, 5) + 120*S2(n/d, 5)) + [d==30 mod 60] * (4*S2(n/d+4,5) - 41*S2(n/d+3,5) + 149*S2(n/d+2,5) - 226*S2(n/d + 1, 5) + 120*S2(n/d, 5)) + [d==20 mod 60 | d==40 mod 60] * (4*S2(n/d + 4, 5) - 42*S2(n/d + 3, 5) + 156*S2(n/d + 2, 5) - 238*S2(n/d + 1, 5) + 120*S2(n/d, 5)) + [d==15 mod 60 | d==45 mod 60] * (3*S2(n/d + 4, 5) - 33*S2(n/d + 3, 5) + 129*S2(n/d + 2, 5) - 210*S2(n/d + 1, 5) + 120*S2(n/d, 5)) + [d mod 60 in {12,24,36,48}] * (4*S2(n/d + 4, 5) - 40*S2(n/d + 3, 5) + 140*S2(n/d + 2, 5) - 200*S2(n/d+1, 5) + 96*S2(n/d, 5)) + [d=10 mod 60 | d==50 mod 60] * (3*S2(n/d + 4, 5) - 33*S2(n/d + 3, 5) + 130*S2(n/d + 2, 5) - 214*S2(n/d + 1, 5) + 120*S2(n/d, 5)) + [d mod 60 in {6,18,42,54}] * (3*S2(n/d + 4, 5) - 31*S2(n/d + 3, 5) + 114*S2(n/d + 2, 5) - 176*S2(n/d + 1, 5) + 96*S2(n/d, 5)) + [d mod 60 in {5,25,35,55}] * (2*S2(n/d + 4, 5) - 23*S2(n/d + 3, 5) + 95*S2(n/d + 2, 5) - 165*S2(n/d + 1, 5) + 100*S2(n/d, 5)) + [d mod 60 in {4,8,16,28,32,44,52,56}] * (3*S2(n/d + 4, 5) - 32*S2(n/d + 3, 5) + 121*S2(n/d + 2, 5) - 188*S2(n/d + 1, 5) + 96*S2(n/d, 5)) + [d mod 60 in {3,9,21,27,33,39,51,57}] * (2*S2(n/d + 4, 5) - 23*S2(n/d + 3, 5) + 94*S2(n/d + 2, 5) - 160*S2(n/d + 1, 5) + 96*S2(n/d, 5)) + [d mod 60 in {2,14,22,26,34,38,46,58}] * (2*S2(n/d + 4, 5) - 23*S2(n/d + 3, 5) + 95*S2(n/d + 2, 5) - 164*S2(n/d + 1, 5) + 96*S2(n/d, 5)) + [d mod 60 in {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}] * (S2[n/d + 4, 5) - 13*S2(n/d + 3, 5) + 60*S2(n/d + 2, 5) - 115*S2(n/d + 1, 5) + 76*S2(n/d, 5))), where S2(n,k) is the Stirling subset number, A008277.
G.f.: 1 - Sum_{d>0} (phi(d) / d) * ([d==0 mod 60] * log(1-5x^d) + [d==30 mod 60] * (3*log(1-5x^d) + log(1-x^d)) / 4 + [d==20 mod 60 | d==40 mod 60] * (2*log(1-5x^d) + log(1-2x^d)) / 3 + [d==15 mod 60 | d==45 mod 60] * (3*log(1-5x^d) + 2*log(1-3x^d) + 3*log(1-x^d)) / 8 + [d mod 60 in {12,24,36,48}] * 4*log(1-5x^d) / 5 + [d=10 mod 60 | d==50 mod 60] * (5*log(1-5x^d) + 4*log(1-2x^d) + 3*log(1-x^d)) / 12 + [d mod 60 in {6,18,42,54}] * (11*log(1-5x^d) + 5*log(1-x^d)) / 20 + [d mod 60 in {5,25,35,55}] * (5*log(1-5x^d) + 2*log(1-3x^d) + 4*log(1-2x^d) + 9*log(1-x^d)) / 24 + [d mod 60 in {4,8,16,28,32,44,52,56}] * (7*log(1-5x^d) + 5*log(1-2x^d)) / 15 + [d mod 60 in {3,9,21,27,33,39,51,57}] * (7*log(1-5x^d) + 10*log(1-3x^d) + 15*log(1-x^d)) / 40 + [d mod 60 in {2,14,22,26,34,38,46,58}] * (13*log(1-5x^d) + 20*log(1-2x^d) + 15*log(1-x^d)) / 60 +[d mod 60 in{1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}] * (log(1-5x^d) + 10*log(1-3x^d) + 20*log(1-2x^d) + 45*log(1-x^d)) / 120).
(End)

A056295 Number of n-bead necklace structures using exactly two different colored beads.

Original entry on oeis.org

0, 1, 1, 3, 3, 7, 9, 19, 29, 55, 93, 179, 315, 595, 1095, 2067, 3855, 7315, 13797, 26271, 49939, 95419, 182361, 349715, 671091, 1290871, 2485533, 4794087, 9256395, 17896831, 34636833, 67110931, 130150587, 252648991, 490853415, 954444607, 1857283155, 3616828363

Offset: 1

Marks R. Nester

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

			For a(7) = 9, the color patterns are AAAAAAB, AAAAABB, AAAABAB, AAAABBB, AAABAAB, AABAABB, AABABAB, AAABABB, and AAABBAB. The first seven are achiral; the last two are a chiral pair. - _Robert A. Russell_, Mar 08 2018

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2.]

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 17.

Column 2 of A152175.

Cf. A000013, A052823.

Maple
```
See A000013.
```

Table[DivisorSum[n, EulerPhi[#] If[OddQ[#], StirlingS2[n/#, 2], StirlingS2[n/#+1, 2]]&]/n, {n,1,30}] (* Robert A. Russell, Feb 20 2018 *)

a(n) = A000013(n) - 1.
From Robert A. Russell, Mar 08 2018: (Start)
G.f.: Sum_{ d>0 } phi(d)*(2*log(1-x^d) - (1+[d == 0 mod 2])*log(1-2*x^d)) / (2*d);
a(n) = (1/n)*Sum_{d|n} phi(d) * S2(n/d + [d == 0 mod 2], 2), where S2(n, k) is the Stirling subset number, A008277. (End)

A002075 Number of equivalence classes with primitive period n of base 3 necklaces, where necklaces are equivalent under rotation and permutation of symbols.

Original entry on oeis.org

1, 1, 2, 4, 8, 22, 52, 140, 366, 992, 2684, 7404, 20440, 56992, 159440, 448540, 1266080, 3587610, 10195276, 29057520, 83018728, 237737984, 682196948, 1961323740, 5648590728, 16294032160, 47071589778, 136171440600

Offset: 1

N. J. A. Sloane

N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
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).

Index entries for sequences related to necklaces

Cf. A000013, A000048, A002076.

Reference gives formula.

Sequence A002076 can be found as follows: Let F3(n) = this sequence, F3*(n) = function from A002076. Then F3*(n) = Sum_{ d divides n } F3(d).

Better description and more terms from Mark Weston (mweston(AT)uvic.ca), Oct 07 2001

A007148 Number of self-complementary 2-colored bracelets (turnover necklaces) with 2n beads.

Original entry on oeis.org

1, 2, 3, 6, 10, 20, 37, 74, 143, 284, 559, 1114, 2206, 4394, 8740, 17418, 34696, 69194, 137971, 275280, 549258, 1096286, 2188333, 4369162, 8724154, 17422652, 34797199, 69505908, 138845926, 277383872, 554189329, 1107297290, 2212558942

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
E. M. Palmer and R. W. Robinson, Enumeration of self-dual configurations Pacific J. Math., 110 (1984), 203-221.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Index entries for sequences related to bracelets

Cf. A000013, A000079, A007147.

Different from, but easily confused with, A045690 and A093371.

# see A245558
L := proc(n,k)
    local a,j ;
    a := 0 ;
    for j in numtheory[divisors](igcd(n,k)) do
        a := a+numtheory[mobius](j)*binomial(n/j,k/j) ;
    end do:
    a/n ;
end proc:
A007148 := proc(n)
    local a,k,l;
    a := 0 ;
    for k from 1 to n do
        for l in numtheory[divisors](igcd(n,k)) do
            a := a+L(n/l,k/l)*ceil(k/2/l) ;
        end do:
    end do:
    a;
end proc:
seq(A007148(n),n=1..20) ; # R. J. Mathar, Jul 23 2017

a[n_] := (1/2)*(2^(n-1) + Total[ EulerPhi[2*#]*2^(n/#) &  /@ Divisors[n]]/(2*n)); Table[ a[n], {n, 1, 33}] (* Jean-François Alcover, Oct 25 2011 *)

a(n)= (1/2) *(2^(n-1)+sumdiv(n,k,eulerphi(2*k)*2^(n/k))/(2*n))

from sympy import divisors, totient
def a(n):
    if n==1: return 1
    return 2**(n - 2) + sum(totient(2*d)*2**(n//d) for d in divisors(n))//(4*n)
print([a(n) for n in range(1, 31)]) # Indranil Ghosh, Jul 24 2017

a(n) = 2^(n-2) + (1/(4n)) * Sum_{d|n} phi(2d)*2^(n/d). - N. J. A. Sloane, Sep 25 2012

a(n) = (1/2)*(A000079(n-1) + A000013(n)).

Description corrected by Christian G. Bower

cp's OEIS Frontend

A000029 Number of necklaces with n beads of 2 colors, allowing turning over (these are also called bracelets).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A063776 Number of subsets of {1,2,...,n} which sum to 0 modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

Extensions

A152175 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A002076 Number of equivalence classes of base-3 necklaces of length n, where necklaces are considered equivalent under both rotations and permutations of the symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A056292 Number of n-bead necklace structures using a maximum of four different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A059053 Number of chiral pairs of necklaces with n beads and two colors (color complements being equivalent); i.e., turning the necklace over neither leaves it unchanged nor simply swaps the colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs