A304972 Triangle read by rows of achiral color patterns (set partitions) for a row or loop of length n. T(n,k) is the number using exactly k colors (sets).

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 10, 9, 3, 1, 1, 7, 19, 16, 12, 3, 1, 1, 15, 38, 53, 34, 18, 4, 1, 1, 15, 65, 90, 95, 46, 22, 4, 1, 1, 31, 130, 265, 261, 195, 80, 30, 5, 1, 1, 31, 211, 440, 630, 461, 295, 100, 35, 5, 1, 1, 63, 422, 1221, 1700, 1696, 1016, 515, 155, 45, 6, 1, 1, 63, 665, 2002

Offset: 1

Author

Robert A. Russell, May 22 2018

Keywords

• nonn
• tabl
• easy

Comments

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

Examples

			Triangle begins:
1;
1,   1;
1,   1,    1;
1,   3,    2,    1;
1,   3,    5,    2,     1;
1,   7,   10,    9,     3,     1;
1,   7,   19,   16,    12,     3,     1;
1,  15,   38,   53,    34,    18,     4,    1;
1,  15,   65,   90,    95,    46,    22,    4,    1;
1,  31,  130,  265,   261,   195,    80,   30,    5,    1;
1,  31,  211,  440,   630,   461,   295,  100,   35,    5,   1;
1,  63,  422, 1221,  1700,  1696,  1016,  515,  155,   45,   6,  1
1,  63,  665, 2002,  3801,  3836,  3156, 1556,  710,  185,  51,  6, 1;
1, 127, 1330, 5369, 10143, 13097, 10508, 6832, 2926, 1120, 266, 63, 7, 1;
For T(4,2)=3, the row patterns are AABB, ABAB, and ABBA.  The loop patterns are AAAB, AABB, and ABAB.
For T(5,3)=5, the color patterns for both rows and loops are AABCC, ABACA, ABBBC, ABCAB, and ABCBA.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275
• Ira Gessel, What is the number of achiral color patterns for a row of n colors containing k different colors?, mathoverflow, Jan 30 2018.
• Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.

Crossrefs

Columns 1-6 are A057427, A052551(n-2), A304973, A304974, A304975, A304976.

A305008 has coefficients that determine the function and generating function for each column.

Row sums are A080107.

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]]
Table[Ach[n, k], {n, 1, 15}, {k, 1, n}] // Flatten
Ach[n_, k_] := Ach[n, k] = Which[0==k, Boole[0==n], 1==k, Boole[n>0],
  OddQ[n], Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1], {i, 0, (n-1)/2}],
  True, Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1]
  + 2^i Ach[n-2-2i, k-2]), {i, 0, n/2-1}]]
Table[Ach[n, k], {n, 1, 15}, {k, 1, n}] // Flatten

PARI

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}
{ my(A=Ach(10)); for(n=1, #A, print(A[n,1..n])) } \\ Andrew Howroyd, Sep 18 2019

Formula

T(n,k) = [n>1] * (k*T(n-2,k) + T(n-2,k-1) + T(n-2,k-2)) + [n<2 & n==k & n>=0].

T(2m-1,k) = A140735(m,k).

T(2m,k) = A293181(m,k).

T(n,k) = [k==0 & n==0] + [k==1 & n>0]

+ [k>1 & n==1 mod 2] * Sum_{i=0..(n-1)/2} (C((n-1)/2, i) * T(n-1-2i, k-1))

+ [k>1 & n==0 mod 2] * Sum_{i=0..(n-2)/2} (C((n-2)/2, i) * (T(n-2-2i, k-1)

+ 2^i * T(n-2-2i, k-2))) where C(n,k) is a binomial coefficient.