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

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

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

A056330 Number of reversible string structures with n beads using exactly six different colors.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 12, 142, 1346, 11511, 89974, 662674, 4662574, 31724735, 210361046, 1367510326, 8752976610, 55343947975, 346541488998, 2153041587538, 13292844257198, 81652683550119, 499484958151630

Offset: 1

Marks R. Nester

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 six different elements. An unoriented row is equivalent to its reverse. - Robert A. Russell, Oct 14 2018

			For a(7)=12, the color patterns are ABCDEFA, ABCDEBF, ABCDCEF, AABCDEF, ABACDEF, ABCADEF, ABCDAEF, ABBCDEF, ABCBDEF, ABCDBEF, and ABCCDEF. The first three 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 (21, -159, 399, 1085, -8085, 9555, 34125, -98644, 5544, 253764, -248724, -136800, 317520, -129600).

Column 6 of A284949.
Cf. A056313.
Cf. A000770 (oriented), A320529 (chiral), A304976 (achiral).

k=6; Table[(StirlingS2[n,k] + If[EvenQ[n], StirlingS2[n/2+3,6] - 3StirlingS2[n/2+2,6] - 8StirlingS2[n/2+1,6] + 16StirlingS2[n/2,6], 3StirlingS2[(n+5)/2,6] - 17StirlingS2[(n+3)/2,6] + 20StirlingS2[(n+1)/2,6]])/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 = 6; Table[(StirlingS2[n, k] + Ach[n, k])/2, {n, 1, 30}] (* Robert A. Russell, Oct 14 2018 *)
LinearRecurrence[{21, -159, 399, 1085, -8085, 9555, 34125, -98644, 5544, 253764, -248724, -136800, 317520, -129600}, {0, 0, 0, 0, 0, 1, 12, 142, 1346, 11511, 89974, 662674, 4662574, 31724735}, 40] (* Robert A. Russell, Oct 14 2018 *)

a(n) = A056325(n) - A056324(n).
From Robert A. Russell, Oct 14 2018: (Start)
a(n) = (S2(n,k) + A(n,k))/2, where k=6 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^6 / Product_{k=1..6} (1 - k*x) + x^6 (1+x) (1-4x^2) (1+2x-x^2-4x^3) / Product_{k=1..6} (1 - k*x^2)) / 2.
a(n) = (A000770(n) + A304976(n)) / 2 = A000770(n) - A320529(n) = A320529(n) + A304976(n). (End)

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 9, 124, 1300, 11316, 89513, 660978, 4658738, 31711638, 210332227, 1367416232, 8752773288, 55343303064, 346540112781, 2153037307846, 13292835205606, 81652655795106, 499484899831775, 3045117929546220, 18513208314957356, 112297592929814292, 679900657841661529, 4110073054119135194, 24814158520762637754

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(7)=9, the chiral pairs are AABCDEF-ABCDEFF, ABACDEF-ABCDEFE, ABCADEF-ABCDEFD, ABCDAEF-ABCDEFC, ABCDEAF-ABCDEFB, ABBCDEF-ABCDEEF, ABCBDEF-ABCDEDF, ABCDBEF-ABCDECF, and ABCCDEF-ABCDDEF.

Index entries for linear recurrences with constant coefficients, signature (21, -159, 399, 1085, -8085, 9555, 34125, -98644, 5544, 253764, -248724, -136800, 317520, -129600).

Column 6 of A320525.

Cf. A000770 (oriented), A056330 (unoriented), A304976 (achiral).

m:=30; R:=PowerSeriesRing(Integers(), m); [0,0,0,0,0,0] cat Coefficients(R!((x^6/(&*[1-k*x: k in [1..6]]) - x^6*(1+x)*(1-4*x^2)*(1+2*x-x^2-4*x^3)/(&*[1-k*x^2: k in [1..6]]) )/2)); // G. C. Greubel, Oct 19 2018

k=6; Table[(StirlingS2[n,k] - If[EvenQ[n], StirlingS2[n/2+3,6] - 3StirlingS2[n/2+2,6] - 8StirlingS2[n/2+1,6] + 16StirlingS2[n/2,6], 3StirlingS2[(n+5)/2,6] - 17StirlingS2[(n+3)/2,6] + 20StirlingS2[(n+1)/2,6]])/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 = 6; Table[(StirlingS2[n, k] - Ach[n, k])/2, {n, 1, 30}]
LinearRecurrence[{21, -159, 399, 1085, -8085, 9555, 34125, -98644, 5544, 253764, -248724, -136800, 317520, -129600}, {0, 0, 0, 0, 0, 0, 9, 124, 1300, 11316, 89513, 660978, 4658738, 31711638}, 30]

x='x+O('x^30); concat(vector(6), Vec((x^6/prod(k=1,6, 1-k*x) - x^6* (1+x)*(1-4*x^2)*(1+2*x-x^2-4*x^3)/prod(k=1,6,(1-k*x^2)))/2)) \\ G. C. Greubel, Oct 19 2018

a(n) = (S2(n,k) - A(n,k))/2, where k=6 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^6 / (Product_{k=1..6} (1 - k*x)) - x^6 *(1+x)*(1-4*x^2)*(1+2*x-x^2-4*x^3) / Product_{k=1..6} (1 - k*x^2)) / 2.
a(n) = (A000770(n) - A304976(n)) / 2 = A000770(n) - A056330(n) = A056330(n) - A304976(n).

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 9, 125, 1054, 7928, 54383, 356594, 2259504, 14008733, 85422360, 514773336, 3074341497, 18238301412, 107649939612, 632987843336, 3711471738408, 21716706883190, 126879832615600, 740528154956264, 4319137675225128, 25181504728152534, 146788320134425736, 855660631677225738, 4988501691655508510, 29089896998939710698

Offset: 1

Robert A. Russell, Oct 19 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 A056299 and A304976, which can be used in conjunction with the first formula.

			For a(8)=9, the chiral pairs are AABACDEF-AABCDEAF, AABCADEF-AABCDAEF, AABCBDEF-AABCDEFE, AABCDBEF-AABCDEFD, AABCDEBF-AABCDEFC, AABCDCEF-AABCDEDF, ABACDEBF-ABACDEBF, ABCADBEF-ABCADECF, and ABCDAEBF-ABCADBEF.

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 6 of A320647.

Cf. A056299 (oriented), A056361 (unoriented), A304976 (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=6; Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/(2n) - Ach[n,k]/2,{n,40}]

a(n) = (A056299(n) - A304976(n)) / 2 = A056299(n) - A056361(n) = A056361(n) - A304976(n).

a(n) = -Ach(n,k)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,k), where k=5 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

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

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

A056330 Number of reversible string structures with n beads using exactly six different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula