|
%I #26 Apr 24 2024 20:06:32
%S 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,
%T 24,78,230,1,1,1,2,6,24,96,426,1066,1,1,1,2,6,24,120,504,2286,6902,1,
%U 1,1,2,6,24,120,600,3216,15402,41506,1
%N 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.
%C 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.
%C 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
%H Alois P. Heinz, <a href="/A267383/b267383.txt">Antidiagonals n = 0..140, flattened</a>
%H Richard P. Stanley, <a href="http://dx.doi.org/10.1016/0012-365X(73)90108-8">Acyclic Orientations of Graphs</a>, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Tur%C3%A1n_graph">Turán graph</a>
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 2, 2, 2, 2, 2, 2, ...
%e 1, 4, 6, 6, 6, 6, 6, ...
%e 1, 14, 18, 24, 24, 24, 24, ...
%e 1, 46, 78, 96, 120, 120, 120, ...
%e 1, 230, 426, 504, 600, 720, 720, ...
%e 1, 1066, 2286, 3216, 3720, 4320, 5040, ...
%p A:= proc(n, k) option remember; local b, l, q; q:=-1;
%p l:= [floor(n/k)$(k-irem(n,k)), ceil(n/k)$irem(n,k)];
%p b:= proc(n, j) option remember; `if`(j=1, (q-n)^l[1]*
%p mul(q-i, i=0..n-1), add(b(n+m, j-1)*
%p Stirling2(l[j], m), m=0..l[j]))
%p end; forget(b);
%p abs(b(0, k))
%p end:
%p seq(seq(A(n, 1+d-n), n=0..d), d=0..14);
%t 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_ *)
%Y Columns k=1-10 give: A000012, A266695, A266858, A267384, A267385, A267386, A267387, A267388, A267389, A267390.
%Y Main diagonal gives A000142.
%Y A(2n,n) gives A033815.
%Y A(n,ceiling(n/2)) gives A161132.
%Y Bisection of column k=2 gives A048163.
%Y Trisection of column k=3 gives A370961.
%Y a(n^2,n) gives A372084.
%K nonn,tabl
%O 0,9
%A _Alois P. Heinz_, Jan 13 2016
|
