|
|
A212084
|
|
Triangle T(n,k), n>=1, 0<=k<=2n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete bipartite graph K_(n,n), highest powers first.
|
|
6
|
|
|
1, -1, 0, 1, -4, 6, -3, 0, 1, -9, 36, -75, 78, -31, 0, 1, -16, 120, -524, 1400, -2236, 1930, -675, 0, 1, -25, 300, -2200, 10650, -34730, 75170, -102545, 78610, -25231, 0, 1, -36, 630, -6915, 52080, -279142, 1074822, -2942445, 5552680, -6796926, 4787174
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
The complete bipartite graph K_(n,n) has 2n vertices and n^2 = A000290(n) edges. The chromatic polynomial of K_(n,n) has 2n+1 = A005408(n) coefficients.
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = [q^(2n-k)] Sum_{j=1..n} (q-j)^n * S2(n,j) * Product_{i=0..j-1} (q-i).
|
|
EXAMPLE
|
3 example graphs: +-----------+
. o o o o o o |
. | |\ /| |\ /|\ /|\ /
. | | X | | X | X | X
. | |/ \| |/ \|/ \|/ \
. o o o o o o |
. +-----------+
Graph: K_(1,1) K_(2,2) K_(3,3)
Vertices: 2 4 6
Edges: 1 4 9
The complete bipartite graph K_(2,2) is the cycle graph C_4 with chromatic polynomial q^4 -4*q^3 +6*q^2 -3*q => row 2 = [1, -4, 6, -3, 0].
Triangle T(n,k) begins:
1, -1, 0;
1, -4, 6, -3, 0;
1, -9, 36, -75, 78, -31, 0;
1, -16, 120, -524, 1400, -2236, 1930, -675, ...
1, -25, 300, -2200, 10650, -34730, 75170, -102545, ...
1, -36, 630, -6915, 52080, -279142, 1074822, -2942445, ...
|
|
MAPLE
|
P:= n-> add(Stirling2(n, k) *mul(q-i, i=0..k-1) *(q-k)^n, k=1..n):
T:= n-> seq(coeff(P(n), q, 2*n-k), k=0..2*n):
seq(T(n), n=1..8);
|
|
CROSSREFS
|
Row sums and last elements of rows give: A000004, row lengths give: A005408.
Sums of absolute values of row elements give: A048163(n+1).
|
|
KEYWORD
|
sign,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|