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

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

Author

Robert A. Russell, Oct 21 2018

Keywords

• nonn
• tabl
• easy

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

Examples

			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.
		

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
• E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Crossrefs

Partial row sums of A152175.

Columns 1-6 are A057427, A000013, A002076, A056292, A056293, A056294.

For increasing k, columns converge to A084423.

Cf. A320748 (unoriented), A320742 (chiral), A305749 (achiral).

Programs

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

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

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