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

%I #29 Mar 31 2022 21:59:36

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

%T 53,34,18,4,1,1,15,65,90,95,46,22,4,1,1,31,130,265,261,195,80,30,5,1,

%U 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

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

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

%H Andrew Howroyd, <a href="/A304972/b304972.txt">Table of n, a(n) for n = 1..1275</a>

%H Ira Gessel, <a href="https://mathoverflow.net/q/291720">What is the number of achiral color patterns for a row of n colors containing k different colors?</a>, mathoverflow, Jan 30 2018.

%H Juan B. Gil and Luiz E. Lopez, <a href="https://arxiv.org/abs/2203.10589">Enumeration of symmetric arc diagrams</a>, arXiv:2203.10589 [math.CO], 2022.

%F 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].

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

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

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

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

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

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

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 1, 1;

%e 1, 3, 2, 1;

%e 1, 3, 5, 2, 1;

%e 1, 7, 10, 9, 3, 1;

%e 1, 7, 19, 16, 12, 3, 1;

%e 1, 15, 38, 53, 34, 18, 4, 1;

%e 1, 15, 65, 90, 95, 46, 22, 4, 1;

%e 1, 31, 130, 265, 261, 195, 80, 30, 5, 1;

%e 1, 31, 211, 440, 630, 461, 295, 100, 35, 5, 1;

%e 1, 63, 422, 1221, 1700, 1696, 1016, 515, 155, 45, 6, 1

%e 1, 63, 665, 2002, 3801, 3836, 3156, 1556, 710, 185, 51, 6, 1;

%e 1, 127, 1330, 5369, 10143, 13097, 10508, 6832, 2926, 1120, 266, 63, 7, 1;

%e For T(4,2)=3, the row patterns are AABB, ABAB, and ABBA. The loop patterns are AAAB, AABB, and ABAB.

%e For T(5,3)=5, the color patterns for both rows and loops are AABCC, ABACA, ABBBC, ABCAB, and ABCBA.

%t Ach[n_, k_] := Ach[n, k] = If[n < 2, Boole[n == k && n >= 0],

%t k Ach[n - 2, k] + Ach[n - 2, k - 1] + Ach[n - 2, k - 2]]

%t Table[Ach[n, k], {n, 1, 15}, {k, 1, n}] // Flatten

%t Ach[n_, k_] := Ach[n, k] = Which[0==k, Boole[0==n], 1==k, Boole[n>0],

%t OddQ[n], Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1], {i, 0, (n-1)/2}],

%t True, Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1]

%t + 2^i Ach[n-2-2i, k-2]), {i, 0, n/2-1}]]

%t Table[Ach[n, k], {n, 1, 15}, {k, 1, n}] // Flatten

%o (PARI)

%o 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}

%o { my(A=Ach(10)); for(n=1, #A, print(A[n,1..n])) } \\ _Andrew Howroyd_, Sep 18 2019

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

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

%Y Row sums are A080107.

%K nonn,tabl,easy

%O 1,8

%A _Robert A. Russell_, May 22 2018