|
| |
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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)).
|
|
|
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
|
For increasing k, columns converge to A084423.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
