A304972 -id:A304972 - cp's OEIS frontend

A309784 T(n,k) is the number of non-equivalent distinguishing coloring partitions of the cycle on n vertices with exactly k parts. Regular triangle read by rows, n >= 1, 1 <= k <= n.

0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 4, 2, 1, 0, 1, 8, 10, 3, 1, 0, 1, 25, 32, 16, 3, 1, 0, 4, 62, 129, 84, 27, 4, 1, 0, 7, 176, 468, 433, 171, 37, 4, 1, 0, 18, 470, 1806, 2260, 1248, 338, 54, 5, 1, 0, 31, 1311, 6780, 11515, 8388, 3056, 590, 70, 5, 1, 0, 70, 3620, 25917, 58312, 56065, 26695, 6907, 1014, 96, 6, 1

Offset: 1

Mohammad Hadi Shekarriz, Aug 17 2019

The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.
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 exactly k parts. For n>=3, this sequence gives T(n,k) = psi_k(C_n), i.e., the number of non-equivalent distinguishing coloring partitions of the cycle C_n on n vertices with exactly k parts.
T(n,k) is the number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using exactly k different colored beads. - Andrew Howroyd, Sep 20 2019

			The triangle begins:
  0;
  0,  0;
  0,  0,   1;
  0,  0,   1,    1;
  0,  0,   4,    2,    1;
  0,  1,   8,   10,    3,    1;
  0,  1,  25,   32,   16,    3,   1;
  0,  4,  62,  129,   84,   27,   4,  1;
  0,  7, 176,  468,  433,  171,  37,  4, 1;
  0, 18, 470, 1806, 2260, 1248, 338, 54, 5, 1;
  ...
For n=6, we can partition the vertices of C_6 into exactly 3 parts in 8 ways such that all these partitions induce distinguishing colorings for C_6 and that all the 8 partitions are non-equivalent. The partitions are as follows:
    { { 1 }, { 2 }, { 3, 4, 5, 6 } }
    { { 1 }, { 2, 3 }, { 4, 5, 6 } }
    { { 1 }, { 2, 3, 4, 6 }, { 5 } }
    { { 1 }, { 2, 3, 5 }, { 4, 6 } }
    { { 1 }, { 2, 3, 6 }, { 4, 5 } }
    { { 1 }, { 2, 4, 5 }, { 3, 6 } }
    { { 1, 2 }, { 3, 4 }, { 5, 6 } }
    { { 1, 2 }, { 3, 5 }, { 4, 6 } }
For n=6, the above 8 partitions can be written as the following 3 colored bracelet structures: ABCCCC, ABBCCC, ABBBCB, ABBCBC, ABBCCB, ABCBBC, AABBCC, AABCBC. - _Andrew Howroyd_, Sep 22 2019

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

Column k=2 appears to be A011948.
Columns k=3..4 are A328038, A328039.
Row sums are A328035.
Cf. A107424, A152175, A152176, A276543, A276544, A285012, A285037, A309748, A309785.

\\ 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(A=Ach(n), M=R(n), S=matrix(n, n, n, k, stirling(n, k, 2))); Mat(vectorv(n, n, sumdiv(n, d, moebius(d)*(M[n/d,] + A[n/d,])/2 - moebius(d)*(S[(n/d+1)\2, ] + S[n/d\2+1, ] + if((n-d)%2, A[(n/d+1)\2, ] + A[n/d\2+1, ]))/if(d%2, 2, 1) )))}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Oct 02 2019

T(n,k) = A276543(n,k) - A285037(n,k). - Andrew Howroyd, Sep 20 2019

T(10,6) corrected by Mohammad Hadi Shekarriz, Sep 28 2019

a(56)-a(78) from Andrew Howroyd, Sep 28 2019

A276544 Triangle read by rows: T(n,k) = number of primitive (aperiodic) reversible string structures with n beads using exactly k different colors.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 4, 4, 1, 0, 9, 15, 6, 1, 0, 16, 49, 37, 9, 1, 0, 35, 160, 183, 76, 12, 1, 0, 66, 498, 876, 542, 142, 16, 1, 0, 133, 1544, 3930, 3523, 1346, 242, 20, 1, 0, 261, 4715, 17179, 21392, 11511, 2980, 390, 25, 1

Offset: 1

Andrew Howroyd, Apr 09 2017

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

			Triangle starts
1
0   1
0   2    1
0   4    4     1
0   9   15     6     1
0  16   49    37     9     1
0  35  160   183    76    12    1
0  66  498   876   542   142   16   1
0 133 1544  3930  3523  1346  242  20  1
0 261 4715 17179 21392 11511 2980 390 25 1
...
Primitive reversible word structures are:
n=1: a => 1
n=2: ab => 1
n=3: aab, aba; abc => 2 + 1
n=4: aaab, aaba, aabb, abba => 4 (k=2)
     aabc, abac, abbc, abca => 4 (k=3)

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 (first 50 rows)

Columns 2-6 are A056336, A056337, A056338, A056339, A056340.
Partial row sums include A056331, A056332, A056333, A056334, A056335.
Row sums are A276549.
Cf. A284871, A284949, A277504, A137651, A107424, A276543.

Ach[n_, k_] := Ach[n, k] = Switch[k, 0, If[n == 0, 1, 0], 1, If[n > 0, 1, 0], _, If[OddQ[n], Sum[Binomial[(n - 1)/2, i] Ach[n - 1 - 2 i, k - 1], {i, 0, (n - 1)/2}], Sum[Binomial[n/2 - 1, i] (Ach[n - 2 - 2 i, k - 1] + 2^i Ach[n - 2 - 2 i, k - 2]), {i, 0, n/2 - 1}]]]
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] (StirlingS2[#, k] + Ach[#, k])/2& ];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 29 2018, after Robert A. Russell and Andrew Howroyd *)

\\ here Ach is A304972 as matrix.
Ach(n,m=n)={my(M=matrix(n, m, i, k, i>=k)); for(i=3, n, for(k=2, m, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
T(n,m=n)={my(M=matrix(n, m, i, k, stirling(i, k, 2)) + Ach(n,m)); matrix(n, m, i, k, sumdiv(i, d, moebius(i/d)*M[d,k]))/2}
{ my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 09 2020

T(n, k) = Sum_{d|n} mu(n/d) * A284949(d, k).

A305749 T(n,k) is the number of achiral color patterns (set partitions) in a row or loop of length n with k or fewer colors (sets).

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, 18, 8, 1, 1, 2, 3, 7, 12, 27, 27, 16, 1, 1, 2, 3, 7, 12, 30, 43, 54, 16, 1, 1, 2, 3, 7, 12, 31, 55, 107, 81, 32, 1, 1, 2, 3, 7, 12, 31, 58, 141, 171, 162, 32, 1, 1, 2, 3, 7, 12, 31, 59, 159, 266, 427, 243, 64, 1, 1, 2, 3, 7, 12, 31, 59, 163, 312, 688, 683, 486, 64, 1

Offset: 1

Robert A. Russell, Jun 09 2018

An equivalent color pattern is obtained when we permute the colors. Thus all permutations of ABC are equivalent, as are AAABB and BBBAA. A color pattern is achiral if it is equivalent to its reversal. Rotations of the colors of a loop are equivalent, so for loops AAABCB = BAAABC = CBAAAB.

			The array begins at T(1,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     2 ...
1  2   3    3    3     3     3     3     3     3     3     3     3 ...
1  4   6    7    7     7     7     7     7     7     7     7     7 ...
1  4   9   11   12    12    12    12    12    12    12    12    12 ...
1  8  18   27   30    31    31    31    31    31    31    31    31 ...
1  8  27   43   55    58    59    59    59    59    59    59    59 ...
1 16  54  107  141   159   163   164   164   164   164   164   164 ...
1 16  81  171  266   312   334   338   339   339   339   339   339 ...
1 32 162  427  688   883   963   993   998   999   999   999   999 ...
1 32 243  683 1313  1774  2069  2169  2204  2209  2210  2210  2210 ...
1 64 486 1707 3407  5103  6119  6634  6789  6834  6840  6841  6841 ...
1 64 729 2731 6532 10368 13524 15080 15790 15975 16026 16032 16033 ...
a(n) are the terms of this array read by antidiagonals.
For T(4,3)=6, the achiral pattern rows are AAAA, AABB, ABAB, ABBA, ABBC, and ABCA. The achiral pattern loops are AAAA, AAAB, AABB, ABAB, AABC, and ABAC.

Columns 1-6 are A057427, A016116, A182522, A305750, A305751, and A305752.

Columns converge to the right to 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]]; (* A304972 *)
Table[Sum[Ach[n, j], {j, 1, k - n + 1}], {k, 1, 15}, {n, 1, k}] // Flatten

T(n,k) = Sum_{j=0..k} 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 <= 1 & n==k].

T(n,k) = Sum_{j=1..k} A304972(n,j).

A320647 Triangle read by rows: T(n,k) is the number of chiral pairs of cycles of length n (1) with a color pattern of exactly k colors or equivalently (2) partitioned into k nonempty subsets.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 2, 0, 0, 0, 1, 12, 17, 4, 0, 0, 0, 2, 44, 84, 51, 9, 0, 0, 0, 7, 137, 388, 339, 125, 15, 0, 0, 0, 12, 408, 1586, 2010, 1054, 258, 24, 0, 0, 0, 31, 1190, 6405, 10900, 7928, 2761, 490, 35, 0, 0, 0, 58, 3416, 24927, 56700, 54383, 25680, 6392, 859, 51, 0, 0, 0, 126, 9730, 96404, 286888, 356594, 218246, 72284, 13472, 1420, 68, 0, 0

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.

			The triangle begins with T(1,1):
  0;
  0,   0;
  0,   0,    0;
  0,   0,    0,     0;
  0,   0,    0,     0,      0;
  0,   0,    4,     2,      0,      0;
  0,   1,   12,    17,      4,      0,      0;
  0,   2,   44,    84,     51,      9,      0,     0;
  0,   7,  137,   388,    339,    125,     15,     0,     0;
  0,  12,  408,  1586,   2010,   1054,    258,    24,     0,    0;
  0,  31, 1190,  6405,  10900,   7928,   2761,   490,    35,    0,  0;
  0,  58, 3416, 24927,  56700,  54383,  25680,  6392,   859,   51,  0, 0;
  0, 126, 9730, 96404, 286888, 356594, 218246, 72284, 13472, 1420, 68, 0, 0;
  ...
For T(6,3)=4, the chiral pairs are AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, and AABACC-AABBAC.
For T(6,4)=2, the chiral pairs are AABACD-AABCAD and AABCBD-AABCDC.

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

Columns 1-6 are A000004, A059053, A320643, A320644, A320645, A320646.
Row sums are A320749.
Cf. A152175 (oriented), A152176 (unoriented), A304972 (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]]
Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/(2n)-Ach[n,k]/2,{n,12},{k,n}] // 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)={(R(n) - Ach(n))/2}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

T(n,k) = (A152175(n,k) - A304972(n,k)) / 2 = A152175(n,k) - A152176(n,k) = A152176(n,k) - A304972(n,k).

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

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

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 1, 0, 0, 0, 0, 0, 0, 6, 13, 2, 0, 0, 0, 0, 0, 0, 6, 30, 46, 7, 0, 0, 0, 0, 0, 0, 6, 34, 130, 144, 12, 0, 0, 0, 0, 0, 0, 6, 34, 181, 532, 420, 31, 0, 0, 0, 0, 0, 0, 6, 34, 190, 871, 2006, 1221, 58, 0, 0, 0, 0, 0, 0, 6, 34, 190, 996, 4016, 7626, 3474, 126, 0, 0, 0, 0, 0, 0, 6, 34, 190, 1011, 5070, 18526, 28401, 9856, 234, 0

Offset: 1

Robert A. Russell, Oct 21 2018

Two color patterns are equivalent if the colors are permuted.

Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.

			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      0      0      0 ...
0  0    0     0     0      0      0      0      0      0      0      0 ...
0  0    0     0     0      0      0      0      0      0      0      0 ...
0  0    0     0     0      0      0      0      0      0      0      0 ...
0  0    4     6     6      6      6      6      6      6      6      6 ...
0  1   13    30    34     34     34     34     34     34     34     34 ...
0  2   46   130   181    190    190    190    190    190    190    190 ...
0  7  144   532   871    996   1011   1011   1011   1011   1011   1011 ...
0 12  420  2006  4016   5070   5328   5352   5352   5352   5352   5352 ...
0 31 1221  7626 18526  26454  29215  29705  29740  29740  29740  29740 ...
0 58 3474 28401 85101 139484 165164 171556 172415 172466 172466 172466 ...
For T(6,4)=6, the chiral pairs are AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, AABACC-AABBAC, AABACD-AABCAD and AABCBD-AABCDC.

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

Partial row sums of A320647.
Columns 1-6 are A000004, A059053, A320743, A320744, A320745, A320746
For increasing k, columns converge to A320749.
Cf. A320747 (oriented), A320748 (unoriented), 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) - A320748(n,k)= A320748(n,k) - A305749(n,k).

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

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 4, 6, 1, 1, 2, 4, 10, 10, 1, 1, 2, 4, 11, 25, 20, 1, 1, 2, 4, 11, 31, 70, 36, 1, 1, 2, 4, 11, 32, 107, 196, 72, 1, 1, 2, 4, 11, 32, 116, 379, 574, 136, 1, 1, 2, 4, 11, 32, 117, 455, 1451, 1681, 272, 1

Offset: 1

Robert A. Russell, Oct 27 2018

Two color patterns are equivalent if the colors are permuted.
In an unoriented row, chiral pairs are counted as one.
T(n,k) = Pi_k(P_n) which is the number of non-equivalent 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. - Mohammad Hadi Shekarriz, Aug 21 2019
From Allan Bickle, Apr 05 2022: (Start)
The columns count unlabeled k-paths with n+k+2 vertices. (A k-path with order n at least k+2 is a k-tree with exactly two k-leaves (vertices of degree k). It can be constructed from a clique with k+1 vertices by iteratively adding a new degree k vertex adjacent to an existing clique containing an existing k-leaf.)
Recurrences for the columns appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)

			Array begins with T(1,1):
  1   1     1     1      1      1      1      1      1      1      1 ...
  1   2     2     2      2      2      2      2      2      2      2 ...
  1   3     4     4      4      4      4      4      4      4      4 ...
  1   6    10    11     11     11     11     11     11     11     11 ...
  1  10    25    31     32     32     32     32     32     32     32 ...
  1  20    70   107    116    117    117    117    117    117    117 ...
  1  36   196   379    455    467    468    468    468    468    468 ...
  1  72   574  1451   1993   2135   2151   2152   2152   2152   2152 ...
  1 136  1681  5611   9134  10480  10722  10742  10743  10743  10743 ...
  1 272  5002 22187  43580  55091  58071  58461  58486  58487  58487 ...
  1 528 14884 87979 211659 301633 333774 339764 340359 340389 340390 ...
For T(4,3)=10, the patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, AAAB, AABA, AABC, ABAC, the last four being chiral with partners ABBB, ABAA, ABCC, and ABCB.

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

B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.

Columns 1-7 are A000012, A005418, A001998(n-1), A056323, A056324, A056325, A345207.
As k increases, columns converge to A103293(n+1).
Cf. transpose of A278984 (oriented), A320751 (chiral), A305749 (achiral).
Partial column sums of A284949.

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) - A320751(n,k) = A320751(n,k) + A305749(n,k).
T(n,k) = Sum_{j=1..k} A284949(n,j).

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

A320525 Triangle read by rows: T(n,k) = number of chiral pairs of color patterns (set partitions) in a row of length n using exactly k colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 6, 10, 4, 0, 0, 12, 40, 28, 6, 0, 0, 28, 141, 167, 64, 9, 0, 0, 56, 464, 824, 508, 124, 12, 0, 0, 120, 1480, 3840, 3428, 1300, 220, 16, 0, 0, 240, 4600, 16920, 21132, 11316, 2900, 360, 20, 0, 0, 496, 14145, 72655, 123050, 89513, 31846, 5890, 560, 25, 0, 0, 992, 43052, 305140, 688850, 660978, 313190, 79256, 11060, 830, 30, 0

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.

If the top entry of the triangle is changed from 0 to 1, this is the number of non-equivalent distinguishing partitions of the path on n vertices (n >= 1) with exactly k parts (1 <= k <= n). - Bahman Ahmadi, Aug 21 2019

			Triangle begins with T(1,1):
  0;
  0,   0;
  0,   1,     0;
  0,   2,     2,      0;
  0,   6,    10,      4,      0;
  0,  12,    40,     28,      6,      0;
  0,  28,   141,    167,     64,      9,      0;
  0,  56,   464,    824,    508,    124,     12,     0;
  0, 120,  1480,   3840,   3428,   1300,    220,    16,     0;
  0, 240,  4600,  16920,  21132,  11316,   2900,   360,    20,   0;
  0, 496, 14145,  72655, 123050,  89513,  31846,  5890,   560,  25, 0;
  0, 992, 43052, 305140, 688850, 660978, 313190, 79256, 11060, 830, 30, 0;
  ...
For T(3,2)=1, the chiral pair is AAB-ABB.  For T(4,2)=2, the chiral pairs are AAAB-ABBB and AABA-ABAA.  For T(5,2)=6, the chiral pairs are AAAAB-ABBBB, AAABA-ABAAA, AAABB-AABBB, AABAB-ABABB, AABBA-ABBAA, and ABAAB-ABBAB.

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.

Columns 1-6 are A000004, A122746(n-2), A320526, A320527, A320528, A320529.
Row sums are A320937.
Cf. A008277 (oriented), A284949 (unoriented), A304972 (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 *)
Table[(StirlingS2[n, k] - Ach[n, k])/2, {n, 1, 12}, {k, 1, n}] // Flatten

\\ here 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)) - Ach(n))/2}
{ my(A=T(10)); for(n=1, #A, print(A[n,1..n])) } \\ Andrew Howroyd, Sep 18 2019

T(n,k) = (S2(n,k) - A(n,k))/2, where 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].

T(n,k) = (A008277(n,k) - A304972(n,k)) / 2 = A008277(n,k) - A284949(n,k) = A284949(n,k) - A304972(n,k).

cp's OEIS Frontend

A309784 T(n,k) is the number of non-equivalent distinguishing coloring partitions of the cycle on n vertices with exactly k parts. Regular triangle read by rows, n >= 1, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A276544 Triangle read by rows: T(n,k) = number of primitive (aperiodic) reversible string structures with n beads using exactly k different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A305749 T(n,k) is the number of achiral color patterns (set partitions) in a row or loop of length n with k or fewer colors (sets).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A320647 Triangle read by rows: T(n,k) is the number of chiral pairs of cycles of length n (1) with a color pattern of exactly k colors or equivalently (2) partitioned into k nonempty subsets.

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs