Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #30 Nov 05 2019 06:00:36
%S 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,
%T 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,
%U 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
%N 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.
%C The cycle graph is defined for n >= 3; extended to n=1,2 using the closed form.
%C 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.
%H Bahman Ahmadi, <a href="/A324803/a324803.txt">GAP Program</a>
%H 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 T(n,k) = Sum_{i<=k} A324802(n,i).
%e Table begins:
%e =================================================================
%e n/k | 1 2 3 4 5 6 7 8 9 10
%e ------+----------------------------------------------------------
%e 1 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
%e 2 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
%e 3 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
%e 4 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
%e 5 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
%e 6 | 0, 0, 4, 6, 6, 6, 6, 6, 6, 6, ...
%e 7 | 0, 1, 13, 30, 34, 34, 34, 34, 34, 34, ...
%e 8 | 0, 2, 45, 127, 176, 185, 185, 185, 185, 185, ...
%e 9 | 0, 7, 144, 532, 871, 996, 1011, 1011, 1011, 1011, ...
%e 10 | 0, 12, 416, 1988, 3982, 5026, 5280, 5304, 5304, 5304, ...
%e ...
%e 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:
%e { { 1 }, { 2, 3 }, { 4, 5, 6, 7 } },
%e { { 1 }, { 2, 3, 4, 6 }, { 5, 7 } },
%e { { 1 }, { 2, 3, 4, 7 }, { 5, 6 } },
%e { { 1 }, { 2, 3, 5, 6 }, { 4, 7 } },
%e { { 1 }, { 2, 3, 5, 7 }, { 4, 6 } },
%e { { 1 }, { 2, 3, 6 }, { 4, 5, 7 } },
%e { { 1 }, { 2, 3, 7 }, { 4, 5, 6 } },
%e { { 1 }, { 2, 4, 5, 6 }, { 3, 7 } },
%e { { 1 }, { 2, 4, 7 }, { 3, 5, 6 } },
%e { { 1, 2 }, { 3, 4, 6 }, { 5, 7 } },
%e { { 1, 2 }, { 3, 5, 6 }, { 4, 7 } },
%e { { 1, 2, 4 }, { 3, 6 }, { 5, 7 } },
%e { { 1, 2, 3, 5 }, { 4, 6, 7 } }.
%Y Column k=2 is A327734.
%Y Cf. A309784, A309785, A320748, A152176, A320647, A324802.
%K nonn,tabl
%O 1,34
%A _Bahman Ahmadi_, Sep 04 2019