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,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

Table of n, a(n) for n=1..78.

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

Adjacent sequences: A320748 A320749 A320750 * A320752 A320753 A320754

Keyword

nonn,tabl,easy

Author

Robert A. Russell, Oct 27 2018

Status

approved