|
%I #43 Apr 17 2024 21:00:20
%S 1,1,2,4,14,46,230,1066,6902,41506,329462,2441314,22934774,202229266,
%T 2193664790,22447207906,276054834902,3216941445106,44222780245622,
%U 578333776748674,8787513806478134,127464417117501586,2121181056663291350,33800841048945424546
%N Number of acyclic orientations of the Turán graph T(n,2).
%C The Turán graph T(n,2) is also the complete bipartite graph K_{floor(n/2),ceiling(n/2)}.
%C 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.
%H Alois P. Heinz, <a href="/A266695/b266695.txt">Table of n, a(n) for n = 0..475</a>
%H Beáta Bényi and Peter Hajnal, <a href="https://arxiv.org/abs/1510.05765">Combinatorics of poly-Bernoulli numbers</a>, arXiv:1510.05765 [math.CO], 2015; Studia Scientiarum Mathematicarum Hungarica, Vol. 52, No. 4 (2015), 537-558, DOI:<a href="https://doi.org/10.1556/012.2015.52.4.1325">10.1556/012.2015.52.4.1325</a>.
%H P. J. Cameron, C. A. Glass, and R. U. Schumacher, <a href="https://arxiv.org/abs/1412.3685">Acyclic orientations and poly-Bernoulli numbers</a>, arXiv:1412.3685 [math.CO], 2014-2018.
%H Richard P. Stanley, <a href="http://dx.doi.org/10.1016/0012-365X(73)90108-8">Acyclic Orientations of Graphs</a>, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Tur%C3%A1n_graph">Turán graph</a>
%F a(n) = Sum_{i=0..floor(n/2)} i!^2 * Stirling2(ceiling(n/2)+1,i+1) * Stirling2(floor(n/2)+1,i+1).
%F a(n) = A099594(floor(n/2),ceiling(n/2)).
%F a(n) = Sum_{k=0..n} abs(A266972(n,k)).
%F a(n) ~ n! / (sqrt(1-log(2)) * 2^n * (log(2))^(n+1)). - _Vaclav Kotesovec_, Feb 18 2017
%p a:= n-> (p-> add(Stirling2(n-p+1, i+1)*Stirling2(p+1, i+1)*
%p i!^2, i=0..p))(iquo(n, 2)):
%p seq(a(n), n=0..25);
%t a[n_] := With[{q=Quotient[n, 2]}, Sum[StirlingS2[n-q+1, i+1] StirlingS2[ q+1, i+1] i!^2, {i, 0, q}]];
%t Array[a, 24, 0] (* _Jean-François Alcover_, Nov 06 2018 *)
%Y Column k=2 of A267383.
%Y Cf. A099594, A212084, A212085, A266858, A266972.
%Y Bisections give A048163 (even part), A188634 (odd part).
%K nonn,changed
%O 0,3
%A _Alois P. Heinz_, Jan 02 2016
|
