A305008 -id:A305008 - 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.

A304973 Number of achiral color patterns (set partitions) for a row or loop of length n using exactly 3 colors (sets).

Original entry on oeis.org

0, 0, 0, 1, 2, 5, 10, 19, 38, 65, 130, 211, 422, 665, 1330, 2059, 4118, 6305, 12610, 19171, 38342, 58025, 116050, 175099, 350198, 527345, 1054690, 1586131, 3172262, 4766585, 9533170, 14316139, 28632278, 42981185, 85962370, 129009091, 258018182, 387158345, 774316690, 1161737179, 2323474358

Offset: 0

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.

			For a(5) = 5, the color patterns for both rows and loops are AABCC, ABACA, ABBBC, ABCAB, and ABCBA.

Index entries for linear recurrences with constant coefficients, signature (0, 5, 0, -6).

Third column of A304972.
Third column of A140735 for odd n.
Third column of A293181 for even n.
Coefficients that determine the first formula and generating function are row 3 of A305008.

Table[If[EvenQ[n], 2 StirlingS2[n/2+1, 3] - 2 StirlingS2[n/2, 3], StirlingS2[(n + 3)/2, 3] - StirlingS2[(n + 1)/2, 3]], {n, 0, 30}]
Join[{0}, LinearRecurrence[{0, 5, 0, -6}, {0, 0, 1, 2}, 40]] (* Robert A. Russell, Oct 14 2018 *)

a(n) = [n==0 mod 2] * (2*S2(n/2+1, 3) - 2*S2(n/2, 3)) + [n==1 mod 2] * (S2((n+3)/2, 3) - S2((n+1)/2, 3)) where S2(n,k) is the Stirling subset number A008277(n,k).
G.f.: x^3 * (1+2x) / ((1-2x^2) * (1-3x^2)).
a(n) = A304972(n,3).
a(2m-1) = A140735(m,3).
a(2m) = A293181(m,3).

A304974 Number of achiral color patterns (set partitions) for a row or loop of length n using exactly 4 colors (sets).

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 9, 16, 53, 90, 265, 440, 1221, 2002, 5369, 8736, 22933, 37130, 96105, 155080, 397541, 640002, 1629529, 2619056, 6636213, 10653370, 26899145, 43144920, 108659461, 174174002, 437826489, 701478976, 1760871893, 2820264810, 7072185385, 11324105960, 28374834981, 45425564002, 113757620249

Offset: 0

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.

			For a(6) = 9, the row color patterns are AABCDD, ABACDC, ABBCCD, ABCADC, ABCBCD, ABCCBD, ABCCDA, ABCDAB, and ABCBCD.  The loop color patterns are AAABCD, AABBCD, AABCCD, AABCDB, ABABCD, ABACAD, ABACBD, ABACDC, and ABCADC.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,7,-7,-12,12).

Fourth column of A304972.
Fourth column of A140735 for odd n.
Fourth column of A293181 for even n.
Coefficients that determine the first formula and generating function are row 4 of A305008.

I:=[0,0,0,1,2]; [0] cat [n le 5 select I[n] else Self(n-1) +7*Self(n-2) -7*Self(n-3) -12*Self(n-4) +12*Self(n-5): n in [1..40]]; // G. C. Greubel, Oct 17 2018

Table[If[EvenQ[n], StirlingS2[n/2 + 2, 4] - StirlingS2[n/2 + 1, 4] - 2 StirlingS2[n/2, 4], 2 StirlingS2[(n + 3)/2, 4] - 4 StirlingS2[(n + 1)/2, 4]], {n, 0, 40}]
Join[{0}, LinearRecurrence[{1, 7, -7, -12, 12}, {0, 0, 0, 1, 2}, 40]] (* Robert A. Russell, Oct 14 2018 *)

m=40; v=concat([0,0,0,1,2], vector(m-5)); for(n=6, m, v[n] = v[n-1] +7*v[n-2] -7*v[n-3] -12*v[n-4] +12*v[n-5]); concat([0], v) \\ G. C. Greubel, Oct 17 2018

a(n) = [n==0 mod 2] * (S2(n/2+2, 4) - S2(n/2+1, 4) - 2*S2(n/2, 4)) + [n==1 mod 2] * (2*S2((n+3)/2, 4) - 4*S2((n+1)/2, 4)) where S2(n,k) is the Stirling subset number A008277(n,k).
G.f.: x^4 * (1+x)^2 * (1-2x^2) / Product_{k=1..4} (1 - k*x^2).
a(n) = A304972(n,4).
a(2m-1) = A140735(m,4).
a(2m) = A293181(m,4).

A304975 Number of achiral color patterns (set partitions) for a row or loop of length n using exactly 5 colors (sets).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 3, 12, 34, 95, 261, 630, 1700, 3801, 10143, 21672, 57414, 119155, 314121, 639210, 1679320, 3370301, 8832483, 17549532, 45907994, 90541815, 236526381, 463889790, 1210585740, 2364180001, 6164760423, 11999840592, 31271161774, 60714998075, 158145313041, 306438236370, 797884712960

Offset: 0

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.

			For a(6) = 3, the color patterns for both rows and loops are ABCCDE, ABCDBE, and ABCDEA.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,11,-11,-38,38,40,-40).

Fifth column of A304972.
Fifth column of A140735 for odd n.
Fifth column of A293181 for even n.
Coefficients that determine the first formula and generating function are row 5 of A305008.

I:=[0,0,0,0,1,3,12]; [0] cat [n le 7 select I[n] else Self(n-1) +11*Self(n-2) -11*Self(n-3) -38*Self(n-4) +38*Self(n-5) +40*Self(n-6) -40*Self(n-7): n in [1..40]]; // G. C. Greubel, Oct 16 2018

Table[If[EvenQ[n], 3 StirlingS2[n/2+2, 5] - 11 StirlingS2[n/2+1, 5] + 6 StirlingS2[n/2, 5], StirlingS2[(n+5)/2, 5] - 3 StirlingS2[(n+3)/2, 5]], {n, 0, 40}]
Join[{0}, LinearRecurrence[{1, 11, -11, -38, 38, 40, -40}, {0, 0, 0, 0, 1, 3, 12}, 40]] (* Robert A. Russell, Oct 14 2018 *)
CoefficientList[Series[x^5 *(1 + x)*(1 - 3*x^2)*(1 + 2*x - 2*x^2) / Product[1 - k*x^2, {k,1,5}], {x, 0, 50}],x] (* Stefano Spezia, Oct 16 2018 *)

m=40; v=concat([0,0,0,0,1,3,12], vector(m-7)); for(n=8, m, v[n] = v[n-1] +11*v[n-2] -11*v[n-3] -38*v[n-4] +38*v[n-5] +40*v[n-6] -40*v[n-7] ); concat([0], v) \\ G. C. Greubel, Oct 16 2018

a(n) = [n==0 mod 2] * (3*S2(n/2+2, 5) - 11*S2(n/2+1, 5) + 6*S2(n/2, 5)) + [n==1 mod 2] * (S2((n+5)/2, 5) - 3*S2((n+3)/2, 5)) where S2(n,k) is the Stirling subset number A008277(n,k).
G.f.: x^5 *(1 + x)*(1 - 3*x^2)*(1 + 2*x - 2*x^2) / Product_{k=1..5} (1 - k*x^2).
a(n) = A304972(n,5).
a(2m-1) = A140735(m,5).
a(2m) = A293181(m,5).

A304976 Number of achiral color patterns (set partitions) for a row or loop of length n using exactly 6 colors (sets).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 3, 18, 46, 195, 461, 1696, 3836, 13097, 28819, 94094, 203322, 644911, 1376217, 4279692, 9051592, 27755013, 58319855, 176992090, 370087718, 1114496747, 2321721493, 6950406008, 14437363668, 43021681249, 89162536011, 264732674406, 547676535634

Offset: 0

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.

			For a(7) = 3, the color patterns for both rows and loops are ABCDCEF, ABCDEBF, and ABCDEFA.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,16,-16,-91,91,216,-216,-180, 180).

Sixth column of A304972.
Sixth column of A140735 for odd n.
Sixth column of A293181 for even n.
Coefficients that determine the first formula and generating function are row 6 of A305008.

I:=[0,0,0,0,0,1,3,18,46]; [0] cat [n le 9 select I[n] else Self(n-1) +16*Self(n-2) -16*Self(n-3) -91*Self(n-4) +91*Self(n-5) +216*Self(n-6) -216*Self(n-7) -180*Self(n-8) +180*Self(n-9): n in [1..40]]; // G. C. Greubel, Oct 16 2018

Table[If[EvenQ[n], StirlingS2[n/2 + 3, 6] - 3 StirlingS2[n/2 + 2, 6] - 8 StirlingS2[n/2 + 1, 6] + 16 StirlingS2[n/2, 6], 3 StirlingS2[(n + 5)/2, 6] - 17 StirlingS2[(n + 3)/2, 6] + 20 StirlingS2[(n + 1)/2, 6]], {n, 0, 40}]
Join[{0}, LinearRecurrence[{1, 16, -16, -91, 91, 216, -216, -180, 180}, {0, 0, 0, 0, 0, 1, 3, 18, 46}, 40]] (* Robert A. Russell, Oct 14 2018 *)
CoefficientList[Series[x^6 *(1+x)*(1-4*x^2)*(1+2*x-x^2-4*x^3) / Product[1 - k*x^2, {k,1,6}], {x, 0, 50}], x] (* Stefano Spezia, Oct 20 2018 *)

m=40; v=concat([0,0,0,0,0,1,3,18,46], vector(m-9)); for(n=10, m, v[n] = v[n-1] +16*v[n-2] -16*v[n-3] -91*v[n-4] +91*v[n-5] +216*v[n-6] -216*v[n-7] -180*v[n-8] +180*v[n-9]); concat([0], v) \\ G. C. Greubel, Oct 16 2018

a(n) = [n==0 mod 2] * (S2(n/2+3, 6) - 3*S2(n/2+2, 6) - 8*S2(n/2+1, 6) + 16*S2(n/2, 6)) + [n==1 mod 2] * (3*S2((n+5)/2, 6) - 17*S2((n+3)/2, 6) + 20*S2((n+1)/2, 6 )) where S2(n,k) is the Stirling subset number A008277(n,k).
G.f.: x^6 *(1+x)*(1-4*x^2)*(1+2*x-x^2-4*x^3) / Product_{k=1..6} (1 - k*x^2).
a(n) = A304972(n,6).
a(2m-1) = A140735(m,6).
a(2m) = A293181(m,6).

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

A304973 Number of achiral color patterns (set partitions) for a row or loop of length n using exactly 3 colors (sets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A304974 Number of achiral color patterns (set partitions) for a row or loop of length n using exactly 4 colors (sets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A304975 Number of achiral color patterns (set partitions) for a row or loop of length n using exactly 5 colors (sets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A304976 Number of achiral color patterns (set partitions) for a row or loop of length n using exactly 6 colors (sets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula