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

Author

Alois P. Heinz, Apr 24 2024

Keywords

• nonn
• tabl

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.

Examples

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

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

Crossrefs

Rows n=0-2 give: A000012, A008776, A370960.

Column k=0 gives A048163(n+1).

Main diagonal gives A370961.

Cf. A212220, A267383, A372261.

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