login
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.
1
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,5
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.
REFERENCES
E. Palmer and F. Harary, Graphical Enumeration, Academic Press, 1973.
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).
EXAMPLE
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
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
PROG
(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
CROSSREFS
Main diagonal gives A000217(n-1).
Row sums give 2 * A084851(n-2) for n>1.
Sequence in context: A127673 A016698 A200115 * A038763 A200384 A128007
KEYWORD
nonn,tabl
AUTHOR
Marko Riedel, Feb 14 2020
STATUS
approved