login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
(Formerly M0761 N0288)
12
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

REFERENCES

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

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

FORMULA

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)

EXAMPLE

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

MATHEMATICA

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

CROSSREFS

Cf. A000013, A000048, A002075.

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

Sequence in context: A056353 A111274 A133385 * A286435 A145761 A071714

Adjacent sequences:  A002073 A002074 A002075 * A002077 A002078 A002079

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 13 04:53 EDT 2020. Contains 335673 sequences. (Running on oeis4.)