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

1, 1, 2, 3, 7, 11, 27, 43, 107, 171, 427, 683, 1707, 2731, 6827, 10923, 27307, 43691, 109227, 174763, 436907, 699051, 1747627, 2796203, 6990507, 11184811, 27962027, 44739243, 111848107, 178956971, 447392427, 715827883, 1789569707, 2863311531, 7158278827

Offset

0,3

Comments

An equivalent color pattern is obtained when we permute the colors. Thus all permutations of ABCD are equivalent, as are AABCD and BBCDA. A color pattern is achiral if it is equivalent to its reversal. Rotations of the colors of a cycle are equivalent, so for cycles AABBCD = BBCDAA = CDAABB.

Links

Muniru A Asiru, Table of n, a(n) for n = 0..2000

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

Formula

a(n) = Sum_{j=0..4} 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 - 3x^2 + x^3) / ((1-x) * (1-4x^2)).

a(2m) = S2(m+4,4) - 8*S2(m+3,4) + 22*S2(m+2,4) - 23*S2(m+1,4) + 6*S2(m,4);

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

For m>0, a(2m) = (4 + 5*4^m) / 12.

a(2m-1) = (2 + 4^m) / 6.

a(n) = 2*A056323(n) - A124303(n) = A124303(n) - 2*A320934(n) = A056323(n) - A320934(n).

a(n) = 2*A056354(n) - A056292(n) = A056292(n) - 2*A320744(n) = A056354(n) - A320744(n).

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

a(n) = a(n-1) + 4*a(n-2) - 4*a(n-3). - Muniru A Asiru, Oct 28 2018

Example

For a(4) = 7, the achiral row patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD. The cycle patterns are AAAA, AAAB, AABB, ABAB, AABC, ABAC, and ABCD.

Maple

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

Mathematica

Table[If[EvenQ[n], StirlingS2[(n+8)/2, 4] - 8 StirlingS2[(n+6)/2, 4] + 22 StirlingS2[(n+4)/2, 4] - 23 StirlingS2[(n+2)/2, 4] + 6 StirlingS2[n/2, 4], StirlingS2[(n+7)/2, 4] - 7 StirlingS2[(n+5)/2, 4] + 16 StirlingS2[(n+3)/2, 4] - 12 StirlingS2[(n+1)/2, 4]], {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=4; Table[Sum[Ach[n, j], {j, 0, k}], {n, 0, 40}]
(* or *)
CoefficientList[Series[(1-3x^2+x^3)/((1-x)(1-4x^2)), {x, 0, 40}], x]
(* or *)
Join[{1}, LinearRecurrence[{1, 4, -4}, {1, 2, 3}, 40]]
(* or *)
Join[{1}, Table[If[EvenQ[n], (4+5 4^(n/2))/12, (2+4^((n+1)/2))/6], {n, 40}]]

Prog

(GAP) a:=[1, 2, 3];; for n in [4..40] do a[n]:=a[n-1]+4*a[n-2]-4*a[n-3]; od; Concatenation([1], a); # Muniru A Asiru, Oct 28 2018

Crossrefs

Fourth column of A305749.

Cf. A124303 (oriented), A056323 (unoriented), A320934 (chiral), for rows.

Cf. A056292 (oriented), A056354 (unoriented), A320744 (chiral), for cycles.

Sequence in context: A036651 A049454 A095055 * A107857 A107858 A214938

Adjacent sequences: A305747 A305748 A305749 * A305751 A305752 A305753

Keyword

nonn,easy

Author

Robert A. Russell, Jun 09 2018

Status

approved