%I #44 Nov 05 2019 06:00:30
%S 1,1,0,1,1,0,1,1,1,0,1,1,2,4,0,1,1,2,8,6,0,1,1,2,9,20,16,0,1,1,2,9,26,
%T 65,28,0,1,1,2,9,27,102,182,64,0,1,1,2,9,27,111,364,560,120,0,1,1,2,9,
%U 27,112,440,1436,1640,256,0
%N The number of non-equivalent distinguishing coloring partitions of the path on n vertices (n>=1) with at most k parts (k>=1). Square array read by descending antidiagonals: the rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of parts.
%C A vertex-coloring of a graph G is called distinguishing if it is only preserved by the identity automorphism of G. This notion is considered in the subject of symmetry breaking of simple (finite or infinite) graphs. A distinguishing coloring partition of a graph G is a partition of the vertices of G such that it induces a distinguishing coloring for G. We say two distinguishing coloring partitions P1 and P2 of G are equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. Given a graph G, we use the notation Psi_k(G) to denote the number of non-equivalent distinguishing coloring partitions of G with at most k parts. This sequence gives A(n,k) = Psi_k(P_n), i.e., the number of non-equivalent distinguishing coloring partitions of the path P_n on n vertices with at most k parts.
%C Note that, for any graph G, Psi_k(G) = Sum_{i<=k} psi_i(G), where psi_i(G) is the number of non-equivalent distinguishing coloring partitions of G with exactly i parts. For instance, here we have T(n,k) = Sum_{i<=k} A309748(n,i).
%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.
%H Mohammad Hadi Shekarriz, <a href="/A309635/a309635.txt">GAP code</a>
%F T(n, k) = Sum_{i=1..k} A309748(n,i).
%e Table begins:
%e ======================================================================
%e n\k| 1 2 3 4 5 6 7 8 9 10
%e ---+------------------------------------------------------------------
%e 1 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ...
%e 2 | 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 ...
%e 3 | 0, 1, 2, 2, 2, 2, 2, 2, 2, 2 ...
%e 4 | 0, 4, 8, 9, 9, 9, 9, 9, 9, 9 ...
%e 5 | 0, 6, 20, 26, 27, 27, 27, 27, 27, 27 ...
%e 6 | 0, 16, 65, 102, 111, 112, 112, 112, 112, 112 ...
%e 7 | 0, 28, 182, 364, 440, 452, 453, 453, 453, 453 ...
%e 8 | 0, 64, 560, 1436, 1978, 2120, 2136, 2137, 2137, 2137 ...
%e 9 | 0, 120, 1640, 5560, 9082, 10428, 10670, 10690, 10691, 10691 ...
%e 10 | 0, 256, 4961, 22136, 43528, 55039, 58019, 58409, 58434, 58435 ...
%e ...
%e For n=4, we can partition the vertices of P_4 into at most 3 parts in 8 ways such that all these partitions induce distinguishing colorings for P_4 and that all the 8 partitions are non-equivalent. The partitions are as follows:
%e { { 1 }, { 2 }, { 3, 4 } }
%e { { 1 }, { 2, 3 }, { 4 } }
%e { { 1 }, { 2, 4 }, { 3 } }
%e { { 1, 4 }, { 2 }, { 3 } }
%e { { 1 }, { 2, 3, 4 } }
%e { { 1, 2 }, { 3, 4 } }
%e { { 1, 2, 4 }, { 3 } }
%e { { 1, 3 }, { 2, 4 } }
%Y Column k=2 is A007179(n > 1).
%Y Cf. A284949, A309748.
%K nonn,tabl
%O 1,13
%A _Mohammad Hadi Shekarriz_, Aug 13 2019