A309635 The number of non-equivalent distinguishing coloring partitions of the path on n vertices (n>=1) with at most k parts (k>=1). Square array read by descending antidiagonals: 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, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 4, 0, 1, 1, 2, 8, 6, 0, 1, 1, 2, 9, 20, 16, 0, 1, 1, 2, 9, 26, 65, 28, 0, 1, 1, 2, 9, 27, 102, 182, 64, 0, 1, 1, 2, 9, 27, 111, 364, 560, 120, 0, 1, 1, 2, 9, 27, 112, 440, 1436, 1640, 256, 0

Offset: 1

Author

Mohammad Hadi Shekarriz, Aug 13 2019

Keywords

• nonn
• tabl

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 most k parts. This sequence gives A(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 at most k parts.

Note that, for any graph G, Psi_k(G) = Sum_{i<=k} psi_i(G), where psi_i(G) is the number of non-equivalent distinguishing coloring partitions of G with exactly i parts. For instance, here we have T(n,k) = Sum_{i<=k} A309748(n,i).

Examples

			Table begins:
  ======================================================================
  n\k| 1    2     3      4      5      6      7      8      9     10
  ---+------------------------------------------------------------------
   1 | 1,   1,    1,     1,     1,     1,     1,     1,     1,     1 ...
   2 | 0,   1,    1,     1,     1,     1,     1,     1,     1,     1 ...
   3 | 0,   1,    2,     2,     2,     2,     2,     2,     2,     2 ...
   4 | 0,   4,    8,     9,     9,     9,     9,     9,     9,     9 ...
   5 | 0,   6,   20,    26,    27,    27,    27,    27,    27,    27 ...
   6 | 0,  16,   65,   102,   111,   112,   112,   112,   112,   112 ...
   7 | 0,  28,  182,   364,   440,   452,   453,   453,   453,   453 ...
   8 | 0,  64,  560,  1436,  1978,  2120,  2136,  2137,  2137,  2137 ...
   9 | 0, 120, 1640,  5560,  9082, 10428, 10670, 10690, 10691, 10691 ...
  10 | 0, 256, 4961, 22136, 43528, 55039, 58019, 58409, 58434, 58435 ...
  ...
For n=4, we can partition the vertices of P_4 into at most 3 parts in 8 ways such that all these partitions induce distinguishing colorings for P_4 and that all the 8 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 } }
    { { 1 }, { 2, 3, 4 } }
    { { 1, 2 }, { 3, 4 } }
    { { 1, 2, 4 }, { 3 } }
    { { 1, 3 }, { 2, 4 } }
		

Links

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

Crossrefs

Column k=2 is A007179(n > 1).

Cf. A284949, A309748.

Formula

T(n, k) = Sum_{i=1..k} A309748(n,i).