A372254 Number A(n,k) of acyclic orientations of the complete tripartite graph K_{n,n,k}; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 2, 1, 6, 14, 1, 18, 78, 230, 1, 54, 426, 1902, 6902, 1, 162, 2286, 15402, 76110, 329462, 1, 486, 12090, 122190, 822954, 4553166, 22934774, 1, 1458, 63198, 951546, 8724078, 61796298, 381523758, 2193664790, 1, 4374, 327306, 7290942, 90768378, 823457454, 6241779786, 42700751022, 276054834902

Offset

0,3

Comments

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.

From Vaclav Kotesovec, Feb 06 2026: (Start)

For fixed r, A(r, n) ~ (2*r)! * (2*r+1)^n.

For fixed k, A(n, k) ~ sqrt(Pi) * 2^(k+1) * n^(2*n + (2*k+1)/2) / (sqrt(1 - log(2)) * exp(2*n) * log(2)^(2*n+k+1)). (End)

Links

Alois P. Heinz, Rows n = 0..140, flattened

Don Knuth, Parades and poly-Bernoulli bijections, Mar 31 2024. See (19.2).

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

Example

Square array A(n,k) begins:
       1,       1,        1,         1,           1,            1, ...
       2,       6,       18,        54,         162,          486, ...
      14,      78,      426,      2286,       12090,        63198, ...
     230,    1902,    15402,    122190,      951546,      7290942, ...
    6902,   76110,   822954,   8724078,    90768378,    928340190, ...
  329462, 4553166, 61796298, 823457454, 10779805722, 138779942046, ...

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, [n$2, k],
      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, 3))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..9);

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, l, b}, {q, l} = {-1, {n, n, k}}; b[n0_, j_] := b[n0, j] = If[j == 1, Product[q-i, {i, 0, n0-1}]*(q-n0)^l[[1]], Sum[b[n0 + m, j-1]*Coefficient[g[l[[j]]], x, m], {m, 0, l[[j]]}]]; Abs[b[0, 3]]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 9}] // Flatten (* Jean-François Alcover, Apr 25 2024, after Alois P. Heinz *)

Crossrefs

Rows n=0-4 give: A000012, A008776, A370960, A393219, A393220.

Columns k=0-3 give: A048163(n+1), A393221, A393222, A393223.

Main diagonal gives A370961.

Cf. A212220, A267383, A372261.

Sequence in context: A123968 A282329 A343806 * A210654 A068797 A254639

Adjacent sequences: A372251 A372252 A372253 * A372255 A372256 A372257

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 24 2024

Status

approved