|
|
A320743
|
|
Number of chiral pairs of color patterns (set partitions) in a cycle of length n using 3 or fewer colors (subsets).
|
|
4
|
|
|
0, 0, 0, 0, 0, 4, 13, 46, 144, 420, 1221, 3474, 9856, 27794, 78632, 222156, 629760, 1787440, 5087797, 14509580, 41479867, 118811286, 341009901, 980488510, 2824029648, 8146494860, 23534997912, 68084154502, 197211336576, 571915188840, 1660405181149, 4825559508106, 14038010213051, 40875403561680, 119122661856133, 347441159864556, 1014152747485696
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,6
|
|
COMMENTS
|
Two color patterns are equivalent if the colors are permuted.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
There are nonrecursive formulas, generating functions, and computer programs for A002076 and A182522, which can be used in conjunction with the first formula.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{j=1..k} -Ach(n,j)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,j), where k=3 is the maximum number of colors, 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
|
For a(6)=4, the chiral pairs are AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, and AABACC-AABBAC.
|
|
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 *)
k=3; Table[Sum[(DivisorSum[n, EulerPhi[#] Adnk[#, n/#, j]&]/n - Ach[n, j])/2, {j, k}], {n, 40}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|