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

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.

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

Formula

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

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

Example

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

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

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.

Sequence in context: A220226 A181854 A109822 * A274292 A359670 A114192

Adjacent sequences: A372393 A372394 A372395 * A372397 A372398 A372399

Keyword

nonn,tabf

Author

Alois P. Heinz, Apr 29 2024

Status

approved