A309785 The number of non-equivalent distinguishing coloring partitions of the cycle on n vertices with at most k parts (k>=1). The cycle graph is defined for n>=3; extended to n=1,2 using the closed form. Square array read by descending antidiagonals: the rows are indexed by n, the number of vertices of the cycle, and the columns are indexed by k, the number of parts.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 2, 4, 1, 0, 0, 0, 1, 2, 6, 9, 1, 0, 0, 0, 1, 2, 7, 19, 26, 4, 0, 0, 0, 1, 2, 7, 22, 58, 66, 7, 0, 0, 0, 1, 2, 7, 23, 74, 195, 183, 18, 0, 0, 0, 1, 2, 7, 23, 77, 279, 651, 488, 31, 0

Offset: 1

Author

Bahman Ahmadi, Aug 17 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 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 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} A309784(n,i).

Examples

			Table begins:
  =============================================================
  n\k| 1   2    3     4     5     6     7     8     9    10
  ---+---------------------------------------------------------
   1 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0 ...
   2 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0 ...
   3 | 0,  0,   1,    1,    1,    1,    1,    1,    1,    1 ...
   4 | 0,  0,   1,    2,    2,    2,    2,    2,    2,    2 ...
   5 | 0,  0,   4,    6,    7,    7,    7,    7,    7,    7 ...
   6 | 0,  1,   9,   19,   22,   23,   23,   23,   23,   23 ...
   7 | 0,  1,  26,   58,   74,   77,   78,   78,   78,   78 ...
   8 | 0,  4,  66,  195,  279,  306,  310,  311,  311,  311 ...
   9 | 0,  7, 183,  651, 1084, 1255, 1292, 1296, 1297, 1297 ...
  10 | 0, 18, 488, 2294, 4554, 5802, 6140, 6194, 6199, 6200 ...
...
-------
For n=6, we can partition the vertices of C_6 into at most 4 parts in 10 ways such that all these partitions induce distinguishing colorings for C_6 and that all the 10 partitions are non-equivalent.
    { { 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, 3 }, { 4 }, { 5, 6 } }
    { { 1 }, { 2, 3 }, { 4, 6 }, { 5 } }
    { { 1 }, { 2, 4 }, { 3, 6 }, { 5 } }
    { { 1 }, { 2, 4, 6 }, { 3 }, { 5 } }
    { { 1 }, { 2, 5 }, { 3, 6 }, { 4 } }
		

Links

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

Crossrefs

Cf. A309635, A309784.

Formula

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