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.
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
Examples
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
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
Crossrefs
Programs
-
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 *)
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)
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
Comments