cp's OEIS Frontend

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

%I A309784 #40 Nov 05 2019 05:59:40
%S A309784 0,0,0,0,0,1,0,0,1,1,0,0,4,2,1,0,1,8,10,3,1,0,1,25,32,16,3,1,0,4,62,
%T A309784 129,84,27,4,1,0,7,176,468,433,171,37,4,1,0,18,470,1806,2260,1248,338,
%U A309784 54,5,1,0,31,1311,6780,11515,8388,3056,590,70,5,1,0,70,3620,25917,58312,56065,26695,6907,1014,96,6,1
%N A309784 T(n,k) is the number of non-equivalent distinguishing coloring partitions of the cycle on n vertices with exactly k parts. Regular triangle read by rows, n >= 1, 1 <= k <= n.
%C A309784 The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.
%C A309784 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 exactly k parts. For n>=3, 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 exactly k parts.
%C A309784 T(n,k) is the number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using exactly k different colored beads. - _Andrew Howroyd_, Sep 20 2019
%H A309784 Andrew Howroyd, <a href="/A309784/b309784.txt">Table of n, a(n) for n = 1..1275</a>
%H A309784 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.
%H A309784 Mohammad Hadi Shekarriz, <a href="/A309784/a309784_1.txt">GAP Program</a>
%F A309784 T(n,k) = A276543(n,k) - A285037(n,k). - _Andrew Howroyd_, Sep 20 2019
%e A309784 The triangle begins:
%e A309784   0;
%e A309784   0,  0;
%e A309784   0,  0,   1;
%e A309784   0,  0,   1,    1;
%e A309784   0,  0,   4,    2,    1;
%e A309784   0,  1,   8,   10,    3,    1;
%e A309784   0,  1,  25,   32,   16,    3,   1;
%e A309784   0,  4,  62,  129,   84,   27,   4,  1;
%e A309784   0,  7, 176,  468,  433,  171,  37,  4, 1;
%e A309784   0, 18, 470, 1806, 2260, 1248, 338, 54, 5, 1;
%e A309784   ...
%e A309784 For n=6, we can partition the vertices of C_6 into exactly 3 parts in 8 ways such that all these partitions induce distinguishing colorings for C_6 and that all the 8 partitions are non-equivalent. The partitions are as follows:
%e A309784     { { 1 }, { 2 }, { 3, 4, 5, 6 } }
%e A309784     { { 1 }, { 2, 3 }, { 4, 5, 6 } }
%e A309784     { { 1 }, { 2, 3, 4, 6 }, { 5 } }
%e A309784     { { 1 }, { 2, 3, 5 }, { 4, 6 } }
%e A309784     { { 1 }, { 2, 3, 6 }, { 4, 5 } }
%e A309784     { { 1 }, { 2, 4, 5 }, { 3, 6 } }
%e A309784     { { 1, 2 }, { 3, 4 }, { 5, 6 } }
%e A309784     { { 1, 2 }, { 3, 5 }, { 4, 6 } }
%e A309784 For n=6, the above 8 partitions can be written as the following 3 colored bracelet structures: ABCCCC, ABBCCC, ABBBCB, ABBCBC, ABBCCB, ABCBBC, AABBCC, AABCBC. - _Andrew Howroyd_, Sep 22 2019
%o A309784 (PARI) \\ Ach is A304972 and R is A152175 as square matrices.
%o A309784 Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
%o A309784 R(n)={Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
%o A309784 T(n)={my(A=Ach(n), M=R(n), S=matrix(n, n, n, k, stirling(n, k, 2))); Mat(vectorv(n, n, sumdiv(n, d, moebius(d)*(M[n/d,] + A[n/d,])/2 - moebius(d)*(S[(n/d+1)\2, ] + S[n/d\2+1, ] + if((n-d)%2, A[(n/d+1)\2, ] + A[n/d\2+1, ]))/if(d%2, 2, 1) )))}
%o A309784 { my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ _Andrew Howroyd_, Oct 02 2019
%Y A309784 Column k=2 appears to be A011948.
%Y A309784 Columns k=3..4 are A328038, A328039.
%Y A309784 Row sums are A328035.
%Y A309784 Cf. A107424, A152175, A152176, A276543, A276544, A285012, A285037, A309748, A309785.
%K A309784 nonn,tabl
%O A309784 1,13
%A A309784 _Mohammad Hadi Shekarriz_, Aug 17 2019
%E A309784 T(10,6) corrected by _Mohammad Hadi Shekarriz_, Sep 28 2019
%E A309784 a(56)-a(78) from _Andrew Howroyd_, Sep 28 2019