|
|
A056294
|
|
Number of n-bead necklace structures using a maximum of six different colored beads.
|
|
7
|
|
|
1, 2, 3, 7, 12, 43, 126, 539, 2304, 11023, 54682, 284071, 1509852, 8195029, 45080666, 250641895, 1404374248, 7917211349, 44848645458, 255055231763, 1455247360128, 8326191290585, 47752990403134
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.
The second Mathematica program uses Gilbert and Riordan's recurrence formula, which they recommend for calculations. - Robert A. Russell, Feb 24 2018
|
|
REFERENCES
|
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]
|
|
LINKS
|
|
|
FORMULA
|
Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
a(n) = (1/n)*Sum_{d|n} phi(d) * ([d==0 mod 60] * (6*S2(n/d + 5, 6) - 90*S2(n/d + 4, 6) + 510*S2(n/d + 3, 6) - 1350*S2(n/d + 2, 6) + 1644*S2(n/d + 1, 6) - 720*S2(n/d, 6)) + [d==30 mod 60] * (5*S2(n/d + 5, 6) - 77*S2(n/d + 4, 6) + 451*S2(n/d + 3, 6) - 1243*S2(n/d + 2, 6) + 1584*S2(n/d + 1, 6) - 720*S2(n/d, 6)) + [d==20 mod 60 | d==40 mod 60] * (4*S2(n/d + 5, 6) - 62*S2(n/d + 4, 6) + 364*S2(n/d + 3, 6) - 998*S2(n/d + 2, 6) + 1252*S2(n/d + 1, 6) - 560*S2(n/d, 6)) + [d==15 mod 60 | d==45 mod 60] * (3*S2(n/d + 5, 6) - 48*S2(n/d + 4, 6) + 291*S2(n/d + 3, 6) - 825*S2(n/d + 2, 6) + 1074*S2(n/d + 1, 6) - 495*S2(n/d, 6)) + [d mod 60 in {12,24,36,48}] * (5*S2(n/d + 5, 6) - 76*S2(n/d + 4, 6) + 439*S2(n/d + 3, 6) - 1196*S2(n/d + 2, 6) + 1524*S2(n/d + 1, 6) - 720*S2(n/d, 6)) + [d=10 mod 60 | d==50 mod 60] * (3*S2(n/d +5 , 6) - 49*S2(n/d + 4, 6) + 305*S2(n/d + 3, 6) - 891*S2(n/d + 2, 6) + 1192*S2(n/d + 1, 6) - 560*S2(n/d, 6)) + [d mod 60 in {6,18,42,54}] * (4*S2(n/d + 5, 6) - 63*S2(n/d + 4, 6) + 380*S2(n/d + 3, 6) - 1089*S2(n/d + 2, 6) + 1464*S2(n/d + 1, 6) - 720*S2(n/d, 6)) + [d mod 60 in {5,25,35,55}] * (2*S2(n/d + 5, 6) - 33*S2(n/d + 4, 6) + 209*S2(n/d + 3, 6) - 629*S2(n/d + 2, 6) + 886*S2(n/d + 1, 6) - 455*S2(n/d, 6)) + [d mod 60 in {4,8,16,28,32,44,52,56}] * (3*S2(n/d + 5, 6) - 48*S2(n/d + 4, 6) + 293*S2(n/d + 3, 6) - 844*S2(n/d + 2, 6) + 1132*S2(n/d + 1, 6) - 560*S2(n/d, 6)) + [d mod 60 in {3,9,21,27,33,39,51,57}] * (2*S2(n/d + 5, 6) - 34*S2(n/d + 4, 6) + 220*S2(n/d + 3, 6) - 671*S2(n/d + 2, 6) + 954*S2(n/d + 1, 6) - 495*S2(n/d, 6)) + [d mod 60 in {2,14,22,26,34,38,46,58}] * (2*S2(n/d + 5, 6) - 35*S2(n/d + 4, 6) + 234*S2(n/d + 3, 6) - 737*S2(n/d + 2, 6) + 1072*S2(n/d + 1, 6) - 560*S2(n/d, 6)) + [d mod 60 in {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}] *
(S2[n/d + 5, 6) - 19*S2(n/d + 4, 6) + 138*S2(n/d + 3, 6) -
475*S2(n/d + 2, 6) + 766*S2(n/d + 1,6) - 455*S2(n/d, 6))), 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-6x^d) + [d==30 mod 60] * (3*log(1-6x^d) + log(1-2x^d)) / 4 + [d==20 mod 60 | d==40 mod 60] * (5*log(1-6x^d) + 2*log(1-3x^d)) / 9 + [d==15 mod 60 | d==45 mod 60] * (5*log(1-6x^d) + 3*log(1-4x^d) + 3*log(1-2x^d)) / 16 + [d mod 60 in {12,24,36,48}] * (4*log(1-6x^d) + log(1-x^d)) / 5 + [d=10 mod 60 | d==50 mod 60] * (11*log(1-6x^d) + 8*log(1-3x^d) + 9*log(1-2x^d)) / 36 + [d mod 60 in {6,18,42,54}] * (11*log(1-6x^d) + 5*log(1-2x^d) + 4*log(1-x^d)) / 20 + [d mod 60 in {5,25,35,55}] * (29*log(1-6x^d) + 3*log(1-4x^d) + 8*log(1-3x^d) + 27*log(1-2x^d) + 24*log(1-x^d)) / 144 + [d mod 60 in {4,8,16,28,32,44,52,56}] * (16*log(1-6x^d) + 10*log(1-3x^d) + 9*log(1-x^d)) / 45 + [d mod 60 in {3,9,21,27,33,39,51,57}] * (9*log(1-6x^d) + 15*log(1-4x^d) + 15*log(1-2x^d) + 16*log(1-x^d)) / 80 + [d mod 60 in {2,14,22,26,34,38,46,58}] * (19*log(1-6x^d) + 40*log(1-3x^d) + 45*log(1-2x^d) + 36*log(1-x^d)) / 180 + [d mod 60 in {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}] * (log(1-6x^d) + 15*log(1-4x^d) + 40*log(1-3x^d) + 135*log(1-2x^d) + 264*log(1-x^d)) / 720).
(End)
|
|
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, 6]; Table[Print[an = a[n]]; an, {n, 1, 23}] (* Jean-François Alcover, Oct 04 2013, after N. J. A. Sloane's Maple code *)
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, 6}], {n, 1, 40}] (* Robert A. Russell, Feb 24 2018 *)
Table[(1/n) DivisorSum[n, EulerPhi[#] Which[Divisible[#, 60], 6 StirlingS2[n/#+5, 6] - 90 StirlingS2[n/#+4, 6] + 510 StirlingS2[n/#+3, 6] - 1350 StirlingS2[n/#+2, 6] + 1644 StirlingS2[n/#+1, 6] - 720 StirlingS2[n/#, 6], Divisible[#, 30], 5 StirlingS2[n/#+5, 6] - 77 StirlingS2[n/#+4, 6] + 451 StirlingS2[n/#+3, 6] - 1243 StirlingS2[n/#+2, 6] + 1584 StirlingS2[n/#+1, 6] - 720 StirlingS2[n/#, 6], Divisible[#, 20], 4 StirlingS2[n/#+5, 6] - 62 StirlingS2[n/#+4, 6] + 364 StirlingS2[n/#+3, 6] - 998 StirlingS2[n/#+2, 6] + 1252 StirlingS2[n/#+1, 6] - 560 StirlingS2[n/#, 6], Divisible[#, 15], 3 StirlingS2[n/#+5, 6] - 48 StirlingS2[n/#+4, 6] + 291 StirlingS2[n/#+3, 6] - 825 StirlingS2[n/#+2, 6] + 1074 StirlingS2[n/#+1, 6] - 495 StirlingS2[n/#, 6], Divisible[#, 12], 5 StirlingS2[n/#+5, 6] - 76 StirlingS2[n/#+4, 6] + 439 StirlingS2[n/#+3, 6] - 1196 StirlingS2[n/#+2, 6] + 1524 StirlingS2[n/#+1, 6] - 720 StirlingS2[n/#, 6], Divisible[#, 10], 3 StirlingS2[n/#+5, 6] - 49 StirlingS2[n/#+4, 6] + 305 StirlingS2[n/#+3, 6] - 891 StirlingS2[n/#+2, 6] + 1192 StirlingS2[n/#+1, 6] - 560 StirlingS2[n/#, 6], Divisible[#, 6], 4 StirlingS2[n/#+5, 6] - 63 StirlingS2[n/#+4, 6] + 380 StirlingS2[n/#+3, 6] - 1089 StirlingS2[n/#+2, 6] + 1464 StirlingS2[n/#+1, 6] - 720 StirlingS2[n/#, 6], Divisible[#, 5], 2 StirlingS2[n/#+5, 6] - 33 StirlingS2[n/#+4, 6] + 209 StirlingS2[n/#+3, 6] - 629 StirlingS2[n/#+2, 6] + 886 StirlingS2[n/#+1, 6] - 455 StirlingS2[n/#, 6], Divisible[#, 4], 3 StirlingS2[n/#+5, 6] - 48 StirlingS2[n/#+4, 6] + 293 StirlingS2[n/#+3, 6] - 844 StirlingS2[n/#+2, 6] + 1132 StirlingS2[n/#+1, 6] - 560 StirlingS2[n/#, 6], Divisible[#, 3], 2 StirlingS2[n/#+5, 6] - 34 StirlingS2[n/#+4, 6] + 220 StirlingS2[n/#+3, 6] - 671 StirlingS2[n/#+2, 6] + 954 StirlingS2[n/#+1, 6] - 495 StirlingS2[n/#, 6], Divisible[#, 2], 2 StirlingS2[n/#+5, 6] - 35 StirlingS2[n/#+4, 6] + 234 StirlingS2[n/#+3, 6] - 737 StirlingS2[n/#+2, 6] + 1072 StirlingS2[n/#+1, 6] - 560 StirlingS2[n/#, 6], True, StirlingS2[n/#+5, 6] - 19 StirlingS2[n/#+4, 6] + 138 StirlingS2[n/#+3, 6] - 475 StirlingS2[n/#+2, 6] + 766 StirlingS2[n/#+1, 6] - 455 StirlingS2[n/#, 6]] &], {n, 1, 40}]
mx = 40; Drop[CoefficientList[Series[1-Sum[(EulerPhi[d] / d) Which[ Divisible[d, 60], Log[1-6x^d], Divisible[d, 30], (3 Log[1-6x^d] + Log[1-2x^d]) / 4, Divisible[d, 20], (5 Log[1-6x^d] + 2 Log[1-3x^d]) / 9, Divisible[d, 15], (5 Log[1-6x^d] + 3 Log[1-4x^d] + 3 Log[1-2x^d]) / 16, Divisible[d, 12], (4 Log[1-6x^d] + Log[1-x^d]) / 5, Divisible[d, 10], (11 Log[1-6x^d] + 8 Log[1-3x^d] + 9 Log[1-2x^d]) / 36, Divisible[d, 6], (11 Log[1-6x^d] + 5 Log[1-2x^d] + 4 Log[1-x^d]) / 20, Divisible[d, 5], (29 Log[1-6x^d] + 3 Log[1-4x^d] + 8 Log[1-3x^d] + 27 Log[1-2x^d] + 24 Log[1-x^d]) / 144, Divisible[d, 4], (16 Log[1-6x^d] + 10 Log[1-3x^d] + 9 Log[1-x^d]) / 45, Divisible[d, 3], (9 Log[1-6x^d] + 15 Log[1-4x^d] + 15 Log[1-2x^d] + 16 Log[1-x^d]) / 80, Divisible[d, 2], (19 Log[1-6x^d] + 40 Log[1-3x^d] + 45 Log[1-2x^d] + 36 Log[1-x^d]) / 180, True, (Log[1-6 x^d] + 15 Log[1-4 x^d] + 40 Log[1-3 x^d] + 135 Log[1-2 x^d] + 264 Log[1-x^d]) / 720], {d, 1, mx}], {x, 0, mx}], x], 1]
(End)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|