This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 12
 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 (list; table; graph; refs; listen; history; text; internal format)
 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, 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 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. Sequence in context: A287214 A287216 A145515 * A272896 A188919 A026519 Adjacent sequences:  A267380 A267381 A267382 * A267384 A267385 A267386 KEYWORD nonn,tabl AUTHOR Alois P. Heinz, Jan 13 2016 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 25 16:33 EDT 2019. Contains 321471 sequences. (Running on oeis4.)