A382363 Rectangular array read by antidiagonals, T(n,k) is the number of labeled digraphs on [n] along with a (coloring) function c:[n] -> [k] such that for all u,v in [n], u->v implies u<=v and c(u)<=c(v), n>=0, k>=0.

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 8, 7, 3, 1, 0, 64, 44, 15, 4, 1, 0, 1024, 508, 129, 26, 5, 1, 0, 32768, 10976, 1962, 284, 40, 6, 1, 0, 2097152, 450496, 54036, 5371, 530, 57, 7, 1, 0, 268435456, 35535872, 2747880, 180424, 11995, 888, 77, 8, 1, 0, 68719476736, 5435551744, 262091808, 10997576, 476165, 23409, 1379, 100, 9, 1

Offset

0,8

Links

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

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, Discrete Mathematics, Vol. 343, No. 11 (2020), 112041; arXiv preprint, arXiv:1909.01550 [math.CO], 2019-2020; See Table 2.

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

Formula

Sum_{n>=0} T(n,k)/A005329(n) = 1/e(-x)^k, where e(x) = Sum_{n>=0}x^n/A005329(n).

Example

  1,    1,     1,     1,      1,      1,       1,...
  0,    1,     2,     3,      4,      5,       6,...
  0,    2,     7,    15,     26,     40,      57,...
  0,    8,    44,   129,    284,    530,     888,...
  0,   64,   508,  1962,   5371,  11995,   23409,...
  0, 1024, 10976, 54036, 180424, 476165, 1072854,...

Mathematica

nn = 6; B[n_] := QFactorial[n, 2]; e[z_] := Sum[z^n/B[n], {n, 0, nn}]; zetapolys = Drop[Map[Expand[InterpolatingPolynomial[#, x]] &, Transpose[Table[Table[B[n], {n, 0, nn}] CoefficientList[Series[1/e[-z]^k, {z, 0, nn}], z], {k, 1, nn}]]], -1]; Table[zetapolys /. x -> i, {i, 0, nn}] // Transpose // Grid

Crossrefs

Cf. A382223, A006125 (column k=1).

Sequence in context: A113080 A174420 A360604 * A266318 A011265 A357340

Adjacent sequences: A382360 A382361 A382362 * A382364 A382365 A382366

Keyword

nonn,tabl

Author

Geoffrey Critzer, Mar 23 2025

Status

approved