|
%I #23 Nov 05 2019 05:52:52
%S 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,
%T 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,
%U 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
%N 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).
%C Two color patterns are equivalent if the colors are permuted. An unoriented cycle counts each chiral pair as one, i.e., they are equivalent.
%C Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
%C 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
%C In other words, the number of n-bead bracelet structures using a maximum of k different colored beads. - _Andrew Howroyd_, Oct 30 2019
%D 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]
%H Andrew Howroyd, <a href="/A320748/b320748.txt">Table of n, a(n) for n = 1..1275</a>
%H B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, <a href="https://arxiv.org/abs/1910.12102">Number of Distinguishing Colorings and Partitions</a>, arXiv:1910.12102 [math.CO], 2019.
%H E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.
%F 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)).
%F T(n,k) = (A320747(n,k) + A305749(n,k)) / 2 = A320747(n,k) - A320742(n,k) = A320742(n,k) + A305749(n,k).
%e Array begins with T(1,1):
%e 1 1 1 1 1 1 1 1 1 1 1 1 ...
%e 1 2 2 2 2 2 2 2 2 2 2 2 ...
%e 1 2 3 3 3 3 3 3 3 3 3 3 ...
%e 1 4 6 7 7 7 7 7 7 7 7 7 ...
%e 1 4 9 11 12 12 12 12 12 12 12 12 ...
%e 1 8 22 33 36 37 37 37 37 37 37 37 ...
%e 1 9 40 73 89 92 93 93 93 93 93 93 ...
%e 1 18 100 237 322 349 353 354 354 354 354 354 ...
%e 1 23 225 703 1137 1308 1345 1349 1350 1350 1350 1350 ...
%e 1 44 582 2433 4704 5953 6291 6345 6350 6351 6351 6351 ...
%e 1 63 1464 8309 19839 28228 31284 31874 31944 31949 31950 31950 ...
%e 1 122 3960 30108 88508 144587 171283 178190 179204 179300 179306 179307 ...
%e 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.
%t 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]]
%t 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 *)
%t Table[Sum[(DivisorSum[n, EulerPhi[#] Adnk[#,n/#,j]&]/n + Ach[n,j])/2, {j,k-n+1}], {k,15}, {n,k}] // Flatten
%o (PARI) \\ Ach is A304972 and R is A152175 as square matrices.
%o 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}
%o 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))]))}
%o T(n)={my(M=(R(n) + Ach(n))/2); for(i=2, n, M[,i] += M[,i-1]); M}
%o { my(A=T(12)); for(n=1, #A, print(A[n, ])) } \\ _Andrew Howroyd_, Nov 03 2019
%Y Partial row sums of A152176.
%Y Columns 1-6 are A057427, A000011, A056353, A056354, A056355, A056356
%Y For increasing k, columns converge to A084708.
%Y Cf. A320747 (oriented), A320742 (chiral), A305749 (achiral).
%K nonn,tabl,easy
%O 1,5
%A _Robert A. Russell_, Oct 21 2018
|
