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.
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.
FORMULA
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
KEYWORD
nonn,tabl
AUTHOR
Marko Riedel, Feb 14 2020
STATUS
approved