|
| |
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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)):
|
|
|
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
|
Row sums give 2 * A084851(n-2) for n>1.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
