login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A266858 Number of acyclic orientations of the Turán graph T(n,3). 3
1, 1, 2, 6, 18, 78, 426, 2286, 15402, 122190, 951546, 8724078, 90768378, 928340190, 10779805722, 138779942046, 1759271695338, 24739709631678, 379578822373866, 5743346972756526, 94864142045862282, 1689637343582548590, 29717468115957434586, 563879701735681033998 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

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.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..465

P. J. Cameron, C. A. Glass, R. U. Schumacher, Acyclic orientations and poly-Bernoulli numbers, arXiv:1412.3685 [math.CO], 2014-2018.

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

FORMULA

a(n) ~ n! / (2*(1 - log(3/2)) * 3^n * (log(3/2))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

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]]];

a[n_] := A[n, 3];

Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Aug 20 2018, after Alois P. Heinz *)

CROSSREFS

Column k=3 of A267383.

Cf. A182553, A212220, A266695.

Sequence in context: A079391 A162058 A113844 * A141580 A007869 A263915

Adjacent sequences:  A266855 A266856 A266857 * A266859 A266860 A266861

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Jan 04 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 January 20 21:49 EST 2021. Contains 340332 sequences. (Running on oeis4.)