A372396 Triangle T(n,k) in which row n lists in increasing order the number of acyclic orientations of complete multipartite graphs K_lambda, where lambda is a partition of n; triangle T(n,k), n>=0, k = 1..A000041(n), read by rows.

1, 1, 1, 2, 1, 4, 6, 1, 8, 14, 18, 24, 1, 16, 46, 54, 78, 96, 120, 1, 32, 146, 162, 230, 330, 384, 426, 504, 600, 720, 1, 64, 454, 486, 1066, 1374, 1536, 1902, 2286, 2616, 3000, 3216, 3720, 4320, 5040, 1, 128, 1394, 1458, 4718, 5658, 6144, 6902, 10554, 12090

Offset: 0

Author

Alois P. Heinz, Apr 29 2024

Keywords

• nonn
• tabf

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

			Triangle T(n,k) begins:
  1;
  1;
  1,  2;
  1,  4,   6;
  1,  8,  14,  18,  24;
  1, 16,  46,  54,  78,  96, 120;
  1, 32, 146, 162, 230, 330, 384, 426, 504, 600, 720;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..28, 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

Crossrefs

Columns k=1-3 give: A000012, A011782 (for n>=2), A027649(n-2) (for n>=4).

Row sums give A372395.

Cf. A000041, A000142, A001563, A267383, A372254, A372261, A372326, A370614.

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:
h:= proc() option remember; local q, l, b; q, l, b:= -1, args,
      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:
b:= proc(n, i, l) `if`(n=0 or i=1, [h([l[], 1$n, 0])],
     [b(n-i, min(n-i, i), [l[], i])[], b(n, i-1, l)[]])
    end:
T:= n-> sort(b(n$2, []))[]:
seq(T(n), n=0..10);

Formula

T(n,A000041(n)) = A000142(n).

T(n,A000041(n)-1) = A001563(n-1) for n>=2.