cp's OEIS Frontend

A309748 The number of non-equivalent distinguishing coloring partitions of the path on n vertices (n>=1) with exactly k parts (k>=1). Regular triangle read by rows: the rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of parts.

%I A309748 #42 Nov 05 2019 05:59:52
%S A309748 1,0,1,0,1,1,0,4,4,1,0,6,14,6,1,0,16,49,37,9,1,0,28,154,182,76,12,1,0,
%T A309748 64,496,876,542,142,16,1,0,120,1520,3920,3522,1346,242,20,1,0,256,
%U A309748 4705,17175,21392,11511,2980,390,25,1,0,496,14266,73030,123665,89973,32141,5990,595,30,1
%N A309748 The number of non-equivalent distinguishing coloring partitions of the path on n vertices (n>=1) with exactly k parts (k>=1). Regular triangle read by rows: 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 A309748 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 exactly k parts. For n>=1, this sequence gives T(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 exactly k parts.
%C A309748 Also, for n > 1 the number of reversible string structures of length n using exactly k different symbols that are not equivalent to their reversal (compare A284949). - _Andrew Howroyd_, Aug 15 2019
%H A309748 Andrew Howroyd, <a href="/A309748/b309748.txt">Table of n, a(n) for n = 1..1275</a>
%H A309748 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 A309748 Mohammad Hadi Shekarriz, <a href="/A309748/a309748.txt">GAP Program</a>
%F A309748 T(n,k) = A309635(n,k) - A309635(n,k-1) for k > 1.
%F A309748 T(n,k) = A284949(n,k) - Stirling2(ceiling(n/2), k) for n > 1. - _Andrew Howroyd_, Aug 15 2019
%e A309748 The triangle begins:
%e A309748   1;
%e A309748   0,   1;
%e A309748   0,   1,    1;
%e A309748   0,   4,    4,     1;
%e A309748   0,   6,   14,     6,     1;
%e A309748   0,  16,   49,    37,     9,     1;
%e A309748   0,  28,  154,   182,    76,    12,    1;
%e A309748   0,  64,  496,   876,   542,   142,   16,   1;
%e A309748   0, 120, 1520,  3920,  3522,  1346,  242,  20,  1;
%e A309748   0, 256, 4705, 17175, 21392, 11511, 2980, 390, 25, 1;
%e A309748   ...
%e A309748 ----
%e A309748 For n=4, we can partition the vertices of P_4 into exactly 3 parts in 4 ways such that all these partitions induce distinguishing colorings for P_4 and that all the 4 partitions are non-equivalent. The partitions are as follows:
%e A309748     { { 1 }, { 2 }, { 3, 4 } }
%e A309748     { { 1 }, { 2, 3 }, { 4 } }
%e A309748     { { 1 }, { 2, 4 }, { 3 } }
%e A309748     { { 1, 4 }, { 2 }, { 3 } }
%o A309748 (PARI) \\ Ach is A304972 as square matrix.
%o A309748 Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
%o A309748 T(n)={(matrix(n, n, i, k, stirling(i, k, 2) - 2*stirling((i+1)\2, k, 2)) + Ach(n))/2}
%o A309748 { my(A=T(10)); A[1,1]=1; for(n=1, #A, print(A[n, 1..n])) } \\ _Andrew Howroyd_, Sep 18 2019
%Y A309748 Columns k=2..4 are A007179, A327610, A327611.
%Y A309748 Row sums are A327612(n > 1).
%Y A309748 Cf. A284949, A304972, A309635, A309784.
%K A309748 nonn,tabl
%O A309748 1,8
%A A309748 _Mohammad Hadi Shekarriz_, Aug 15 2019
%E A309748 Terms a(56) and beyond from _Andrew Howroyd_, Sep 18 2019