A382223 Rectangular array read by antidiagonals: T(n,k) is the number of labeled digraphs on [n] along with a (coloring) function c:[n] -> [k] with the property 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, 1, 2, 1, 0, 1, 5, 3, 1, 0, 1, 16, 12, 4, 1, 0, 1, 67, 66, 22, 5, 1, 0, 1, 374, 513, 172, 35, 6, 1, 0, 1, 2825, 5769, 1969, 355, 51, 7, 1, 0, 1, 29212, 95706, 33856, 5380, 636, 70, 8, 1, 0, 1, 417199, 2379348, 893188, 125090, 12006, 1036, 92, 9, 1

Offset

0,9

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) = 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, 1,   5,   12,    22,     35,     51,...
 0, 1,  16,   66,   172,    355,    636,...
 0, 1,  67,  513,  1969,   5380,  12006,...
 0, 1, 374, 5769, 33856, 125090, 352476,...

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[e[z]^k, {z, 0, nn}], z], {k, 1, nn}]]], -1]; Table[zetapolys /. x -> i, {i, 0, nn}] // Transpose // Grid

Crossrefs

Cf. A006116 column k=2, A289539 column k=3, A005329, A382363.

Sequence in context: A291883 A361957 A239145 * A388992 A327127 A151824

Adjacent sequences: A382220 A382221 A382222 * A382224 A382225 A382226

Keyword

nonn,tabl

Author

Geoffrey Critzer, Mar 23 2025

Status

approved