cp's OEIS Frontend

A309651 T(n,k) is the number of non-equivalent distinguishing colorings of the cycle on n vertices with exactly k colors (k>=1). Regular triangle read by rows, n >= 1, 1 <= k <= n.

%I A309651 #41 Nov 05 2019 06:00:15
%S A309651 0,0,0,0,0,1,0,0,3,3,0,0,12,24,12,0,1,34,124,150,60,0,2,111,588,1200,
%T A309651 1080,360,0,6,315,2484,7845,11970,8820,2520,0,14,933,10240,46280,
%U A309651 105840,129360,80640,20160,0,30,2622,40464,254664,821592,1481760,1512000,816480,181440
%N A309651 T(n,k) is the number of non-equivalent distinguishing colorings of the cycle on n vertices with exactly k colors (k>=1). Regular triangle read by rows, n >= 1, 1 <= k <= n.
%C A309651 The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.
%C A309651 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 exactly k colors. The sequence here, displays T(n,k)=phi_k(C_n), i.e., the number of non-equivalent distinguishing colorings of the cycle C_n on n vertices with exactly k colors.
%C A309651 From _Andrew Howroyd_, Aug 15 2019: (Start)
%C A309651 First differs from A305541 at n = 6.
%C A309651 Also the number of n-bead asymmetric bracelets with exactly k different colored beads. More precisely the number of chiral pairs of primitive (aperiodic) color loops of length n with exactly k different colors. For example, for n=4 and k = 3, there are 3 achiral loops (1213, 1232, 1323) and 3 pairs of chiral loops (1123/1132, 1223/1322, 1233/1332).
%C A309651 (End)
%H A309651 Andrew Howroyd, <a href="/A309651/b309651.txt">Table of n, a(n) for n = 1..1275</a> (first 50 rows)
%H A309651 B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, <a href="https://arxiv.org/abs/1910.12102">Number of Distinguishing Colorings and Partitions</a>, arXiv:1910.12102 [math.CO], 2019.
%F A309651 Let n>2. For any k >= floor(n/2) we have phi_k(C_n)=k! * Stirling2(n,k)/2n.
%F A309651 T(n, k) = Sum_{i=2..k} (-1)^(k-i)*binomial(k,i)*A309528(n, i). - _Andrew Howroyd_, Aug 12 2019
%F A309651 Column k is the Moebius transform of column k of A305541. - _Andrew Howroyd_, Sep 13 2019
%e A309651 The triangle begins:
%e A309651   0
%e A309651   0,  0;
%e A309651   0,  0,    1;
%e A309651   0,  0,    3,     3;
%e A309651   0,  0,   12,    24,     12;
%e A309651   0,  1,   34,   124,    150,     60;
%e A309651   0,  2,  111,   588,   1200,   1080,     360;
%e A309651   0,  6,  315,  2484,   7845,  11970,    8820,    2520;
%e A309651   0, 14,  933, 10240,  46280, 105840,  129360,   80640,  20160;
%e A309651   0, 30, 2622, 40464, 254664, 821592, 1481760, 1512000, 816480, 181440;
%e A309651   ...
%e A309651 For n=4, we can color the vertices of the cycle C_4 with exactly 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:
%e A309651 { { 1 }, { 2 }, { 3, 4 } }
%e A309651 { { 1 }, { 2, 3 }, { 4 } }
%e A309651 { { 1, 2 }, { 3 }, { 4 } }
%o A309651 (PARI) \\ U(n,k) is A309528
%o A309651 U(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}
%o A309651 T(n,k)={sum(i=2, k, (-1)^(k-i)*binomial(k,i)*U(n,i))} \\ _Andrew Howroyd_, Aug 12 2019
%Y A309651 Columns k=2..4 are A032239(n>=3), A326660, A326789.
%Y A309651 Row sums are A326888.
%Y A309651 Cf. A001710, A254040, A309528, A305541.
%K A309651 nonn,tabl
%O A309651 1,9
%A A309651 _Bahman Ahmadi_, Aug 11 2019