A002076 - OEIS

%I M0761 N0288 #66 May 25 2019 19:29:56

%S 1,1,2,3,6,9,26,53,146,369,1002,2685,7434,20441,57046,159451,448686,

%T 1266081,3588002,10195277,29058526,83018783,237740670,682196949,

%U 1961331314,5648590737,16294052602,47071590147,136171497650,394427456121,1143839943618,3320824711205

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

%C Number of set partitions of an oriented cycle of length n with 3 or fewer subsets. - _Robert A. Russell_, Nov 05 2018

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H Vincenzo Librandi, <a href="/A002076/b002076.txt">Table of n, a(n) for n = 0..500</a>

%H N. J. Fine, <a href="http://projecteuclid.org/euclid.ijm/1255381350">Classes of periodic sequences</a>, Illinois J. Math., 2 (1958), 285-302.

%H E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.

%H Marko Riedel, <a href="https://math.stackexchange.com/questions/3121744/">Necklaces with swappable colors by Power Group Enumeration</a>

%H Marko Riedel, <a href="/A002076/a002076.maple.txt">Maple code for any necklace size, any number of swappable colors, by Power Group Enumeration.</a>

%H N. J. A. Sloane, <a href="/A000013/a000013.txt">Maple code for this and related sequences</a>

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%F Reference gives formula.

%F From _Robert A. Russell_, May 29 2018: (Start)

%F 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.

%F G.f.: 1 - Sum_{d>0} (phi(d) / d) * ([d==0 mod 6] * log(1-3x^d) +

%F   [d==3 mod 6] * (log(1-3x^d) + log(1-x^d)) / 2 +

%F   [d==2 mod 6 | d==4 mod 6] * 2*log(1-3x^d) / 3 +

%F   [d==1 mod 6 | d=5 mod 6] * (log(1-3x^d) + 3*log(1-x^d)) / 6).

%F (End)

%e 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.

%e 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

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

%t (* This Mathematica program uses Gilbert and Riordan's recurrence formula, which they recommend for calculations: *)

%t Adn[d_, n_] := Adn[d, n] = If[1==n, DivisorSum[d, x^# &],

%t   Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n-1], x] x]];

%t Join[{1},Table[SeriesCoefficient[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &] /(n (1 - x)), {x, 0, 3}], {n,40}]]  (* _Robert A. Russell_, Feb 24 2018 *)

%t From _Robert A. Russell_, May 29 2018: (Start)

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

%t mx = 40; CoefficientList[Series[1 - Sum[(EulerPhi[d] / d) Which[

%t   Divisible[d, 6], Log[1 - 3x^d], Divisible[d, 3], (Log[1 - 3x^d] +

%t   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]

%t (End)

%t (* Adnk(n,d,k) is coefficient of x^k in A(d,n)(x) from Gilbert & Riordan *)

%t 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]]

%t k=3; Join[{1},Table[Sum[DivisorSum[n,EulerPhi[#] Adnk[#,n/#,j] &],{j,k}]/n,{n,40}]] (* _Robert A. Russell_, Nov 05 2018 *)

%Y Cf. A000013, A000048, A002075.

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

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

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

%E a(0)=1 prepended by _Robert A. Russell_, Nov 05 2018