cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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.

This page as a plain text file.
%I A267383 #26 Apr 24 2024 20:06:32
%S A267383 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 A267383 24,78,230,1,1,1,2,6,24,96,426,1066,1,1,1,2,6,24,120,504,2286,6902,1,
%U A267383 1,1,2,6,24,120,600,3216,15402,41506,1
%N 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.
%C A267383 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 A267383 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 A267383 Alois P. Heinz, <a href="/A267383/b267383.txt">Antidiagonals n = 0..140, flattened</a>
%H A267383 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 A267383 Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%H A267383 Wikipedia, <a href="https://en.wikipedia.org/wiki/Tur%C3%A1n_graph">Turán graph</a>
%e A267383 Square array A(n,k) begins:
%e A267383   1,    1,    1,    1,    1,    1,    1, ...
%e A267383   1,    1,    1,    1,    1,    1,    1, ...
%e A267383   1,    2,    2,    2,    2,    2,    2, ...
%e A267383   1,    4,    6,    6,    6,    6,    6, ...
%e A267383   1,   14,   18,   24,   24,   24,   24, ...
%e A267383   1,   46,   78,   96,  120,  120,  120, ...
%e A267383   1,  230,  426,  504,  600,  720,  720, ...
%e A267383   1, 1066, 2286, 3216, 3720, 4320, 5040, ...
%p A267383 A:= proc(n, k) option remember; local b, l, q; q:=-1;
%p A267383        l:= [floor(n/k)$(k-irem(n,k)), ceil(n/k)$irem(n,k)];
%p A267383        b:= proc(n, j) option remember; `if`(j=1, (q-n)^l[1]*
%p A267383              mul(q-i, i=0..n-1), add(b(n+m, j-1)*
%p A267383              Stirling2(l[j], m), m=0..l[j]))
%p A267383            end; forget(b);
%p A267383        abs(b(0, k))
%p A267383     end:
%p A267383 seq(seq(A(n, 1+d-n), n=0..d), d=0..14);
%t A267383 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 A267383 Columns k=1-10 give: A000012, A266695, A266858, A267384, A267385, A267386, A267387, A267388, A267389, A267390.
%Y A267383 Main diagonal gives A000142.
%Y A267383 A(2n,n) gives A033815.
%Y A267383 A(n,ceiling(n/2)) gives A161132.
%Y A267383 Bisection of column k=2 gives A048163.
%Y A267383 Trisection of column k=3 gives A370961.
%Y A267383 a(n^2,n) gives A372084.
%K A267383 nonn,tabl
%O A267383 0,9
%A A267383 _Alois P. Heinz_, Jan 13 2016