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