A332496 - OEIS

%I #49 Feb 17 2020 21:26:03

%S 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 96,21,1,19,108,290,425,351,154,28,1,22,147,476,875,966,637,232,36,1,

%U 25,192,728,1610,2226,1960,1072,333,45,1,28,243,1056,2730,4536,4998,3648,1701,460,55

%N 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 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 E. Palmer and F. Harary, Graphical Enumeration, Academic Press, 1973.

%H Marko Riedel, <a href="/A332496/b332496.txt">Table of n, a(n) for n = 1..1275 (first 50 rows)</a>

%H Marko Riedel et al., Math.StackExchange, <a href="https://math.stackexchange.com/questions/3545391/">Calculate number of possible colorings.</a>

%H 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 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 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 Triangle T(n,k) begins:

%e   0;

%e   1,  1;

%e   1,  4,   3;

%e   1,  7,  12,   6;

%e   1, 10,  27,  28,  10;

%e   1, 13,  48,  76,  55,  15;

%e   1, 16,  75, 160, 175,  96,  21;

%e   1, 19, 108, 290, 425, 351, 154,  28;

%e   1, 22, 147, 476, 875, 966, 637, 232, 36;

%e   ...

%e 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 T:= (n, k)-> `if`(n=1, 0, (k!/2/(n-2)!)*add(abs(Stirling1(n-2, p))

%p               *(Stirling2(p+1, k)+Stirling2(p+2, k)), p=0..n-2)):

%p seq(seq(T(n, k), k=1..n), n=1..12);  # _Alois P. Heinz_, Feb 14 2020

%o (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 for(n=1,11,print(" ");for(k=1,n,print1(T(n,k),", "))) \\ _Hugo Pfoertner_, Feb 14 2020

%Y Cf. A008277, A048994.

%Y Main diagonal gives A000217(n-1).

%Y Row sums give 2 * A084851(n-2) for n>1.

%K nonn,tabl

%O 1,5

%A _Marko Riedel_, Feb 14 2020