A340798 Square array read by descending antidiagonals. Let G be a simple labeled graph on n nodes. T(n,k) is the number of ways to give G an acyclic orientation and a coloring function C:V(G) -> {1,2,...,k} so that u->v implies C(u) >= C(v) for all u,v in V(G), n >= 0, k >= 0.

1, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 3, 10, 25, 0, 1, 4, 21, 122, 543, 0, 1, 5, 36, 339, 3550, 29281, 0, 1, 6, 55, 724, 12477, 241442, 3781503, 0, 1, 7, 78, 1325, 32316, 1035843, 37717630, 1138779265, 0

Offset

0,8

Links

Table of n, a(n) for n=0..44.

R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.

Formula

Let E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)). Then Sum_{n>=0} T(n,k)*x^n/(n!*2^binomial(n,2)) = 1/E(-x)^k.

T(n,k) = (-1)^n p_n(-k) where p_n is the n-th polynomial described in A219765.

Example

Array begins
  1,     1,      1,       1,       1,       1, ...
  0,     1,      2,       3,       4,       5, ...
  0,     3,     10,      21,      36,      55, ...
  0,    25,    122,     339,     724,    1325, ...
  0,   543,   3550,   12477,   32316,   69595, ...
  0, 29281, 241442, 1035843, 3180484, 7934885, ...
  ...

Mathematica

nn = 6; e[x_] := Sum[x^n/(n! 2^Binomial[n, 2]), {n, 0, nn}];
Prepend[Table[Table[n! 2^Binomial[n, 2], {n, 0, nn}] CoefficientList[
      Series[1/e[-x]^k, {x, 0, nn}], x], {k, 1, nn}], PadRight[{1}, nn + 1]] // Transpose // Grid

Crossrefs

Cf. A003024 (column k=1), A339934 (column k=2), A322280, A219765.

Sequence in context: A320079 A349971 A340986 * A355427 A122078 A292783

Adjacent sequences: A340795 A340796 A340797 * A340799 A340800 A340801

Keyword

nonn,tabl

Author

Geoffrey Critzer, Jan 21 2021

Status

approved