|
%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
|
