|
|
A372326
|
|
Number A(n,k) of acyclic orientations of the Turán graph T(k*n,n); square array A(n,k), n>=0, k>=1, read by antidiagonals.
|
|
8
|
|
|
1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 14, 6, 1, 1, 1, 230, 426, 24, 1, 1, 1, 6902, 122190, 24024, 120, 1, 1, 1, 329462, 90768378, 165392664, 2170680, 720, 1, 1, 1, 22934774, 138779942046, 4154515368024, 457907248920, 287250480, 5040, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
COMMENTS
|
The Turán graph T(k*n,n) is the complete n-partite graph K_{k,...,k}.
An acyclic orientation is an assignment of a direction to each edge such that no cycle in the graph is consistently oriented. Stanley showed that the number of acyclic orientations of a graph G is equal to the absolute value of the chromatic polynomial X_G(q) evaluated at q=-1.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Square array A(n,k) begins:
1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, ...
1, 2, 14, 230, 6902, ...
1, 6, 426, 122190, 90768378, ...
1, 24, 24024, 165392664, 4154515368024, ...
1, 120, 2170680, 457907248920, 495810323060597880, ...
|
|
MAPLE
|
g:= proc(n) option remember; `if`(n=0, 1, add(
expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
end:
A:= proc(n, k) option remember; local q, l, b; q, l, b:= -1, [k$n, 0],
proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
(q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
end; abs(b(0, nops(l)))
end:
seq(seq(A(n, d-n), n=0..d), d=0..10);
|
|
MATHEMATICA
|
g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n - j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
A[n_, k_] := A[n, k] = Module[{q = -1, l, b}, l = Append[Table[k, {n}], 0];
b[nn_, j_] := b[nn, j] = If[j == 1, Product[q - i, {i, 0, nn - 1}]*
(q - nn)^l[[1]], Sum[b[nn + m, j - 1]*Coefficient[g[l[[j]]], x, m],
{m, 0, l[[j]]}]];
Abs[b[0, Length[l]]]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|