A339768 Square array read by descending antidiagonals. T(n,k) is the number of acyclic k-multidigraphs on n labeled vertices, n>=0,k>=0.

1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 25, 1, 1, 1, 7, 109, 543, 1, 1, 1, 9, 289, 9449, 29281, 1, 1, 1, 11, 601, 63487, 3068281, 3781503, 1, 1, 1, 13, 1081, 267249, 69711361, 3586048685, 1138779265, 1

Offset

0,9

Comments

Here, a k-multidigraph is a directed graph where up to k arcs (directed edges) are allowed to join vertex pairs. The arcs have no identity, i.e., they are indistinguishable except for the ordered pair of distinct vertices that they join.

Links

Seiichi Manyama, Antidiagonals n = 0..50, flattened

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

Formula

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

T(0,k) = 1 and T(n,k) = Sum_{j=1..n} (-1)^(j+1) * (k+1)^(j*(n-j)) * binomial(n,j) * T(n-j,k) for n > 0. - Seiichi Manyama, Jun 13 2022

Example

  1,     1,       1,        1,         1,          1, ...
  1,     1,       1,        1,         1,          1, ...
  1,     3,       5,        7,         9,         11, ...
  1,    25,     109,      289,       601,       1081, ...
  1,   543,    9449,    63487,    267249,     849311, ...
  1, 29281, 3068281, 69711361, 742650001, 5004309601, ...

Mathematica

nn = 5; Table[g[n_] := q^Binomial[n, 2] n!; e[z_] := Sum[z^k/g[k], {k, 0, nn}];
   Table[g[n], {n, 0, nn}] CoefficientList[Series[1/e[-z], {z, 0, nn}], z], {q, 1, nn + 1}] //Transpose // Grid

Crossrefs

Cf. A003024 (column k=1), A188457 (column k=2), A137435 (column k=3).

Main diagonal gives A354962.

Sequence in context: A348481 A274391 A368862 * A372644 A348954 A126799

Adjacent sequences: A339765 A339766 A339767 * A339769 A339770 A339771

Keyword

nonn,tabl

Author

Geoffrey Critzer, Feb 21 2021

Status

approved