OFFSET
0,3
COMMENTS
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
Alois P. Heinz, Rows n = 0..40, flattened
Don Knuth, Parades and poly-Bernoulli bijections, Mar 31 2024. See (19.2).
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Acyclic orientation
Wikipedia, Multipartite graph
EXAMPLE
Triangle of triangles T(n,k,j) begins:
1;
;
1;
2, 6;
;
1;
4, 18;
14, 78, 426;
;
1;
8, 54;
46, 330, 2286;
230, 1902, 15402, 122190;
;
...
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:
T:= proc() option remember; local q, l, b; q, l, b:= -1, [args],
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(seq(T(n, k, j), j=0..k), k=0..n), n=0..5);
MATHEMATICA
g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n - j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
T[n_, k_, j_] := T[n, k, j] = Module[{q = -1, l = {n, k, j}, b},
b[n0_, j0_] := b[n0, j0] = If[j0 == 1, Product[q - i, {i, 0, n0 - 1}]*
(q - n0)^n, Sum[b[n0 + m, j0 - 1]*Coefficient[g[l[[j0]]], x, m],
{m, 0, l[[j0]]}]];
Abs[b[0, 3]]];
Table[Table[Table[T[n, k, j], {j, 0, k}], {k, 0, n}], {n, 0, 5}] // Flatten (* Jean-François Alcover, Jun 14 2024, after Alois P. Heinz *)
CROSSREFS
KEYWORD
AUTHOR
Alois P. Heinz, Apr 24 2024
STATUS
approved