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

Author

Geoffrey Critzer, Jan 21 2021

Keywords

• nonn
• tabl

Examples

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

Links

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

Crossrefs

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

Programs

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

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.