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.

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, 24024, 120, 1, 1, 1, 329462, 90768378, 165392664, 2170680, 720, 1, 1, 1, 22934774, 138779942046, 4154515368024, 457907248920, 287250480, 5040, 1

Offset: 0

Author

Alois P. Heinz, Apr 27 2024

Keywords

• nonn
• tabl

Comments

The Turán graph T(k*n,n) is the complete n-partite graph K_{k,...,k}.

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.

Examples

			Square array A(n,k) begins:
  1,   1,       1,            1,                  1, ...
  1,   1,       1,            1,                  1, ...
  1,   2,      14,          230,               6902, ...
  1,   6,     426,       122190,           90768378, ...
  1,  24,   24024,    165392664,      4154515368024, ...
  1, 120, 2170680, 457907248920, 495810323060597880, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..42, flattened
• Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
• Wikipedia, Acyclic orientation
• Wikipedia, Multipartite graph
• Wikipedia, Turán graph

Crossrefs

Columns k=0-2 give: A000012, A000142, A033815.

Rows n=0+1,2-3 give: A000012, A048163(k+1), A370961.

Main diagonal gives A372084.

Cf. A267383.

Programs

Maple

g:= proc(n) option remember; `if`(n=0, 1, add(
      expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
    end:
A:= proc(n, k) option remember; local q, l, b; q, l, b:= -1, [k$n, 0],
      proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
        (q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
      end; abs(b(0, nops(l)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n - j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
A[n_, k_] := A[n, k] = Module[{q = -1, l, b}, l = Append[Table[k, {n}], 0];
   b[nn_, j_] := b[nn, j] = If[j == 1, Product[q - i, {i, 0, nn - 1}]*
   (q - nn)^l[[1]], Sum[b[nn + m, j - 1]*Coefficient[g[l[[j]]], x, m],
   {m, 0, l[[j]]}]];
   Abs[b[0, Length[l]]]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Jun 09 2024, after Alois P. Heinz *)

Formula

A(n,k) = A267383(k*n,n).