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