login
A320751
Array read by antidiagonals: T(n,k) is the number of chiral pairs of color patterns (set partitions) in a row of length n using k or fewer colors (subsets).
7
0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 0, 0, 1, 4, 6, 0, 0, 0, 1, 4, 16, 12, 0, 0, 0, 1, 4, 20, 52, 28, 0, 0, 0, 1, 4, 20, 80, 169, 56, 0, 0, 0, 1, 4, 20, 86, 336, 520, 120, 0, 0, 0, 1, 4, 20, 86, 400, 1344, 1600, 240, 0, 0, 0, 1, 4, 20, 86, 409, 1852, 5440, 4840, 496, 0
OFFSET
1,14
COMMENTS
Two color patterns are equivalent if the colors are permuted.
A chiral row is not equivalent to its reverse.
T(n,k)=Xi_k(P_n) which is the number of non-equivalent distinguishing partitions of the path 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. A distinguishing partition is a partition of the vertex set of G such that no nontrivial automorphism of G can preserve it. - Bahman Ahmadi, Sep 02 2019
LINKS
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
FORMULA
T(n,k) = Sum_{j=1..k} (S2(n,j) - Ach(n,j)) / 2, where S2 is the Stirling subset number A008277 and 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)).
T(n,k) = (A278984(k,n) - A305749(n,k)) / 2 = A278984(k,n) - A320750(n,k) = A320750(n,k) - A305749(n,k).
T(n,k) = Sum_{j=1..k} A320525(n,j).
EXAMPLE
Array begins with T(1,1):
0 0 0 0 0 0 0 0 0 0 ...
0 0 0 0 0 0 0 0 0 0 ...
0 1 1 1 1 1 1 1 1 1 ...
0 2 4 4 4 4 4 4 4 4 ...
0 6 16 20 20 20 20 20 20 20 ...
0 12 52 80 86 86 86 86 86 86 ...
0 28 169 336 400 409 409 409 409 409 ...
0 56 520 1344 1852 1976 1988 1988 1988 1988 ...
0 120 1600 5440 8868 10168 10388 10404 10404 10404 ...
0 240 4840 21760 42892 54208 57108 57468 57488 57488 ...
0 496 14641 87296 210346 299859 331705 337595 338155 338180 ...
0 992 44044 349184 1038034 1699012 2012202 2091458 2102518 2103348 ...
For T(4,2)=2, the chiral pairs are AAAB-ABBB and AABA-ABAA.
For T(4,3)=4, the above, AABC-ABCC, and ABAC-ABCB.
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 *)
Table[Sum[StirlingS2[n, j] - Ach[n, j], {j, k-n+1}]/2, {k, 15}, {n, k}] // Flatten
CROSSREFS
Columns 1-6 are A000004, A122746(n-3), A107767(n-1), A320934, A320935, A320936.
As k increases, columns converge to A320937.
Cf. transpose of A278984 (oriented), A320750 (unoriented), A305749 (achiral).
Partial column sums of A320525.
Sequence in context: A187080 A301342 A226369 * A263764 A325668 A070202
KEYWORD
nonn,tabl,easy
AUTHOR
Robert A. Russell, Oct 27 2018
STATUS
approved