|
|
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).
|
|
47
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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(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
|
A305008 has coefficients that determine the function and generating function for each column.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|