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

Author

Geoffrey Critzer, Feb 21 2021

Keywords

• nonn
• tabl

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.

Examples

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

Links

• Seiichi Manyama, Antidiagonals n = 0..50, flattened
• R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.

Crossrefs

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

Main diagonal gives A354962.

Programs

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

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