login
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.
5
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, 49, 9, 0, 0, 0, 7, 137, 388, 339, 125, 15, 0, 0, 0, 12, 404, 1572, 1994, 1044, 254, 24, 0, 0, 0, 31, 1190, 6405, 10900, 7928, 2761, 490, 35, 0, 0, 0, 57, 3394, 24853, 56586, 54272, 25609, 6365, 850, 51, 0, 0
OFFSET
1,18
COMMENTS
The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.
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.
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
LINKS
Bahman Ahmadi, GAP Program
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
FORMULA
T(n,k) = A324803(n,k) - A324803(n,k-1).
EXAMPLE
Triangle begins:
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, 49, 9, 0, 0;
0, 7, 137, 388, 339, 125, 15, 0, 0;
0, 12, 404, 1572, 1994, 1044, 254, 24, 0, 0;
...
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:
{ { 1 }, { 2, 3 }, { 4, 5, 6, 7 } },
{ { 1 }, { 2, 3, 4, 6 }, { 5, 7 } },
{ { 1 }, { 2, 3, 4, 7 }, { 5, 6 } },
{ { 1 }, { 2, 3, 5, 6 }, { 4, 7 } },
{ { 1 }, { 2, 3, 5, 7 }, { 4, 6 } },
{ { 1 }, { 2, 3, 6 }, { 4, 5, 7 } },
{ { 1 }, { 2, 3, 7 }, { 4, 5, 6 } },
{ { 1 }, { 2, 4, 5, 6 }, { 3, 7 } },
{ { 1 }, { 2, 4, 7 }, { 3, 5, 6 } },
{ { 1, 2 }, { 3, 4, 6 }, { 5, 7 } },
{ { 1, 2 }, { 3, 5, 6 }, { 4, 7 } },
{ { 1, 2, 4 }, { 3, 6 }, { 5, 7 } }.
From Andrew Howroyd, Sep 23 2019: (Start)
For n=6, k=4 the partitions are:
{ { 1, 2, 4 }, { 3 }, { 5 }, { 6 } },
{ { 1, 2 }, { 3, 5 }, { 4 }, { 6 } }.
These correspond to the bracelet structures AABACD and AABCBD.
(End)
CROSSREFS
Column k=2 is A327734.
Row sums are A327740.
Sequence in context: A167891 A105087 A238012 * A320647 A028572 A107492
KEYWORD
nonn,tabl
AUTHOR
Bahman Ahmadi, Sep 04 2019
EXTENSIONS
a(56)-a(78) from Andrew Howroyd, Sep 23 2019
STATUS
approved