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!)
A266695 Number of acyclic orientations of the Turán graph T(n,2). 7
1, 1, 2, 4, 14, 46, 230, 1066, 6902, 41506, 329462, 2441314, 22934774, 202229266, 2193664790, 22447207906, 276054834902, 3216941445106, 44222780245622, 578333776748674, 8787513806478134, 127464417117501586, 2121181056663291350, 33800841048945424546 (list; graph; refs; listen; history; text; internal format)
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

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

Beáta Bényi, Peter Hajnal, Combinatorics of poly-Bernoulli numbers, arXiv:1510.05765 [math.CO], 2015

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.

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.

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

Sequence in context: A263740 A005437 A214267 * A327034 A263741 A263742

Adjacent sequences:  A266692 A266693 A266694 * A266696 A266697 A266698

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Jan 02 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 August 10 07:37 EDT 2020. Contains 336368 sequences. (Running on oeis4.)