cp's OEIS Frontend

A332496 Triangular array T(n,k): the number of not necessarily proper colorings of the complete graph on n unlabeled vertices minus an edge using exactly k colors.

%I A332496 #49 Feb 17 2020 21:26:03
%S A332496 0,1,1,1,4,3,1,7,12,6,1,10,27,28,10,1,13,48,76,55,15,1,16,75,160,175,
%T A332496 96,21,1,19,108,290,425,351,154,28,1,22,147,476,875,966,637,232,36,1,
%U A332496 25,192,728,1610,2226,1960,1072,333,45,1,28,243,1056,2730,4536,4998,3648,1701,460,55
%N A332496 Triangular array T(n,k): the number of not necessarily proper colorings of the complete graph on n unlabeled vertices minus an edge using exactly k colors.
%C A332496 It is not possible to remove an edge from an ordinary graph on one node and there is no remaining graph to color, hence we determine the first term for n=1 and k=1 to be zero. The automorphism group of the graph obtained from the complete graph by removing an edge is the so-called product group of two symmetric groups S_2 S_{n-2} in the sense of Harary and Palmer, section 2.2.
%D A332496 E. Palmer and F. Harary, Graphical Enumeration, Academic Press, 1973.
%H A332496 Marko Riedel, <a href="/A332496/b332496.txt">Table of n, a(n) for n = 1..1275 (first 50 rows)</a>
%H A332496 Marko Riedel et al., Math.StackExchange, <a href="https://math.stackexchange.com/questions/3545391/">Calculate number of possible colorings.</a>
%H A332496 Marko Riedel, <a href="/A332496/a332496.maple.txt">Maple code for colorings using at most k colors and exactly k colors, including cycle index.</a>
%F A332496 T(n,k) = (k!/2/(n-2)!) Sum_{p=0..n-2} |s(n-2,p)| (S(p+1, k)+S(p+2, k)). Here s(n,k) is the signed Stirling number of the first kind (A048994) and S(n,k) the Stirling number of the second kind (A008277).
%e A332496 T(n,n) = C(n,2) because we need to select the two colors that color the vertices of the removed edge from the n available colors. The remaining vertices are not distinguishable.
%e A332496 Triangle T(n,k) begins:
%e A332496   0;
%e A332496   1,  1;
%e A332496   1,  4,   3;
%e A332496   1,  7,  12,   6;
%e A332496   1, 10,  27,  28,  10;
%e A332496   1, 13,  48,  76,  55,  15;
%e A332496   1, 16,  75, 160, 175,  96,  21;
%e A332496   1, 19, 108, 290, 425, 351, 154,  28;
%e A332496   1, 22, 147, 476, 875, 966, 637, 232, 36;
%e A332496   ...
%e A332496 T(4,2) = 7 because when n = 4 there are two unordered pairs of vertices, each of which can be colored in 3 ways using a maximum of 2 colors giving 9 colorings. From this, the two coloring using only one of the two colors needs to be subtracted, so T(4,2) = 9 - 2 = 7. - _Andrew Howroyd_, Feb 15 2020
%p A332496 T:= (n, k)-> `if`(n=1, 0, (k!/2/(n-2)!)*add(abs(Stirling1(n-2, p))
%p A332496               *(Stirling2(p+1, k)+Stirling2(p+2, k)), p=0..n-2)):
%p A332496 seq(seq(T(n, k), k=1..n), n=1..12);  # _Alois P. Heinz_, Feb 14 2020
%o A332496 (PARI) T(n,k) = {if(n<2,0,(k!/2/(n-2)!)*sum(p=0,n-2,abs(stirling(n-2,p,1))* (stirling(p+1, k,2)+stirling(p+2, k,2))))};
%o A332496 for(n=1,11,print(" ");for(k=1,n,print1(T(n,k),", "))) \\ _Hugo Pfoertner_, Feb 14 2020
%Y A332496 Cf. A008277, A048994.
%Y A332496 Main diagonal gives A000217(n-1).
%Y A332496 Row sums give 2 * A084851(n-2) for n>1.
%K A332496 nonn,tabl
%O A332496 1,5
%A A332496 _Marko Riedel_, Feb 14 2020