login
A266695
Number of acyclic orientations of the Turán graph T(n,2).
9
1, 1, 2, 4, 14, 46, 230, 1066, 6902, 41506, 329462, 2441314, 22934774, 202229266, 2193664790, 22447207906, 276054834902, 3216941445106, 44222780245622, 578333776748674, 8787513806478134, 127464417117501586, 2121181056663291350, 33800841048945424546
OFFSET
0,3
COMMENTS
The Turán graph T(n,2) is also the complete bipartite graph K_{floor(n/2),ceiling(n/2)}.
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
Beáta Bényi and Peter Hajnal, Combinatorics of poly-Bernoulli numbers, arXiv:1510.05765 [math.CO], 2015; Studia Scientiarum Mathematicarum Hungarica, Vol. 52, No. 4 (2015), 537-558, DOI:10.1556/012.2015.52.4.1325.
P. J. Cameron, C. A. Glass, and 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.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Wikipedia, Turán graph
FORMULA
a(n) = Sum_{i=0..floor(n/2)} i!^2 * Stirling2(ceiling(n/2)+1,i+1) * Stirling2(floor(n/2)+1,i+1).
a(n) = A099594(floor(n/2),ceiling(n/2)).
a(n) = Sum_{k=0..n} abs(A266972(n,k)).
a(n) ~ n! / (sqrt(1-log(2)) * 2^n * (log(2))^(n+1)). - Vaclav Kotesovec, Feb 18 2017
MAPLE
a:= n-> (p-> add(Stirling2(n-p+1, i+1)*Stirling2(p+1, i+1)*
i!^2, i=0..p))(iquo(n, 2)):
seq(a(n), n=0..25);
MATHEMATICA
a[n_] := With[{q=Quotient[n, 2]}, Sum[StirlingS2[n-q+1, i+1] StirlingS2[ q+1, i+1] i!^2, {i, 0, q}]];
Array[a, 24, 0] (* Jean-François Alcover, Nov 06 2018 *)
CROSSREFS
Column k=2 of A267383.
Bisections give A048163 (even part), A188634 (odd part).
Sequence in context: A263740 A005437 A214267 * A327034 A263741 A263742
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jan 02 2016
STATUS
approved