A304972 -id:A304972 - cp's OEIS frontend

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

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

A309748 The number of non-equivalent distinguishing coloring partitions of the path on n vertices (n>=1) with exactly k parts (k>=1). Regular triangle read by rows: the rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of parts.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 4, 4, 1, 0, 6, 14, 6, 1, 0, 16, 49, 37, 9, 1, 0, 28, 154, 182, 76, 12, 1, 0, 64, 496, 876, 542, 142, 16, 1, 0, 120, 1520, 3920, 3522, 1346, 242, 20, 1, 0, 256, 4705, 17175, 21392, 11511, 2980, 390, 25, 1, 0, 496, 14266, 73030, 123665, 89973, 32141, 5990, 595, 30, 1

Offset: 1

Mohammad Hadi Shekarriz, Aug 15 2019

A vertex-coloring of a graph G is called distinguishing if it is only preserved by the identity automorphism of G. This notion is considered in the subject of symmetry breaking of simple (finite or infinite) graphs. A distinguishing coloring partition of a graph G is a partition of the vertices of G such that it induces a distinguishing coloring for G. We say two distinguishing coloring partitions P1 and P2 of G are equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. Given a graph G, we use the notation psi_k(G) to denote the number of non-equivalent distinguishing coloring partitions of G with at exactly k parts. For n>=1, this sequence gives T(n,k) = psi_k(P_n), i.e., the number of non-equivalent distinguishing coloring partitions of the path P_n on n vertices with exactly k parts.

Also, for n > 1 the number of reversible string structures of length n using exactly k different symbols that are not equivalent to their reversal (compare A284949). - Andrew Howroyd, Aug 15 2019

			The triangle begins:
  1;
  0,   1;
  0,   1,    1;
  0,   4,    4,     1;
  0,   6,   14,     6,     1;
  0,  16,   49,    37,     9,     1;
  0,  28,  154,   182,    76,    12,    1;
  0,  64,  496,   876,   542,   142,   16,   1;
  0, 120, 1520,  3920,  3522,  1346,  242,  20,  1;
  0, 256, 4705, 17175, 21392, 11511, 2980, 390, 25, 1;
  ...
----
For n=4, we can partition the vertices of P_4 into exactly 3 parts in 4 ways such that all these partitions induce distinguishing colorings for P_4 and that all the 4 partitions are non-equivalent. The partitions are as follows:
    { { 1 }, { 2 }, { 3, 4 } }
    { { 1 }, { 2, 3 }, { 4 } }
    { { 1 }, { 2, 4 }, { 3 } }
    { { 1, 4 }, { 2 }, { 3 } }

Andrew Howroyd, Table of n, a(n) for n = 1..1275
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
Mohammad Hadi Shekarriz, GAP Program

Columns k=2..4 are A007179, A327610, A327611.
Row sums are A327612(n > 1).
Cf. A284949, A304972, A309635, A309784.

\\ Ach is A304972 as square matrix.
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}
T(n)={(matrix(n, n, i, k, stirling(i, k, 2) - 2*stirling((i+1)\2, k, 2)) + Ach(n))/2}
{ my(A=T(10)); A[1,1]=1; for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 18 2019

T(n,k) = A309635(n,k) - A309635(n,k-1) for k > 1.

T(n,k) = A284949(n,k) - Stirling2(ceiling(n/2), k) for n > 1. - Andrew Howroyd, Aug 15 2019

Terms a(56) and beyond from Andrew Howroyd, Sep 18 2019

A320751 Array read by antidiagonals: T(n,k) is the number of chiral pairs of color patterns (set partitions) in a row of length n using k or fewer colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 0, 0, 1, 4, 6, 0, 0, 0, 1, 4, 16, 12, 0, 0, 0, 1, 4, 20, 52, 28, 0, 0, 0, 1, 4, 20, 80, 169, 56, 0, 0, 0, 1, 4, 20, 86, 336, 520, 120, 0, 0, 0, 1, 4, 20, 86, 400, 1344, 1600, 240, 0, 0, 0, 1, 4, 20, 86, 409, 1852, 5440, 4840, 496, 0

Offset: 1

Robert A. Russell, Oct 27 2018

Two color patterns are equivalent if the colors are permuted.
A chiral row is not equivalent to its reverse.
T(n,k)=Xi_k(P_n) which is the number of non-equivalent distinguishing partitions of the path on n vertices, with at most k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. A distinguishing partition is a partition of the vertex set of G such that no nontrivial automorphism of G can preserve it. - Bahman Ahmadi, Sep 02 2019

			Array begins with T(1,1):
0   0     0      0       0       0       0       0       0       0 ...
0   0     0      0       0       0       0       0       0       0 ...
0   1     1      1       1       1       1       1       1       1 ...
0   2     4      4       4       4       4       4       4       4 ...
0   6    16     20      20      20      20      20      20      20 ...
0  12    52     80      86      86      86      86      86      86 ...
0  28   169    336     400     409     409     409     409     409 ...
0  56   520   1344    1852    1976    1988    1988    1988    1988 ...
0 120  1600   5440    8868   10168   10388   10404   10404   10404 ...
0 240  4840  21760   42892   54208   57108   57468   57488   57488 ...
0 496 14641  87296  210346  299859  331705  337595  338155  338180 ...
0 992 44044 349184 1038034 1699012 2012202 2091458 2102518 2103348 ...
For T(4,2)=2, the chiral pairs are AAAB-ABBB and AABA-ABAA.
For T(4,3)=4, the above, AABC-ABCC, and ABAC-ABCB.

B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.

Columns 1-6 are A000004, A122746(n-3), A107767(n-1), A320934, A320935, A320936.
As k increases, columns converge to A320937.
Cf. transpose of A278984 (oriented), A320750 (unoriented), A305749 (achiral).
Partial column sums of A320525.

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 *)
Table[Sum[StirlingS2[n,j] - Ach[n,j], {j,k-n+1}]/2, {k,15}, {n,k}] // Flatten

T(n,k) = Sum_{j=1..k} (S2(n,j) - Ach(n,j)) / 2, where S2 is the Stirling subset number A008277 and 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)).
T(n,k) = (A278984(k,n) - A305749(n,k)) / 2 = A278984(k,n) - A320750(n,k) = A320750(n,k) - A305749(n,k).
T(n,k) = Sum_{j=1..k} A320525(n,j).

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

A320526 a(n) is the number of chiral pairs of color patterns (set partitions) in a row of length n using exactly 3 colors (subsets).

Original entry on oeis.org

0, 0, 0, 2, 10, 40, 141, 464, 1480, 4600, 14145, 43052, 130480, 393820, 1186521, 3568784, 10725760, 32213200, 96714465, 290284052, 871142800, 2613981700, 7843080201, 23531425304, 70598731840, 211804847800, 635432109585, 1906330676252, 5719061512720, 17157321139180

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(4)=2, the two chiral pairs are AABC-ABCC and ABAC-ABCB.

Index entries for linear recurrences with constant coefficients, signature (6, -6, -24, 49, 6, -66, 36).

Column 3 of A320525.

Cf. A000392 (oriented), A056327 (unoriented), A304973 (achiral).

I:=[0,0,0,2,10,40,141]; [n le 7 select I[n] else 6*Self(n-1) -6*Self(n-2) -24*Self(n-3) +49*Self(n-4) +6*Self(n-5) -66*Self(n-6) +36*Self(n-7): n in [1..40]]; // G. C. Greubel, Oct 16 2018

k=3; Table[(StirlingS2[n,k] - If[EvenQ[n], 2StirlingS2[n/2+1,3] - 2StirlingS2[n/2,3], StirlingS2[(n+3)/2,3] - StirlingS2[(n+1)/2,3]])/2, {n, 1, 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 = 3; Table[(StirlingS2[n, k] - Ach[n, k])/2, {n, 1, 30}]
LinearRecurrence[{6, -6, -24, 49, 6, -66, 36}, {0, 0, 0, 2, 10, 40,
  141}, 40]

m=40; v=concat([0,0,0,2,10,40,141], vector(m-7)); for(n=8, m, v[n] = 6*v[n-1] -6*v[n-2] -24*v[n-3] +49*v[n-4] +6*v[n-5] -66*v[n-6] +36*v[n-7] ); v \\ G. C. Greubel, Oct 16 2018

a(n) = (S2(n,k) - A(n,k))/2, where k=3 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^3 / Product_{k=1..3} (1 - k*x) - x^3*(1 + 2 x)/((1 - 2 x^2)*(1 - 3 x^2))) / 2.
a(n) = (A000392(n) - A304973(n)) / 2 = A000392(n) - A056327(n) = A056327(n) - A304973(n).

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

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 12, 44, 137, 408, 1190, 3416, 9730, 27560, 78148, 221250, 627960, 1784038, 5081154, 14496956, 41455409, 118764600, 340919744, 980315700, 2823696150, 8145853520, 23533759241, 68081765650, 197206716570, 571906256808, 1660387879116, 4825525985408, 14037945170525, 40875277302720, 119122416494961, 347440682773324, 1014151818975190, 2962391932326680, 8659301777595196, 25328461701728194

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 A056296 and A304973, which can be used in conjunction with the first formula.

			For a(6)=4, the chiral pairs are AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, and AABACC-AABBAC.

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

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

a(n) = (A056296(n) - A304973(n)) / 2 = A056296(n) - A056358(n) = A056358(n) - A304973(n).

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

A320748 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented cycle of length n using k or fewer colors (subsets).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 4, 1, 1, 2, 3, 6, 4, 1, 1, 2, 3, 7, 9, 8, 1, 1, 2, 3, 7, 11, 22, 9, 1, 1, 2, 3, 7, 12, 33, 40, 18, 1, 1, 2, 3, 7, 12, 36, 73, 100, 23, 1, 1, 2, 3, 7, 12, 37, 89, 237, 225, 44, 1, 1, 2, 3, 7, 12, 37, 92, 322, 703, 582, 63, 1, 1, 2, 3, 7, 12, 37, 93, 349, 1137, 2433, 1464, 122, 1, 1, 2, 3, 7, 12, 37, 93, 353, 1308, 4704, 8309, 3960, 190, 1, 1, 2, 3, 7, 12, 37, 93, 354, 1345, 5953, 19839, 30108, 10585, 362, 1

Offset: 1

Robert A. Russell, Oct 21 2018

Two color patterns are equivalent if the colors are permuted. An unoriented cycle counts each chiral pair as one, i.e., they are equivalent.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
T(n,k)=Pi_k(C_n) which is the number of non-equivalent partitions of the cycle on n vertices, with at most k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. - Bahman Ahmadi, Aug 21 2019
In other words, the number of n-bead bracelet structures using a maximum of k different colored beads. - Andrew Howroyd, Oct 30 2019

			Array begins with T(1,1):
1   1    1     1     1      1      1      1      1      1      1      1 ...
1   2    2     2     2      2      2      2      2      2      2      2 ...
1   2    3     3     3      3      3      3      3      3      3      3 ...
1   4    6     7     7      7      7      7      7      7      7      7 ...
1   4    9    11    12     12     12     12     12     12     12     12 ...
1   8   22    33    36     37     37     37     37     37     37     37 ...
1   9   40    73    89     92     93     93     93     93     93     93 ...
1  18  100   237   322    349    353    354    354    354    354    354 ...
1  23  225   703  1137   1308   1345   1349   1350   1350   1350   1350 ...
1  44  582  2433  4704   5953   6291   6345   6350   6351   6351   6351 ...
1  63 1464  8309 19839  28228  31284  31874  31944  31949  31950  31950 ...
1 122 3960 30108 88508 144587 171283 178190 179204 179300 179306 179307 ...
For T(7,2)=9, the patterns are AAAAAAB, AAAAABB, AAAABAB, AAAABBB, AAABAAB, AAABABB, AABAABB, AABABAB, and AAABABB; only the last is chiral, paired with AAABBAB.

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]

Andrew Howroyd, Table of n, a(n) for n = 1..1275
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Partial row sums of A152176.
Columns 1-6 are A057427, A000011, A056353, A056354, A056355, A056356
For increasing k, columns converge to A084708.
Cf. A320747 (oriented), A320742 (chiral), A305749 (achiral).

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]]
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 *)
Table[Sum[(DivisorSum[n, EulerPhi[#] Adnk[#,n/#,j]&]/n + Ach[n,j])/2, {j,k-n+1}], {k,15}, {n,k}] // Flatten

\\ Ach is A304972 and R is A152175 as square matrices.
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}
R(n)={Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n)={my(M=(R(n) + Ach(n))/2); for(i=2, n, M[,i] += M[,i-1]); M}
{ my(A=T(12)); for(n=1, #A, print(A[n, ])) } \\ Andrew Howroyd, Nov 03 2019

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

T(n,k) = (A320747(n,k) + A305749(n,k)) / 2 = A320747(n,k) - A320742(n,k) = A320742(n,k) + A305749(n,k).

A107767 a(n) = (1 + 3^n - 23^(n/2))/4 if n is even, (1 + 3^n - 43^((n-1)/2))/4 if n odd.

Original entry on oeis.org

0, 1, 4, 16, 52, 169, 520, 1600, 4840, 14641, 44044, 132496, 397852, 1194649, 3585040, 10758400, 32278480, 96845281, 290545684, 871666576, 2615029252, 7845176329, 23535617560, 70607118400, 211821620920, 635465659921

Offset: 1

Emeric Deutsch, Jun 12 2005

a(n-1) is the number of chiral pairs of color patterns (set partitions) for a row of length n using up to 3 colors (subsets). For n=4, a(n-1)=4, the chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB. - Robert A. Russell, Oct 28 2018

Balaban, A. T., Brunvoll, J., Cyvin, B. N., & Cyvin, S. J. (1988). Enumeration of branched catacondensed benzenoid hydrocarbons and their numbers of Kekulé structures. Tetrahedron, 44(1), 221-228. See Eq. 5.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Gy. Tasi and F. Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see p. 60).
Index entries for linear recurrences with constant coefficients, signature (4,0,-12,9).

Cf. A167993 (first differences).
Column 3 of A320751, offset by 1.
Cf. A124302 (oriented), A001998 (unoriented), A182522 (achiral), varying offsets.

a:=[];; for n in [1..30] do if n mod 2 <> 0 then Add(a,(1+3^n-4*3^((n-1)/2))/4); else Add(a,(1+3^n-2*3^(n/2))/4); fi; od; a; # Muniru A Asiru, Oct 30 2018

I:=[0, 1, 4, 16]; [n le 4 select I[n] else 4*Self(n-1)-12*Self(n-3)+9*Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jun 26 2012

a:=proc(n) if n mod 2 = 0 then (1+3^n-2*3^(n/2))/4 else (1+3^n-4*3^((n-1)/2))/4 fi end: seq(a(n),n=1..32);

CoefficientList[Series[-x/((x-1)*(3*x-1)*(3*x^2-1)),{x,0,40}],x] (* or *) LinearRecurrence[{4,0,-12,9},{0,1,4,16},50] (* Vincenzo Librandi, Jun 26 2012 *)
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=3; Table[Sum[StirlingS2[n,j]-Ach[n,j],{j,k}]/2,{n,2,40}] (* Robert A. Russell, Oct 28 2018 *)
CoefficientList[Series[(1/12 E^(-Sqrt[3] x) (-3 + 2 Sqrt[3] - (3 + 2 Sqrt[3]) E^(2 Sqrt[3] x) + 3 E^((3 + Sqrt[3]) x) + 3 E^(x + Sqrt[3] x)))/x, {x, 0, 20}], x]*Table[(k+1)!, {k, 0, 20}] (* Stefano Spezia, Oct 29 2018 *)

x='x+O('x^50); concat(0, Vec(x^2/((1-x)*(3*x-1)*(3*x^2-1)))) \\ Altug Alkan, Sep 23 2018

G.f.: -x^2 / ( (x-1)*(3*x-1)*(3*x^2-1) ). - R. J. Mathar, Dec 16 2010
a(n) = 4*a(n-1) - 12*a(n-3) + 9*a(n-4). - Vincenzo Librandi, Jun 26 2012
From Robert A. Russell, Oct 28 2018: (Start)
a(n-1) = Sum_{j=0..k} (S2(n,j) - Ach(n,j)) / 2, where k=3 is the maximum number of colors, S2 is the Stirling subset number A008277, and 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)).
a(n-1) = (A124302(n) - A182522(n))/2.
a(n-1) = A124302(n) - A001998(n-1).
a(n-1) = A001998(n-1) - A182522(n).
a(n-1) = A122746(n-2) + A320526(n). (End)
E.g.f.: (1/12)*exp(-sqrt(3)*x)*(-3 + 2*sqrt(3) - (3 + 2*sqrt(3))*exp(2*sqrt(3)*x) + 3*exp((3 + sqrt(3))*x) + 3*exp(x + sqrt(3)*x)). - Stefano Spezia, Oct 29 2018
From Bruno Berselli, Oct 31 2018: (Start)
a(n) = (1 + 3^n - 3^((n-1)/2)*(4 + (-2 + sqrt(3))*(1 + (-1)^n)))/4. Therefore:
a(2*k)   = (3^k - 1)^2/4;
a(2*k+1) = (3^k - 1)*(3^(k+1) - 1)/4. (End)

Entry revised by N. J. A. Sloane, Jul 29 2011

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

cp's OEIS Frontend

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

A309748 The number of non-equivalent distinguishing coloring partitions of the path on n vertices (n>=1) with exactly k parts (k>=1). Regular triangle read by rows: the rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A320751 Array read by antidiagonals: T(n,k) is the number of chiral pairs of color patterns (set partitions) in a row of length n using k or fewer colors (subsets).

Views

Author

Keywords

Comments

Examples

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

A320526 a(n) is the number of chiral pairs of color patterns (set partitions) in a row of length n using exactly 3 colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A320748 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented cycle of length n using k or fewer colors (subsets).

Views

Author

Keywords

Comments

Examples

A107767 a(n) = (1 + 3^n - 23^(n/2))/4 if n is even, (1 + 3^n - 43^((n-1)/2))/4 if n odd.