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).

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

Author

Robert A. Russell, Oct 27 2018

Keywords

• nonn
• tabl
• easy

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

Examples

			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.
		

Links

• B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.

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.

Programs

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

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).