|
| |
|
|
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
|
|
|
|
FORMULA
|
Reference gives formula.
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 *)
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
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Better description and more terms from Mark Weston (mweston(AT)uvic.ca), Oct 06 2001
|
|
|
STATUS
|
approved
|
| |
|
|
