A324803 T(n,k) is the number of non-equivalent distinguishing partitions of the cycle on n vertices with at most k part. Square array read by descending antidiagonals, n >= 1, k >= 1.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 1, 0, 0, 0, 0, 0, 0, 6, 13, 2, 0, 0, 0, 0, 0, 0, 6, 30, 45, 7, 0, 0, 0, 0, 0, 0, 6, 34, 127, 144, 12, 0, 0, 0, 0, 0, 0, 6, 34, 176, 532, 416, 31, 0, 0, 0, 0, 0, 0, 6, 34, 185, 871, 1988, 1221, 57, 0, 0, 0, 0, 0, 0, 6, 34, 185, 996, 3982

Offset: 1

Author

Bahman Ahmadi, Sep 04 2019

Keywords

• nonn
• tabl

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 at most k parts.

Examples

			Table begins:
=================================================================
  n/k | 1   2    3     4     5     6     7     8     9    10
------+----------------------------------------------------------
    1 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0, ...
    2 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0, ...
    3 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0, ...
    4 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0, ...
    5 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0, ...
    6 | 0,  0,   4,    6,    6,    6,    6,    6,    6,    6, ...
    7 | 0,  1,  13,   30,   34,   34,   34,   34,   34,   34, ...
    8 | 0,  2,  45,  127,  176,  185,  185,  185,  185,  185, ...
    9 | 0,  7, 144,  532,  871,  996, 1011, 1011, 1011, 1011, ...
   10 | 0, 12, 416, 1988, 3982, 5026, 5280, 5304, 5304, 5304, ...
  ...
For n=7, we can partition the vertices of the cycle C_7 with at most 3 parts, in 13 ways, such that all these partitions are distinguishing for C_7 and that all the 13 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 } },
    { { 1, 2, 3, 5 }, { 4, 6, 7 } }.
		

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.

Crossrefs

Column k=2 is A327734.

Cf. A309784, A309785, A320748, A152176, A320647, A324802.

Formula

T(n,k) = Sum_{i<=k} A324802(n,i).