OFFSET
0,9
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.
Conjecture: In general, column k > 1 is asymptotic to n! / ((k-1) * (1 - log(k/(k-1)))^((k-1)/2) * k^n * (log(k/(k-1)))^(n+1)). - Vaclav Kotesovec, Feb 18 2017
LINKS
Alois P. Heinz, Antidiagonals n = 0..140, flattened
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, Turán graph
EXAMPLE
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, ...
1, 2, 2, 2, 2, 2, 2, ...
1, 4, 6, 6, 6, 6, 6, ...
1, 14, 18, 24, 24, 24, 24, ...
1, 46, 78, 96, 120, 120, 120, ...
1, 230, 426, 504, 600, 720, 720, ...
1, 1066, 2286, 3216, 3720, 4320, 5040, ...
MAPLE
A:= proc(n, k) option remember; local b, l, q; q:=-1;
l:= [floor(n/k)$(k-irem(n, k)), ceil(n/k)$irem(n, k)];
b:= proc(n, j) option remember; `if`(j=1, (q-n)^l[1]*
mul(q-i, i=0..n-1), add(b(n+m, j-1)*
Stirling2(l[j], m), m=0..l[j]))
end; forget(b);
abs(b(0, k))
end:
seq(seq(A(n, 1+d-n), n=0..d), d=0..14);
MATHEMATICA
A[n_, k_] := A[n, k] = Module[{ b, l, q}, q = -1; l = Join[Array[Floor[n/k] &, k - Mod[n, k]], Array[ Ceiling[n/k] &, Mod[n, k]]]; b[nn_, j_] := b[nn, j] = If[j == 1, (q - nn)^l[[1]]*Product[q - i, {i, 0, nn - 1}], Sum[b[nn + m, j - 1]*StirlingS2[l[[j]], m], {m, 0, l[[j]]}]]; Abs[b[0, k]]]; Table[Table[A[n, 1 + d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jan 13 2016
STATUS
approved