A320525 Triangle read by rows: T(n,k) = number of chiral pairs of color patterns (set partitions) in a row of length n using exactly k colors (subsets).

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 6, 10, 4, 0, 0, 12, 40, 28, 6, 0, 0, 28, 141, 167, 64, 9, 0, 0, 56, 464, 824, 508, 124, 12, 0, 0, 120, 1480, 3840, 3428, 1300, 220, 16, 0, 0, 240, 4600, 16920, 21132, 11316, 2900, 360, 20, 0, 0, 496, 14145, 72655, 123050, 89513, 31846, 5890, 560, 25, 0, 0, 992, 43052, 305140, 688850, 660978, 313190, 79256, 11060, 830, 30, 0

Offset

1,8

Comments

Two color patterns are equivalent if we permute the colors. Chiral color patterns must not be equivalent if we reverse the order of the pattern.

If the top entry of the triangle is changed from 0 to 1, this is the number of non-equivalent distinguishing partitions of the path on n vertices (n >= 1) with exactly k parts (1 <= k <= n). - Bahman Ahmadi, Aug 21 2019

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

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

Formula

T(n,k) = (S2(n,k) - A(n,k))/2, where S2 is the Stirling subset number A008277 and A(n,k) = [n>1] * (k*A(n-2,k) + A(n-2,k-1) + A(n-2,k-2)) + [n<2 & n==k & n>=0].

T(n,k) = (A008277(n,k) - A304972(n,k)) / 2 = A008277(n,k) - A284949(n,k) = A284949(n,k) - A304972(n,k).

Example

Triangle begins with T(1,1):
  0;
  0,   0;
  0,   1,     0;
  0,   2,     2,      0;
  0,   6,    10,      4,      0;
  0,  12,    40,     28,      6,      0;
  0,  28,   141,    167,     64,      9,      0;
  0,  56,   464,    824,    508,    124,     12,     0;
  0, 120,  1480,   3840,   3428,   1300,    220,    16,     0;
  0, 240,  4600,  16920,  21132,  11316,   2900,   360,    20,   0;
  0, 496, 14145,  72655, 123050,  89513,  31846,  5890,   560,  25, 0;
  0, 992, 43052, 305140, 688850, 660978, 313190, 79256, 11060, 830, 30, 0;
  ...
For T(3,2)=1, the chiral pair is AAB-ABB.  For T(4,2)=2, the chiral pairs are AAAB-ABBB and AABA-ABAA.  For T(5,2)=6, the chiral pairs are AAAAB-ABBBB, AAABA-ABAAA, AAABB-AABBB, AABAB-ABABB, AABBA-ABBAA, and ABAAB-ABBAB.

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[(StirlingS2[n, k] - Ach[n, k])/2, {n, 1, 12}, {k, 1, n}] // Flatten

Prog

(PARI) \\ here Ach is A304972 as square matrix.
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}
T(n)={(matrix(n, n, i, k, stirling(i, k, 2)) - Ach(n))/2}
{ my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 18 2019

Crossrefs

Columns 1-6 are A000004, A122746(n-2), A320526, A320527, A320528, A320529.

Row sums are A320937.

Cf. A008277 (oriented), A284949 (unoriented), A304972 (achiral).

Sequence in context: A296148 A121178 A175917 * A357647 A069971 A167291

Adjacent sequences: A320522 A320523 A320524 * A320526 A320527 A320528

Keyword

nonn,tabl,easy

Author

Robert A. Russell, Oct 14 2018

Status

approved