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.

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

Author

Alois P. Heinz, Jan 13 2016

Keywords

• nonn
• tabl

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

Examples

			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, ...
		

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

Crossrefs

Columns k=1-10 give: A000012, A266695, A266858, A267384, A267385, A267386, A267387, A267388, A267389, A267390.

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.

Programs

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 *)