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

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

Links

Table of n, a(n) for n=1..78.

Bahman Ahmadi, GAP Program

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

Formula

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

Example

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

Crossrefs

Cf. A309635, A309784.

Sequence in context: A287651 A365951 A163259 * A188668 A366463 A366466

Adjacent sequences: A309782 A309783 A309784 * A309786 A309787 A309788

Keyword

nonn,tabl

Author

Bahman Ahmadi, Aug 17 2019

Status

approved