login
Number of n-bead necklace structures using a maximum of six different colored beads.
7

%I #37 Sep 04 2018 03:34:01

%S 1,2,3,7,12,43,126,539,2304,11023,54682,284071,1509852,8195029,

%T 45080666,250641895,1404374248,7917211349,44848645458,255055231763,

%U 1455247360128,8326191290585,47752990403134

%N Number of n-bead necklace structures using a maximum of six different colored beads.

%C Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

%C The second Mathematica program uses Gilbert and Riordan's recurrence formula, which they recommend for calculations. - _Robert A. Russell_, Feb 24 2018

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

%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 N. J. A. Sloane, <a href="/A000013/a000013.txt">Maple code for this and related sequences</a>

%F Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.

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

%F 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}] *

%F (S2[n/d + 5, 6) - 19*S2(n/d + 4, 6) + 138*S2(n/d + 3, 6) -

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

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

%F (End)

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

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

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

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

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

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

%t (End)

%Y Cf. A000013, A054625.

%K nonn

%O 1,2

%A _Marks R. Nester_