login
A267383
Number A(n,k) of acyclic orientations of the Turán graph T(n,k); square array A(n,k), n>=0, k>=1, read by antidiagonals.
21
1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 4, 1, 1, 1, 2, 6, 14, 1, 1, 1, 2, 6, 18, 46, 1, 1, 1, 2, 6, 24, 78, 230, 1, 1, 1, 2, 6, 24, 96, 426, 1066, 1, 1, 1, 2, 6, 24, 120, 504, 2286, 6902, 1, 1, 1, 2, 6, 24, 120, 600, 3216, 15402, 41506, 1
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
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
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
Main diagonal gives A000142.
A(2n,n) gives A033815.
A(n,ceiling(n/2)) gives A161132.
Bisection of column k=2 gives A048163.
Trisection of column k=3 gives A370961.
a(n^2,n) gives A372084.
Sequence in context: A287214 A287216 A145515 * A332648 A272896 A188919
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jan 13 2016
STATUS
approved