cp's OEIS Frontend

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

%I A372326 #29 Jun 09 2024 09:02:22
%S A372326 1,1,1,1,1,1,1,1,2,1,1,1,14,6,1,1,1,230,426,24,1,1,1,6902,122190,
%T A372326 24024,120,1,1,1,329462,90768378,165392664,2170680,720,1,1,1,22934774,
%U A372326 138779942046,4154515368024,457907248920,287250480,5040,1
%N A372326 Number A(n,k) of acyclic orientations of the Turán graph T(k*n,n); square array A(n,k), n>=0, k>=1, read by antidiagonals.
%C A372326 The Turán graph T(k*n,n) is the complete n-partite graph K_{k,...,k}.
%C A372326 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 A372326 Alois P. Heinz, <a href="/A372326/b372326.txt">Antidiagonals n = 0..42, flattened</a>
%H A372326 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 A372326 Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%H A372326 Wikipedia, <a href="https://en.wikipedia.org/wiki/Multipartite_graph">Multipartite graph</a>
%H A372326 Wikipedia, <a href="https://en.wikipedia.org/wiki/Tur%C3%A1n_graph">Turán graph</a>
%F A372326 A(n,k) = A267383(k*n,n).
%e A372326 Square array A(n,k) begins:
%e A372326   1,   1,       1,            1,                  1, ...
%e A372326   1,   1,       1,            1,                  1, ...
%e A372326   1,   2,      14,          230,               6902, ...
%e A372326   1,   6,     426,       122190,           90768378, ...
%e A372326   1,  24,   24024,    165392664,      4154515368024, ...
%e A372326   1, 120, 2170680, 457907248920, 495810323060597880, ...
%p A372326 g:= proc(n) option remember; `if`(n=0, 1, add(
%p A372326       expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
%p A372326     end:
%p A372326 A:= proc(n, k) option remember; local q, l, b; q, l, b:= -1, [k$n, 0],
%p A372326       proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
%p A372326         (q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
%p A372326       end; abs(b(0, nops(l)))
%p A372326     end:
%p A372326 seq(seq(A(n, d-n), n=0..d), d=0..10);
%t A372326 g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n - j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
%t A372326 A[n_, k_] := A[n, k] = Module[{q = -1, l, b}, l = Append[Table[k, {n}], 0];
%t A372326    b[nn_, j_] := b[nn, j] = If[j == 1, Product[q - i, {i, 0, nn - 1}]*
%t A372326    (q - nn)^l[[1]], Sum[b[nn + m, j - 1]*Coefficient[g[l[[j]]], x, m],
%t A372326    {m, 0, l[[j]]}]];
%t A372326    Abs[b[0, Length[l]]]];
%t A372326 Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* _Jean-François Alcover_, Jun 09 2024, after _Alois P. Heinz_ *)
%Y A372326 Columns k=0-2 give: A000012, A000142, A033815.
%Y A372326 Rows n=0+1,2-3 give: A000012, A048163(k+1), A370961.
%Y A372326 Main diagonal gives A372084.
%Y A372326 Cf. A267383.
%K A372326 nonn,tabl
%O A372326 0,9
%A A372326 _Alois P. Heinz_, Apr 27 2024