The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A309528 The number of non-equivalent 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 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. Two vertex-colorings 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 non-equivalent 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 non-equivalent distinguishing colorings of the cycle C_n on n vertices with at most k colors. LINKS Table of n, a(n) for n=1..78. B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019. FORMULA A(n,k) = (A074650(n,k) - A284856(n,k))/2. - Andrew Howroyd, Aug 11 2019 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 non-identity automorphism of C_4 preserves the coloring) and that all the three colorings are non-equivalent. 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 Columns k=2..5 for n >= 3 are A032239, A032240, A032241, A032242. Cf. A074650, A284856. Different from A293496. Sequence in context: A125856 A057110 A073275 * A293496 A290326 A284947 Adjacent sequences: A309525 A309526 A309527 * A309529 A309530 A309531 KEYWORD nonn,tabl AUTHOR Bahman Ahmadi, Aug 06 2019 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 10 03:15 EDT 2023. Contains 363186 sequences. (Running on oeis4.)