OFFSET
1,5
COMMENTS
Two color patterns are equivalent if the colors are permuted. An unoriented cycle counts each chiral pair as one, i.e., they are equivalent.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
T(n,k)=Pi_k(C_n) which is the number of non-equivalent partitions of the cycle on n vertices, with at most k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. - Bahman Ahmadi, Aug 21 2019
In other words, the number of n-bead bracelet structures using a maximum of k different colored beads. - Andrew Howroyd, Oct 30 2019
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
Andrew Howroyd, Table of n, a(n) for n = 1..1275
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
FORMULA
T(n,k) = Sum_{j=1..k} Ach(n,j)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,j), where Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k)+Ach(n-2,k-1)+Ach(n-2,k-2)) and A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)).
EXAMPLE
Array begins with T(1,1):
1 1 1 1 1 1 1 1 1 1 1 1 ...
1 2 2 2 2 2 2 2 2 2 2 2 ...
1 2 3 3 3 3 3 3 3 3 3 3 ...
1 4 6 7 7 7 7 7 7 7 7 7 ...
1 4 9 11 12 12 12 12 12 12 12 12 ...
1 8 22 33 36 37 37 37 37 37 37 37 ...
1 9 40 73 89 92 93 93 93 93 93 93 ...
1 18 100 237 322 349 353 354 354 354 354 354 ...
1 23 225 703 1137 1308 1345 1349 1350 1350 1350 1350 ...
1 44 582 2433 4704 5953 6291 6345 6350 6351 6351 6351 ...
1 63 1464 8309 19839 28228 31284 31874 31944 31949 31950 31950 ...
1 122 3960 30108 88508 144587 171283 178190 179204 179300 179306 179307 ...
For T(7,2)=9, the patterns are AAAAAAB, AAAAABB, AAAABAB, AAAABBB, AAABAAB, AAABABB, AABAABB, AABABAB, and AAABABB; only the last is chiral, paired with AAABBAB.
MATHEMATICA
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]]
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]] (* A304972 *)
Table[Sum[(DivisorSum[n, EulerPhi[#] Adnk[#, n/#, j]&]/n + Ach[n, j])/2, {j, k-n+1}], {k, 15}, {n, k}] // Flatten
PROG
Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
R(n)={Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n)={my(M=(R(n) + Ach(n))/2); for(i=2, n, M[, i] += M[, i-1]); M}
{ my(A=T(12)); for(n=1, #A, print(A[n, ])) } \\ Andrew Howroyd, Nov 03 2019
KEYWORD
AUTHOR
Robert A. Russell, Oct 21 2018
STATUS
approved