login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A267383 Number A(n,k) of acyclic orientations of the Turán graph T(n,k); square array A(n,k), n>=0, k>=1, read by antidiagonals. 12

%I #19 Oct 18 2018 16:24:07

%S 1,1,1,1,1,1,1,1,2,1,1,1,2,4,1,1,1,2,6,14,1,1,1,2,6,18,46,1,1,1,2,6,

%T 24,78,230,1,1,1,2,6,24,96,426,1066,1,1,1,2,6,24,120,504,2286,6902,1,

%U 1,1,2,6,24,120,600,3216,15402,41506,1

%N Number A(n,k) of acyclic orientations of the Turán graph T(n,k); square array A(n,k), n>=0, k>=1, read by antidiagonals.

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

%C Conjecture: In general, column k > 1 is asymptotic to n! / ((k-1) * (1 - log(k/(k-1)))^((k-1)/2) * k^n * (log(k/(k-1)))^(n+1)). - _Vaclav Kotesovec_, Feb 18 2017

%H Alois P. Heinz, <a href="/A267383/b267383.txt">Antidiagonals n = 0..140, flattened</a>

%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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Tur%C3%A1n_graph">Turán graph</a>

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 2, 2, 2, 2, 2, 2, ...

%e 1, 4, 6, 6, 6, 6, 6, ...

%e 1, 14, 18, 24, 24, 24, 24, ...

%e 1, 46, 78, 96, 120, 120, 120, ...

%e 1, 230, 426, 504, 600, 720, 720, ...

%e 1, 1066, 2286, 3216, 3720, 4320, 5040, ...

%p A:= proc(n, k) option remember; local b, l, q; q:=-1;

%p l:= [floor(n/k)$(k-irem(n,k)), ceil(n/k)$irem(n,k)];

%p b:= proc(n, j) option remember; `if`(j=1, (q-n)^l[1]*

%p mul(q-i, i=0..n-1), add(b(n+m, j-1)*

%p Stirling2(l[j], m), m=0..l[j]))

%p end; forget(b);

%p abs(b(0, k))

%p end:

%p seq(seq(A(n, 1+d-n), n=0..d), d=0..14);

%t 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]]]; Table[Table[A[n, 1 + d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* _Jean-François Alcover_, Feb 22 2016, after _Alois P. Heinz_ *)

%Y Columns k=1-10 give: A000012, A266695, A266858, A267384, A267385, A267386, A267387, A267388, A267389, A267390.

%Y Main diagonal gives A000142.

%Y A(2n,n) gives A033815.

%Y A(n,ceiling(n/2)) gives A161132.

%K nonn,tabl

%O 0,9

%A _Alois P. Heinz_, Jan 13 2016

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 00:26 EDT 2024. Contains 371264 sequences. (Running on oeis4.)