A320748 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented 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, 22, 9, 1, 1, 2, 3, 7, 12, 33, 40, 18, 1, 1, 2, 3, 7, 12, 36, 73, 100, 23, 1, 1, 2, 3, 7, 12, 37, 89, 237, 225, 44, 1, 1, 2, 3, 7, 12, 37, 92, 322, 703, 582, 63, 1, 1, 2, 3, 7, 12, 37, 93, 349, 1137, 2433, 1464, 122, 1, 1, 2, 3, 7, 12, 37, 93, 353, 1308, 4704, 8309, 3960, 190, 1, 1, 2, 3, 7, 12, 37, 93, 354, 1345, 5953, 19839, 30108, 10585, 362, 1
Offset: 1
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 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.
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.
Crossrefs
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]] 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
-
PARI
\\ Ach is A304972 and R is A152175 as square matrices. 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
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)).
Comments