A304974 -id:A304974 - cp's OEIS frontend

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

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

Offset: 1

Robert A. Russell, May 22 2018

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

			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.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Ira Gessel, What is the number of achiral color patterns for a row of n colors containing k different colors?, mathoverflow, Jan 30 2018.
Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.

Columns 1-6 are A057427, A052551(n-2), A304973, A304974, A304975, A304976.
A305008 has coefficients that determine the function and generating function for each column.
Row sums are A080107.

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

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

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(2m-1,k) = A140735(m,k).
T(2m,k) = A293181(m,k).
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.

A056328 Number of reversible string structures with n beads using exactly four different colors.

Original entry on oeis.org

0, 0, 0, 1, 6, 37, 183, 877, 3930, 17185, 73095, 306361, 1267266, 5198557, 21182343, 85910917, 347187210, 1399451545, 5629911015, 22616256721, 90754855026, 363890126677, 1458172596903, 5840531635357, 23385650196090

Offset: 1

Marks R. Nester

nonn

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure.

Number of set partitions for an unoriented row of n elements using exactly four different elements. An unoriented row is equivalent to its reverse. - Robert A. Russell, Oct 14 2018

			For a(5)=6, the color patterns are ABCDA, ABCBD, AABCD, ABACD, ABCAD, and ABBCD. The first two are achiral. - _Robert A. Russell_, Oct 14 2018

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Index entries for linear recurrences with constant coefficients, signature (8, -12, -44, 121, 12, -228, 144).

Column 4 of A284949.
Cf. A056311.
Cf. A000453 (oriented), A320527 (chiral), A304974 (achiral).

k=4; Table[(StirlingS2[n,k] + If[EvenQ[n], StirlingS2[n/2+2,4] - StirlingS2[n/2+1,4] - 2StirlingS2[n/2,4], 2StirlingS2[(n+3)/2,4] - 4StirlingS2[(n+1)/2,4]])/2, {n,30}] (* Robert A. Russell, Oct 14 2018 *)
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]]
k = 4; Table[(StirlingS2[n, k] + Ach[n, k])/2, {n, 1, 30}] (* Robert A. Russell, Oct 14 2018 *)
LinearRecurrence[{8, -12, -44, 121, 12, -228, 144}, {0, 0, 0, 1, 6, 37, 183}, 30] (* Robert A. Russell, Oct 14 2018 *)

a(n) = A056323(n) - A001998(n-1).
Empirical g.f.: -x^4*(3*x^3 + x^2 - 2*x + 1) / ((x-1)*(2*x-1)*(2*x+1)*(3*x-1)*(4*x-1)*(3*x^2-1)). - Colin Barker, Nov 25 2012
From Robert A. Russell, Oct 14 2018: (Start)
a(n) = (S2(n,k) + A(n,k))/2, where k=4 is the number of colors (sets), S2 is the Stirling subset number A008277 and A(n,k) = [n>1] * (k*A(n-2,k) + A(n-2,k-1) + A(n-2,k-2)) + [n<2 & n==k & n>=0].
a(n) = (A000453(n) + A304974(n)) / 2 = A000453(n) - A320527(n) = A320527(n) + A304974(n). (End)

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

Original entry on oeis.org

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

Robert A. Russell, Jun 09 2018

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.

			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.

Muniru A Asiru, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1,4,-4).

Fourth column of A305749.
Cf. A124303 (oriented), A056323 (unoriented), A320934 (chiral), for rows.
Cf. A056292 (oriented), A056354 (unoriented), A320744 (chiral), for cycles.

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

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

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}]]

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

A305008 Triangle read by rows of coefficients for functions and generating functions for the number of achiral color patterns (set partitions) for a row or loop of varying length using exactly n colors (sets).

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 2, -1, -2, 1, 2, -1, -4, -2, 1, 3, -3, -11, 0, 6, 1, 3, -3, -17, -8, 20, 16, 1, 4, -6, -32, 1, 64, 20, -20, 1, 4, -6, -44, -19, 140, 136, -120, -132, 1, 5, -10, -70, 5, 301, 152, -396, -280, 28, 1, 5, -10, -90, -35, 541, 608, -1228, -1752, 800, 1216, 1, 6, -15, -130, 15, 966, 643, -2798

Offset: 0

Robert A. Russell, May 23 2018

Triangle begins with T(0,0).
Two color patterns are equivalent if we permute the colors. Achiral color patterns must be equivalent if we reverse the order of the pattern.
The generating function for exactly n colors (column n of A304972) is
  x^n * Sum_{k=0..n} (T(n, k) * x^k) / Product_{k=1..n} (1 - k*x^2).
Both the numerator and denominator of this g.f. have factors of (1+x) and (1-(n-2)*x^2) when n > 2.
Letting S2(m,n) be the Stirling subset number A008277(m,n), the function for exactly n colors for a row or loop of length m, A304972(m,n), n even, is
  [m==0 mod 2] * Sum_{k=0..n/2} T(n, 2k) * S2((m+n)/2-k, n) +
  [m==1 mod 2] * Sum_{k=1..n/2} T(n, 2k-1) * S2((m+n+1)/2-k, n).
When n is odd, the function for A304972(m,n) is
  [m==0 mod 2] * Sum_{k=0..(n-1)/2} T(n, 2k+1) * S2((m+n-1)-k, n) +
  [m==1 mod 2] * Sum_{k=0..(n-1)/2} T(n, 2k) * S2((m+n)/2-k, n).

			Triangle begins:
1;
1, 1;
1, 1,   0;
1, 2,  -1,   -2;
1, 2,  -1,   -4,  -2;
1, 3,  -3,  -11,   0,   6;
1, 3,  -3,  -17,  -8,  20,  16;
1, 4,  -6,  -32,   1,  64,  20,   -20;
1, 4,  -6,  -44, -19, 140, 136,  -120,  -132;
1, 5, -10,  -70,   5, 301, 152,  -396,  -280,   28;
1, 5, -10,  -90, -35, 541, 608, -1228, -1752,  800, 1216;
1, 6, -15, -130,  15, 966, 643, -2798, -3028, 2236, 3600, 936;

Coefficients for functions and generating functions of A304973, A304974, A304975, A304976, which are columns 3-6 of A304972.

Coef[n_, -1] := Coef[n, -1] = 0; Coef[n_, 0] := Coef[n, 0] = Boole[n>=0];
Coef[n_, k_] := Coef[n, k] = If[k > n, 0, Coef[n-1, k-1] + Coef[n-2, k] - (n-1) Coef[n-2, k-2]]
Table[Coef[n, k], {n, 0, 30}, {k, 0, n}] // Flatten

T(n,k) = [1 <= k <= n] * (T(n-1, k-1) + T(n-2, k) - (n-1) * T(n-2, k-2)) + [k==0 & n>=0].

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

Original entry on oeis.org

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

Robert A. Russell, Jun 09 2018

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.

			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.

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

Fifth column of A305749.
Cf. A056272 (oriented), A056324 (unoriented), A320935 (chiral), for rows.
Cf. A056293 (oriented), A056355 (unoriented), A320745 (chiral), for cycles.

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

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}]]

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

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

Original entry on oeis.org

1, 1, 2, 3, 7, 12, 31, 58, 159, 312, 883, 1774, 5103, 10368, 30067, 61414, 178815, 366168, 1068259, 2190190, 6395919, 13120944, 38335123, 78665590, 229890591, 471814344, 1378985155, 2830350526, 8272839855, 16980500640, 49633834099, 101878204486

Offset: 0

Robert A. Russell, Jun 09 2018

An equivalent color pattern is obtained when we permute the colors. Thus all permutations of ABCDE are equivalent, as are AABCDEF and BBCDEFA. A color pattern is achiral if it is equivalent to its reversal. Rotations of the colors of a cycle are equivalent, so for cycles AABCCDEF = BCCDEFAA = CCDEFAAB.

			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.

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

Sixth column of A305749.
Cf. A056273 (oriented), A056325 (unoriented), A320936 (chiral), for rows.
Cf. A056294 (oriented), A056356 (unoriented), A320746 (chiral), for cycles.

seq(coeff(series((1-10*x^2+x^3+29*x^4-6*x^5-25*x^6+8*x^7)/((1-x)*(1-2*x^2)*(1-3*x^2)*(1-6*x^2)),x,n+1), x, n), n = 0 .. 35); # Muniru A Asiru, Oct 30 2018

Table[If[EvenQ[n], StirlingS2[(n+12)/2, 6] - 19 StirlingS2[(n+10)/2, 6] + 140 StirlingS2[(n+8)/2, 6] - 501 StirlingS2[(n+6)/2, 6] + 887 StirlingS2[(n+4)/2, 6] - 692 StirlingS2[(n+2)/2, 6] + 160 StirlingS2[n/2, 6], StirlingS2[(n+11)/2, 6] - 18 StirlingS2[(n+9)/2, 6] + 124 StirlingS2[(n+7)/2, 6] - 404 StirlingS2[(n+5)/2, 6] + 613 StirlingS2[(n+3)/2, 6] - 340 StirlingS2[(n+1)/2, 6]], {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=6; Table[Sum[Ach[n, j], {j, 0, k}], {n, 0, 40}]
CoefficientList[Series[(1-10x^2+x^3+29x^4-6x^5-25x^6+8x^7) / ((1-x)(1-2x^2)(1-3x^2)(1-6 x^2)), {x, 0, 40}], x]
LinearRecurrence[{1,11,-11,-36,36,36,-36},{1,1,2,3,7,12,31,58},40]
Join[{1}, Table[If[EvenQ[n], (36 + 45 2^(n/2) + 40 3^(n/2) + 19 6^(n/2)) / 180, (72 + 45 2^((n+1)/2) + 40 3^((n+1)/2) + 13 6^((n+1)/2)) / 360], {n,40}]]

a(n) = Sum_{j=0..6} 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-10x^2+x^3+29x^4-6x^5-25x^6+8x^7) / ((1-x)*(1-2x^2)*(1-3x^2)*(1-6x^2)).
a(2m) = S2(m+6,6) - 19*S2(m+5,6) + 140*S2(m+4,6) - 501*S2(m+3,6) + 887*S2(m+2,6) - 692*S2(m+1,6) + 160*S2(m,6);
a(2m-1) = S2(m+5,6) - 18*S2(m+4,6) + 124*S2(m+3,6) - 404*S2(m+2,6) + 613*S2(m+1,6) - 340*S2(m,6), where S2(n,k) is the Stirling subset number A008277.
For n>0, a(2m) = (36 + 45*2^m + 40*3^m + 19*6^m) / 180.
a(2m-1) = (72 + 45*2^m + 40*3^m + 13*6^m) / 360.
a(n) = 2*A056325(n) - A056273(n) = A056273(n) - 2*A320936(n) = A056325(n) - A320936(n).
a(n) = 2*A056356(n) - A056294(n) = A056294(n) - 2*A320746(n) = A056356(n) - A320936(n).
a(n) = A057427(n) + A052551(n-2) + A304973(n) + A304974(n) + A304975(n) + A304976(n).
a(n) = a(n-1) + 11*a(n-2) - 11*a(n-3) - 36*a(n-4) + 36*a(n-5) + 36*a(n-6) - 36*a(n-7). - Muniru A Asiru, Oct 30 2018

A320527 Number of chiral pairs of color patterns (set partitions) in a row of length n using exactly 4 colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 4, 28, 167, 824, 3840, 16920, 72655, 305140, 1265264, 5193188, 21173607, 85887984, 347150080, 1399355440, 5629755935, 22615859180, 90754215024, 363888497148, 1458169977847, 5840524999144, 23385639542720, 93613165023560, 374664497695215, 1499293455643620, 5999080285068784, 24002040333605908

Offset: 1

Robert A. Russell, Oct 14 2018

Two color patterns are equivalent if we permute the colors. Chiral color patterns must not be equivalent if we reverse the order of the pattern.

			For a(5)=4, the chiral pairs are AABCD-ABCDD, ABACD-ABCDC, ABBCD-ABCCD and ABCAD-ABCDB.

Index entries for linear recurrences with constant coefficients, signature (8, -12, -44, 121, 12, -228, 144).

Col. 4 of A320525.

Cf. A000453 (oriented), A056328 (unoriented), A304974 (achiral).

k=4; Table[(StirlingS2[n,k] - If[EvenQ[n], StirlingS2[n/2+2,4] - StirlingS2[n/2+1,4] - 2StirlingS2[n/2,4], 2StirlingS2[(n+3)/2,4] - 4StirlingS2[(n+1)/2,4]])/2, {n,30}]
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[(StirlingS2[n, k] - Ach[n, k])/2, {n, 1, 30}]
LinearRecurrence[{8, -12, -44, 121, 12, -228, 144}, {0, 0, 0, 0, 4, 28, 167}, 30]

a(n) = (S2(n,k) - A(n,k))/2, where k=4 is the number of colors (sets), S2 is the Stirling subset number A008277 and A(n,k) = [n>1] * (k*A(n-2,k) + A(n-2,k-1) + A(n-2,k-2)) + [n<2 & n==k & n>=0].
G.f.: (x^4 / Product_{k=1..4} (1 - k*x) - x^4*(1 + x)^2*(1 - 2 x^2) / Product_{k=1..4} (1 - k*x^2)) / 2.
a(n) = (A000453(n) - A304974(n)) / 2 = A000453(n) - A056328(n) = A056328(n) - A304974(n).

A320644 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using exactly 4 colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 17, 84, 388, 1586, 6405, 24927, 96404, 368641, 1407515, 5357974, 20403120, 77699323, 296229485, 1130614092, 4321324766, 16539645539, 63397442097, 243352167691, 935420468092, 3600493932070, 13876442107403, 53546144395718, 206864753332164, 800067806813323, 3097590602034137, 12004772596768984, 46568647645538594, 180809553280920680

Offset: 1

Robert A. Russell, Oct 18 2018

Two color patterns are the same if the colors are permuted. A chiral cycle is different from its reverse.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
There are nonrecursive formulas, generating functions, and computer programs for A056297 and A304974, which can be used in conjunction with the first formula.

			For a(6)=2, the chiral pairs are AABACD-AABCAD and AABCBD-AABCDC.

Andrew Howroyd, Table of n, a(n) for n = 1..200
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Column 4 of A320647.

Cf. A056297 (oriented), A056359 (unoriented), A304974 (achiral).

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 *)
Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d,Adnk[d,n-1,k-#] &], Boole[n==0 && k==0]]
k=4; Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/(2n) - Ach[n,k]/2,{n,40}]

a(n) = (A056297(n) - A304974(n)) / 2 = A056297(n) - A056359(n) = A056359(n) - A304974(n).

a(n) = -Ach(n,k)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,k), where k=4 is number of colors or sets, Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k)+Ach(n-2,k-1)+Ach(n-2,k-2)), and A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A056328 Number of reversible string structures with n beads using exactly four different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

Formula

A305008 Triangle read by rows of coefficients for functions and generating functions for the number of achiral color patterns (set partitions) for a row or loop of varying length using exactly n colors (sets).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320527 Number of chiral pairs of color patterns (set partitions) in a row of length n using exactly 4 colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs