A305749 T(n,k) is the number of achiral color patterns (set partitions) in a row or loop of length n with k or fewer colors (sets).

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 4, 1, 1, 2, 3, 6, 4, 1, 1, 2, 3, 7, 9, 8, 1, 1, 2, 3, 7, 11, 18, 8, 1, 1, 2, 3, 7, 12, 27, 27, 16, 1, 1, 2, 3, 7, 12, 30, 43, 54, 16, 1, 1, 2, 3, 7, 12, 31, 55, 107, 81, 32, 1, 1, 2, 3, 7, 12, 31, 58, 141, 171, 162, 32, 1, 1, 2, 3, 7, 12, 31, 59, 159, 266, 427, 243, 64, 1, 1, 2, 3, 7, 12, 31, 59, 163, 312, 688, 683, 486, 64, 1

Offset

1,5

Comments

An equivalent color pattern is obtained when we permute the colors. Thus all permutations of ABC are equivalent, as are AAABB and BBBAA. A color pattern is achiral if it is equivalent to its reversal. Rotations of the colors of a loop are equivalent, so for loops AAABCB = BAAABC = CBAAAB.

Links

Table of n, a(n) for n=1..105.

Formula

T(n,k) = Sum_{j=0..k} Ach(n,j), where Ach(n,k) = [n>1] * (k*T(n-2,k) + T(n-2,k-1) + T(n-2,k-2)) + [0 <= n <= 1 & n==k].

T(n,k) = Sum_{j=1..k} A304972(n,j).

Example

The array begins at T(1,1):
1  1   1    1    1     1     1     1     1     1     1     1     1 ...
1  2   2    2    2     2     2     2     2     2     2     2     2 ...
1  2   3    3    3     3     3     3     3     3     3     3     3 ...
1  4   6    7    7     7     7     7     7     7     7     7     7 ...
1  4   9   11   12    12    12    12    12    12    12    12    12 ...
1  8  18   27   30    31    31    31    31    31    31    31    31 ...
1  8  27   43   55    58    59    59    59    59    59    59    59 ...
1 16  54  107  141   159   163   164   164   164   164   164   164 ...
1 16  81  171  266   312   334   338   339   339   339   339   339 ...
1 32 162  427  688   883   963   993   998   999   999   999   999 ...
1 32 243  683 1313  1774  2069  2169  2204  2209  2210  2210  2210 ...
1 64 486 1707 3407  5103  6119  6634  6789  6834  6840  6841  6841 ...
1 64 729 2731 6532 10368 13524 15080 15790 15975 16026 16032 16033 ...
a(n) are the terms of this array read by antidiagonals.
For T(4,3)=6, the achiral pattern rows are AAAA, AABB, ABAB, ABBA, ABBC, and ABCA. The achiral pattern loops are AAAA, AAAB, AABB, ABAB, AABC, and ABAC.

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[Sum[Ach[n, j], {j, 1, k - n + 1}], {k, 1, 15}, {n, 1, k}] // Flatten

Crossrefs

Columns 1-6 are A057427, A016116, A182522, A305750, A305751, and A305752.

Columns converge to the right to A080107.

Sequence in context: A323767 A357824 A159936 * A320748 A320747 A348690

Adjacent sequences: A305746 A305747 A305748 * A305750 A305751 A305752

Keyword

nonn,tabl,easy

Author

Robert A. Russell, Jun 09 2018

Status

approved