OFFSET
1,8
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.
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.
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.
EXAMPLE
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.
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
PROG
(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
CROSSREFS
KEYWORD
AUTHOR
Robert A. Russell, May 22 2018
STATUS
approved