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,9

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.

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

Formula

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

Example

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

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 *)

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.

Sequence in context: A342458 A358722 A256688 * A029582 A067095 A070888

Adjacent sequences: A372323 A372324 A372325 * A372327 A372328 A372329

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 27 2024

Status

approved