login
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.
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
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
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer, Jan 21 2021
STATUS
approved