

A309528


The number of nonequivalent distinguishing colorings of the cycle on n vertices with at most k colors (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 permissible colors.


6



0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 4, 3, 0, 0, 0, 0, 10, 15, 12, 1, 0, 0, 0, 20, 45, 72, 37, 2, 0, 0, 0, 35, 105, 252, 266, 117, 6, 0, 0, 0, 56, 210, 672, 1120, 1044, 333, 14, 0, 0, 0, 84, 378, 1512, 3515, 5270, 3788, 975, 30, 0, 0, 0, 120, 630, 3024, 9121, 19350, 23475, 14056, 2712, 62, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,18


COMMENTS

A vertexcoloring 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. Two vertexcolorings of a graph are called equivalent if there is an automorphism of the graph which preserves the colors of the vertices. Given a graph G, we use the notation Phi_k(G) to denote the number of nonequivalent distinguishing colorings of G with at most k colors. The sequence here, displays A(n,k)=Phi_k(C_n), i.e., the number of nonequivalent distinguishing colorings of the cycle C_n on n vertices with at most k colors.


LINKS



FORMULA



EXAMPLE

The table begins:
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 0, 1, 4, 10, 20, 35, 56, 84, 120, ...
0, 0, 3, 15, 45, 105, 210, 378, 630, 990, ...
0, 0, 12, 72, 252, 672, 1512, 3024, 5544, 9504, ...
0, 1, 37, 266, 1120, 3515, 9121, 20692, 42456, 80565, ...
0, 2, 117, 1044, 5270, 19350, 57627, 147752, 338364, 709290, ...
0, 6, 333, 3788, 23475, 102690, 355446, 1039248, 2673810, 6222150, ...
0, 14, 975, 14056, 106950, 555990, 2233469, 7440160, 21493836, 55505550, ...
0, 30, 2712, 51132, 483504, 3009426, 14089488, 53611992, 174189024, 499720518, ...

For n=4, we can color the vertices of the cycle C_4 with at most 3 colors, in 3 ways, such that all the colorings distinguish the graph (i.e., no nonidentity automorphism of C_4 preserves the coloring) and that all the three colorings are nonequivalent. The color classes are as follows:
{ { 1 }, { 2 }, { 3, 4 } }
{ { 1 }, { 2, 3 }, { 4 } }
{ { 1, 2 }, { 3 }, { 4 } }


PROG

(PARI) A(n, k)={sumdiv(n, d, moebius(n/d)*(k^d/n  if(d%2, k^((d+1)/2), (k+1)*k^(d/2)/2)))/2} \\ Andrew Howroyd, Aug 11 2019


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



