login
A320647
Triangle read by rows: T(n,k) is the number of chiral pairs of cycles of length n (1) with a color pattern of exactly k colors or equivalently (2) partitioned into k nonempty subsets.
10
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 2, 0, 0, 0, 1, 12, 17, 4, 0, 0, 0, 2, 44, 84, 51, 9, 0, 0, 0, 7, 137, 388, 339, 125, 15, 0, 0, 0, 12, 408, 1586, 2010, 1054, 258, 24, 0, 0, 0, 31, 1190, 6405, 10900, 7928, 2761, 490, 35, 0, 0, 0, 58, 3416, 24927, 56700, 54383, 25680, 6392, 859, 51, 0, 0, 0, 126, 9730, 96404, 286888, 356594, 218246, 72284, 13472, 1420, 68, 0, 0
OFFSET
1,18
COMMENTS
Two color patterns are the same if the colors are permuted. A chiral cycle is different from its reverse.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
LINKS
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
FORMULA
T(n,k) = (A152175(n,k) - A304972(n,k)) / 2 = A152175(n,k) - A152176(n,k) = A152176(n,k) - A304972(n,k).
T(n,k) = -Ach(n,k)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,k), 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)).
EXAMPLE
The triangle begins with T(1,1):
0;
0, 0;
0, 0, 0;
0, 0, 0, 0;
0, 0, 0, 0, 0;
0, 0, 4, 2, 0, 0;
0, 1, 12, 17, 4, 0, 0;
0, 2, 44, 84, 51, 9, 0, 0;
0, 7, 137, 388, 339, 125, 15, 0, 0;
0, 12, 408, 1586, 2010, 1054, 258, 24, 0, 0;
0, 31, 1190, 6405, 10900, 7928, 2761, 490, 35, 0, 0;
0, 58, 3416, 24927, 56700, 54383, 25680, 6392, 859, 51, 0, 0;
0, 126, 9730, 96404, 286888, 356594, 218246, 72284, 13472, 1420, 68, 0, 0;
...
For T(6,3)=4, the chiral pairs are AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, and AABACC-AABBAC.
For T(6,4)=2, the chiral pairs are AABACD-AABCAD and AABCBD-AABCDC.
MATHEMATICA
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 *)
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[DivisorSum[n, EulerPhi[#]Adnk[#, n/#, k]&]/(2n)-Ach[n, k]/2, {n, 12}, {k, n}] // Flatten
PROG
(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)={(R(n) - Ach(n))/2}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019
CROSSREFS
Row sums are A320749.
Cf. A152175 (oriented), A152176 (unoriented), A304972 (achiral).
Sequence in context: A105087 A238012 A324802 * A028572 A107492 A159257
KEYWORD
nonn,tabl,easy
AUTHOR
Robert A. Russell, Oct 18 2018
STATUS
approved