login
A320747
Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an oriented cycle of length n using k or fewer colors (subsets).
3
1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 4, 1, 1, 2, 3, 6, 4, 1, 1, 2, 3, 7, 9, 8, 1, 1, 2, 3, 7, 11, 26, 10, 1, 1, 2, 3, 7, 12, 39, 53, 20, 1, 1, 2, 3, 7, 12, 42, 103, 146, 30, 1, 1, 2, 3, 7, 12, 43, 123, 367, 369, 56, 1, 1, 2, 3, 7, 12, 43, 126, 503, 1235, 1002, 94, 1, 1, 2, 3, 7, 12, 43, 127, 539, 2008, 4439, 2685, 180, 1, 1, 2, 3, 7, 12, 43, 127, 543, 2304, 8720, 15935, 7434, 316, 1, 1, 2, 3, 7, 12, 43, 127, 544, 2356, 11023, 38365, 58509, 20441, 596, 1
OFFSET
1,5
COMMENTS
Two color patterns are equivalent if the colors are permuted. An oriented cycle counts each chiral pair as two.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
In other words, the number of n-bead necklace 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
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
FORMULA
T(n,k) = (1/n)*Sum_{j=1..k} Sum_{d|n} phi(d)*A(d,n/d,j), where 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)).
T(n,k) = A320748(n,k) + A320742(n,k) = 2*A320748(n,k) - A305749(n,k) = A305749(n,k) + 2*A320742(n,k).
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 26 39 42 43 43 43 43 43 43 43 ...
1 10 53 103 123 126 127 127 127 127 127 127 ...
1 20 146 367 503 539 543 544 544 544 544 544 ...
1 30 369 1235 2008 2304 2356 2360 2361 2361 2361 2361 ...
1 56 1002 4439 8720 11023 11619 11697 11702 11703 11703 11703 ...
1 94 2685 15935 38365 54682 60499 61579 61684 61689 61690 61690 ...
1 180 7434 58509 173609 284071 336447 349746 351619 351766 351772 351773 ...
For T(4,2)=4, the patterns are AAAA, AAAB, AABB, and ABAB.
For T(4,3)=6, the patterns are the above four, AABC and ABAC.
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]]
Table[Sum[DivisorSum[n, EulerPhi[#] Adnk[#, n/#, j] &], {j, k-n+1}]/n, {k, 15}, {n, k}] // Flatten
PROG
(PARI) \\ R is A152175 as square matrix
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)); 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
CROSSREFS
Partial row sums of A152175.
For increasing k, columns converge to A084423.
Cf. A320748 (unoriented), A320742 (chiral), A305749 (achiral).
Sequence in context: A159936 A305749 A320748 * A348690 A238392 A144464
KEYWORD
nonn,tabl,easy
AUTHOR
Robert A. Russell, Oct 21 2018
STATUS
approved