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,8

Comments

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

Links

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

Formula

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

Example

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 } }

Prog

(PARI) \\ 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

Crossrefs

Columns k=2..4 are A007179, A327610, A327611.

Row sums are A327612(n > 1).

Cf. A284949, A304972, A309635, A309784.

Sequence in context: A336302 A163353 A164612 * A180401 A354043 A057270

Adjacent sequences: A309745 A309746 A309747 * A309749 A309750 A309751

Keyword

nonn,tabl

Author

Mohammad Hadi Shekarriz, Aug 15 2019

Extensions

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

Status

approved