A327611 -id:A327611 - cp's OEIS frontend

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.

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

A327610 Number of length n reversible string structures that are not palindromic using exactly three different colors.

Original entry on oeis.org

0, 0, 1, 4, 14, 49, 154, 496, 1520, 4705, 14266, 43384, 130844, 394849, 1187614, 3571936, 10729040, 32222785, 96724306, 290313064, 871172324, 2614069249, 7843168774, 23531688976, 70598997560, 211805640865, 635432906746, 1906333059544, 5719063904204

Offset: 1

Andrew Howroyd, Sep 18 2019

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (6,-6,-24,49,6,-66,36).

Column k=3 of A309748.

Cf. A000392, A056327, A284949, A327611.

concat([0,0], Vec((1 - 2*x - 4*x^2 + 13*x^3 - 9*x^4)/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 2*x^2)*(1 - 3*x^2)) + O(x^30)))

a(n) = A056327 - A000392(ceiling(n/2)).
a(n) = 6*a(n-1) - 6*a(n-2) - 24*a(n-3) + 49*a(n-4) + 6*a(n-5) - 66*a(n-6) + 36*a(n-7) for n > 7.
G.f.: x^3*(1 - 2*x - 4*x^2 + 13*x^3 - 9*x^4)/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 2*x^2)*(1 - 3*x^2)).

cp's OEIS Frontend

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