A266695 Number of acyclic orientations of the Turán graph T(n,2).

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

Author

Alois P. Heinz, Jan 02 2016

Keywords

• nonn

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

• Alois P. Heinz, Table of n, a(n) for n = 0..475
• 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

Crossrefs

Column k=2 of A267383.

Cf. A099594, A212084, A212085, A266858, A266972.

Bisections give A048163 (even part), A188634 (odd part).

Programs

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

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