cp's OEIS Frontend

A293500 Number of orientable strings of length n using a maximum of k colors, array read by descending antidiagonals, T(n,k) for n >= 1 and k >= 1.

%I A293500 #49 Nov 05 2019 05:59:33
%S A293500 0,0,0,0,1,0,0,3,2,0,0,6,9,6,0,0,10,24,36,12,0,0,15,50,120,108,28,0,0,
%T A293500 21,90,300,480,351,56,0,0,28,147,630,1500,2016,1053,120,0,0,36,224,
%U A293500 1176,3780,7750,8064,3240,240,0,0,45,324,2016,8232,23220,38750,32640,9720,496,0
%N A293500 Number of orientable strings of length n using a maximum of k colors, array read by descending antidiagonals, T(n,k) for n >= 1 and k >= 1.
%C A293500 Reversing the string does not leave it unchanged. Only one string from each pair is counted.
%C A293500 Equivalently, the number of nonequivalent strings up to reversal that are not palindromes.
%C A293500 Except for the first term, column k is the "BHK" (reversible, identity, unlabeled) transform of k,0,0,0,... [Corrected by _Petros Hadjicostas_, Jul 01 2018]
%C A293500 From _Petros Hadjicostas_, Jul 01 2018: (Start)
%C A293500 Consider the input sequence (c_k(n): n >= 1) with g.f. C_k(x) = Sum_{n>=1} c_k(n)*x^n. Let a_k(n) = BHK(c_k(n): n >= 1) be the output sequence under Bower's BHK transform. It can be proved that the g.f. of BHK(c_k(n): n >= 1) is A_k(x) = (C_k(x)^2 - C_k(x^2))/(2*(1-C_k(x))*(1-C_k(x^2))) + C_k(x). (See the comments for sequences A032096, A032097, and A032098.)
%C A293500 For column k of this two-dimensional array, the input sequence is defined by c_k(1) = k and c_k(n) = 0 for n >= 1. Thus, C_k(x) = k*x, and hence the g.f. of column k (with the term C_k(x) = k*x excluded) is (C_k(x)^2 - C_k(x^2))/(2*(1-C_k(x))*(1-C_k(x^2))) = (1/2)*(k - 1)*k*x^2/((k*x^2 - 1)*(k*x - 1)), from which we can easily prove Howroyd's formula.
%C A293500 (End)
%C A293500 Comment from _Bahman Ahmadi_, Aug 05 2019: (Start)
%C A293500 We give an alternative definition for the square array A(n,k) = T(n,k) with n >= 2 and k >= 0. A(n,k) is the number of inequivalent "distinguishing colorings" of the path on n vertices using at most k colors.  The rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of permissible colors.
%C A293500 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 context of "symmetry breaking" of simple (finite or infinite) graphs. Two vertex-colorings of a graph are called "equivalent" if there is an automorphism of the graph which preserves the colors of the vertices.  Given a graph G, we use the notation Phi_k(G) to denote the number of inequivalent distinguishing colorings of G with at most k colors. This sequence gives A(n,k) = Phi_k(P_n), i.e., the number of inequivalent distinguishing colorings of the path P_n on n vertices with at most k colors.
%C A293500 For n=3, we can color the vertices of P_3 with at most 2 colors in 3 ways such that all the colorings distinguish the graph (i.e., no non-identity automorphism of the path P_3 preserves the coloring) and that all the three colorings are inequivalent.
%C A293500 We have Phi_k(P_n) = binomial(k,2)*k^(n-2) + k*Phi_k(P_(n-2)) for n >= 4; Phi_k(P_2) = binomial(k,2); Phi_k(P_3) = k*binomial(k,2).
%C A293500 (End)
%H A293500 Andrew Howroyd, <a href="/A293500/b293500.txt">Table of n, a(n) for n = 1..1275</a>
%H A293500 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 A293500 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>.
%F A293500 T(n,k) = (k^n - k^(ceiling(n/2)))/2.
%F A293500 G.f. for column k: (1/2)*(k - 1)*k*x^2/((k*x^2 - 1)*(k*x - 1)). - _Petros Hadjicostas_, Jul 07 2018
%F A293500 From _Robert A. Russell_, Nov 16 2018: (Start)
%F A293500 T(n,k) = (A003992(k,n) - A321391(n,k)) / 2.
%F A293500 T(n,k) = = A003992(k,n) - A277504(n,k) = A277504(n,k) - A321391(n,k).
%F A293500 G.f. for row n: (Sum_{j=0..n} S2(n,j)*j!*x^j/(1-x)^(j+1) - Sum_{j=0..ceiling(n/2)} S2(ceiling(n/2),j)*j!*x^j/(1-x)^(j+1)) / 2, where S2 is the Stirling subset number A008277.
%F A293500 G.f. for row n>1: x * Sum_{k=1..n-1} A145883(n,k) * x^k / (1-x)^(n+1).
%F A293500 E.g.f. for row n: (Sum_{k=0..n} S2(n,k)*x^k - Sum_{k=0..ceiling(n/2)} S2(ceiling(n/2),k)*x^k) * exp(x) / 2, where S2 is the Stirling subset number A008277.
%F A293500 T(0,k) = T(1,k) = 0; T(2,k) = binomial(k,2); for n>2, T(n,k) = k*(T(n-3,k)+T(n-2,k)-k*T(n-1,k)).
%F A293500 For k>n, T(n,k) = Sum_{j=1..n+1} -binomial(j-n-2,j) * T(n,k-j). (End)
%e A293500 Array begins:
%e A293500 ======================================================
%e A293500 n\k| 1   2    3     4      5      6       7       8
%e A293500 ---|--------------------------------------------------
%e A293500 1  | 0   0    0     0      0      0       0       0...
%e A293500 2  | 0   1    3     6     10     15      21      28...
%e A293500 3  | 0   2    9    24     50     90     147     224...
%e A293500 4  | 0   6   36   120    300    630    1176    2016...
%e A293500 5  | 0  12  108   480   1500   3780    8232   16128...
%e A293500 6  | 0  28  351  2016   7750  23220   58653  130816...
%e A293500 7  | 0  56 1053  8064  38750 139320  410571 1046528...
%e A293500 8  | 0 120 3240 32640 195000 839160 2881200 8386560...
%e A293500 ...
%e A293500 For T(4,2)=6, the chiral pairs are AAAB-BAAA, AABA-ABAA, AABB-BBAA, ABAB-BABA, ABBB-BBBA, and BABB-BBAB.
%t A293500 Table[Function[n, (k^n - k^(Ceiling[n/2]))/2][m - k + 1], {m, 11}, {k, m, 1, -1}] // Flatten (* _Michael De Vlieger_, Oct 11 2017 *)
%o A293500 (PARI) T(n,k) = (k^n - k^(ceil(n/2)))/2;
%Y A293500 Columns 2-5 for n > 1 are A032085, A032086, A032087, A032088.
%Y A293500 Column 6 is A320524.
%Y A293500 Rows 2-6 are A161680, A006002(n-1), A083374, A321672, A085744.
%Y A293500 Cf. A277504, A293496.
%Y A293500 Cf. A003992 (oriented), A277504 (unoriented), A321391 (achiral).
%K A293500 nonn,tabl,easy
%O A293500 1,8
%A A293500 _Andrew Howroyd_, Oct 10 2017