cp's OEIS Frontend

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

%I A324802 #38 Nov 05 2019 06:00:19
%S A324802 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,2,0,0,0,1,12,17,4,0,0,0,2,43,82,
%T A324802 49,9,0,0,0,7,137,388,339,125,15,0,0,0,12,404,1572,1994,1044,254,24,0,
%U A324802 0,0,31,1190,6405,10900,7928,2761,490,35,0,0,0,57,3394,24853,56586,54272,25609,6365,850,51,0,0
%N A324802 T(n,k) is the number of non-equivalent distinguishing partitions of the cycle on n vertices with exactly k parts. Regular triangle read by rows, n >= 1, 1 <= k <= n.
%C A324802 The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.
%C A324802 Two partitions P1 and P2 of a the vertex set of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. A distinguishing partition is a partition of the vertex set of G such that no nontrivial automorphism of G can preserve it. Here T(n,k)=xi_k(C_n), the number of non-equivalent distinguishing partitions of the cycle on n vertices, with exactly k parts.
%C A324802 Number of n-bead bracelet structures using exactly k different colored beads that are not self-equivalent under either a nonzero rotation or reversal (turning over bracelet). Comparable sequences for unoriented (reversible) strings and necklaces (cyclic group) are A320525 and A327693. - _Andrew Howroyd_, Sep 23 2019
%H A324802 Bahman Ahmadi, <a href="/A324802/a324802.txt">GAP Program</a>
%H A324802 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 A324802 T(n,k) = A324803(n,k) - A324803(n,k-1).
%e A324802 Triangle begins:
%e A324802   0;
%e A324802   0,  0;
%e A324802   0,  0,   0;
%e A324802   0,  0,   0,    0;
%e A324802   0,  0,   0,    0,    0;
%e A324802   0,  0,   4,    2,    0,    0;
%e A324802   0,  1,  12,   17,    4,    0,   0;
%e A324802   0,  2,  43,   82,   49,    9,   0,  0;
%e A324802   0,  7, 137,  388,  339,  125,  15,  0, 0;
%e A324802   0, 12, 404, 1572, 1994, 1044, 254, 24, 0, 0;
%e A324802   ...
%e A324802 For n=7, we can partition the vertices of the cycle C_7 with exactly 3 parts, in 12 ways, such that all these partitions are distinguishing for C_7 and that all the 12 partitions are non-equivalent. The partitions are as follows:
%e A324802     { { 1 }, { 2, 3 }, { 4, 5, 6, 7 } },
%e A324802     { { 1 }, { 2, 3, 4, 6 }, { 5, 7 } },
%e A324802     { { 1 }, { 2, 3, 4, 7 }, { 5, 6 } },
%e A324802     { { 1 }, { 2, 3, 5, 6 }, { 4, 7 } },
%e A324802     { { 1 }, { 2, 3, 5, 7 }, { 4, 6 } },
%e A324802     { { 1 }, { 2, 3, 6 }, { 4, 5, 7 } },
%e A324802     { { 1 }, { 2, 3, 7 }, { 4, 5, 6 } },
%e A324802     { { 1 }, { 2, 4, 5, 6 }, { 3, 7 } },
%e A324802     { { 1 }, { 2, 4, 7 }, { 3, 5, 6 } },
%e A324802     { { 1, 2 }, { 3, 4, 6 }, { 5, 7 } },
%e A324802     { { 1, 2 }, { 3, 5, 6 }, { 4, 7 } },
%e A324802     { { 1, 2, 4 }, { 3, 6 }, { 5, 7 } }.
%e A324802 From _Andrew Howroyd_, Sep 23 2019: (Start)
%e A324802 For n=6, k=4 the partitions are:
%e A324802     { { 1, 2, 4 }, { 3 }, { 5 }, { 6 } },
%e A324802     { { 1, 2 }, { 3, 5 }, { 4 }, { 6 } }.
%e A324802 These correspond to the bracelet structures AABACD and AABCBD.
%e A324802 (End)
%Y A324802 Column k=2 is A327734.
%Y A324802 Row sums are A327740.
%Y A324802 Cf. A309784, A309785, A320525, A320748, A152176, A320647, A324803, A327693.
%K A324802 nonn,tabl
%O A324802 1,18
%A A324802 _Bahman Ahmadi_, Sep 04 2019
%E A324802 a(56)-a(78) from _Andrew Howroyd_, Sep 23 2019