A324803 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,34

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.

LINKS

Table of n, a(n) for n=1..101.

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) = Sum_{i<=k} A324802(n,i).

EXAMPLE

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 } },