A305751 Number of achiral color patterns (set partitions) in a row or cycle of length n with 5 or fewer colors (subsets).

1, 1, 2, 3, 7, 12, 30, 55, 141, 266, 688, 1313, 3407, 6532, 16970, 32595, 84721, 162846, 423348, 813973, 2116227, 4069352, 10580110, 20345735, 52898501, 101726626, 264488408, 508629033, 1322433847, 2543136972, 6612152850, 12715668475

Offset

0,3

Comments

An equivalent color pattern is obtained when we permute the colors. Thus all permutations of ABCDE are equivalent, as are AABCDE and BBCDEA. A color pattern is achiral if it is equivalent to its reversal. Rotations of the colors of a cycle are equivalent, so for cycles AABBCDE = BBCDEAA = CDEAABB.

Links

Table of n, a(n) for n=0..31.

Index entries for linear recurrences with constant coefficients, signature (1,7,-7,-10,10).

Formula

a(n) = Sum_{j=0..5} 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<2 & n==k].

G.f.: (1 - 2x)*(1+2x-2x^2-3x^3+x^4) / ((1-x)*(1-2x^2)*(1-5x^2)).

a(2m) = S2(m+5,5) - 13*S2(m+4,5) + 62*S2(m+3,5) - 130*S2(m+2,5) + 110*S2(m+1,5) - 24*S2(m,5);

a(2m-1) = S2(m+4,5) - 12*S2(m+3,5) + 52*S2(m+2,5) - 95*S2(m+1,5) + 60*S2(m,5), where S2(n,k) is the Stirling subset number A008277.

For n>0, a(2m) = (15 + 20*2^m + 13*5^m) / 60.

a(2m-1) = (3 + 2*2^m + 5^m) / 12.

a(n) = 2*A056324(n) - A056272(n) = A056272(n) - 2*A320935(n) = A056324(n) - A320935(n).

a(n) = 2*A056355(n) - A056293(n) = A056293(n) - 2*A320745(n) = A056355(n) - A320745(n).

a(n) = A057427(n) + A052551(n-2) + A304973(n) + A304974(n) + A304975(n).

a(n) = a(n-1) + 7*a(n-2) - 7*a(n-3) - 10*a(n-4) + 10*a(n-5). - Muniru A Asiru, Oct 30 2018

Example

For a(5) = 12, the achiral patterns for both rows and cycles are AAAAA, AABAA, ABABA, ABBBA, AABCC, ABACA, ABBBC, ABCAB, ABCBA, ABCBD, ABCDA, and ABCDE.

Maple

seq(coeff(series((1-2*x)*(1+2*x-2*x^2-3*x^3+x^4)/((1-x)*(1-2*x^2)*(1-5*x^2)), x, n+1), x, n), n = 0 .. 40); # Muniru A Asiru, Oct 30 2018

Mathematica

Table[If[EvenQ[n], StirlingS2[(n+10)/2, 5] - 13 StirlingS2[(n+8)/2, 5] + 62 StirlingS2[(n+6)/2, 5] - 130 StirlingS2[(n+4)/2, 5] + 110 StirlingS2[(n+2)/2, 5] - 24 StirlingS2[n/2, 5], StirlingS2[(n+9)/2, 5] - 12 StirlingS2[(n+7)/2, 5] + 52 StirlingS2[(n+5)/2, 5] - 95 StirlingS2[(n+3)/2, 5] + 60 StirlingS2[(n+1)/2, 5]], {n, 0, 40}]
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 *)
k=5; Table[Sum[Ach[n, j], {j, 0, k}], {n, 0, 40}]
CoefficientList[Series[(1-2x)(1+2x-2x^2-3x^3+x^4) / ((1- x)(1-2x^2)(1-5x^2)), {x, 0, 40}], x]
Join[{1}, LinearRecurrence[{1, 7, -7, -10, 10}, {1, 2, 3, 7, 12}, 40]]
Join[{1}, Table[If[EvenQ[n], (15 + 20 2^(n/2) + 13 5^(n/2)) / 60, (3 + 2 2^((n+1)/2) + 5^((n+1)/2)) / 12], {n, 40}]]

Crossrefs

Fifth column of A305749.

Cf. A056272 (oriented), A056324 (unoriented), A320935 (chiral), for rows.

Cf. A056293 (oriented), A056355 (unoriented), A320745 (chiral), for cycles.

Sequence in context: A339159 A297438 A111759 * A047749 A134565 A300749

Adjacent sequences: A305748 A305749 A305750 * A305752 A305753 A305754

Keyword

nonn,easy

Author

Robert A. Russell, Jun 09 2018

Status

approved