login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 20 20:56 EST 2019. Contains 329347 sequences. (Running on oeis4.)