A370614 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 into distinct parts; triangle T(n,k), n>=0, k = 1..A000009(n), read by rows.

1, 1, 1, 1, 4, 1, 8, 1, 16, 46, 1, 32, 146, 330, 1, 64, 454, 1066, 1374, 1, 128, 1394, 4718, 5658, 10554, 1, 256, 4246, 20266, 23118, 41506, 57054, 101502, 1, 512, 12866, 85310, 93930, 237686, 302730, 525642, 657210, 1165104, 1, 1024, 38854, 354106, 380094

Offset: 0

Author

Alois P. Heinz, Apr 30 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;
  1,   4;
  1,   8;
  1,  16,   46;
  1,  32,  146,   330;
  1,  64,  454,  1066,  1374;
  1, 128, 1394,  4718,  5658, 10554;
  1, 256, 4246, 20266, 23118, 41506, 57054, 101502;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..46, 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-2 give: A000012, A011782 (for n>=3).

Row sums give A370613.

Cf. A000009, A267383, A372254, A372261, A372326, A372396.

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`(i*(i+1)/2 sort(b(n$2, [0]))[]:
seq(T(n), n=0..12);