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.

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, 96, 21, 1, 19, 108, 290, 425, 351, 154, 28, 1, 22, 147, 476, 875, 966, 637, 232, 36, 1, 25, 192, 728, 1610, 2226, 1960, 1072, 333, 45, 1, 28, 243, 1056, 2730, 4536, 4998, 3648, 1701, 460, 55

Offset: 1

Author

Marko Riedel, Feb 14 2020

Keywords

• nonn
• tabl

Comments

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.

Examples

			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.
Triangle T(n,k) begins:
  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,  96,  21;
  1, 19, 108, 290, 425, 351, 154,  28;
  1, 22, 147, 476, 875, 966, 637, 232, 36;
  ...
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
		

References

• E. Palmer and F. Harary, Graphical Enumeration, Academic Press, 1973.

Links

• Marko Riedel, Table of n, a(n) for n = 1..1275 (first 50 rows)
• Marko Riedel et al., Math.StackExchange, Calculate number of possible colorings.
• Marko Riedel, Maple code for colorings using at most k colors and exactly k colors, including cycle index.

Crossrefs

Cf. A008277, A048994.

Main diagonal gives A000217(n-1).

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

Programs

Maple

T:= (n, k)-> `if`(n=1, 0, (k!/2/(n-2)!)*add(abs(Stirling1(n-2, p))
              *(Stirling2(p+1, k)+Stirling2(p+2, k)), p=0..n-2)):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Feb 14 2020

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))))};
for(n=1,11,print(" ");for(k=1,n,print1(T(n,k),", "))) \\ Hugo Pfoertner, Feb 14 2020

Formula

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).