A380336 Triangular array read by rows. T(n,k) is the number of ways to choose a size k subset S of [n] and form a labeled acyclic digraph on S. Then form another labeled acyclic digraph on [n]-S. For each pair u in S and v in [n]-S add the directed edge u->v or not, n>=0, 0<=k<=n.

1, 1, 1, 3, 4, 3, 25, 36, 36, 25, 543, 800, 864, 800, 543, 29281, 43440, 48000, 48000, 43440, 29281, 3781503, 5621952, 6255360, 6400000, 6255360, 5621952, 3781503, 1138779265, 1694113344, 1888975872, 1946112000, 1946112000, 1888975872, 1694113344, 1138779265

Offset

0,4

Links

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

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.

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

Formula

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

T(n,k) = binomial(n,k)*A003024(k)*A003024(n-k)*2^(k*(n-k)). - Alois P. Heinz, Jan 22 2025

Example

Triangle T(n,k) begins:
     1;
     1,     1;
     3,     4,     3;
    25,    36,    36,    25;
   543,   800,   864,   800,   543;
 29281, 43440, 48000, 48000, 43440, 29281;
 ...

Mathematica

nn = 6; B[n_] := n! 2^Binomial[n, 2]; e[z_] := Sum[z^n/B[n], {n, 0, nn}]; Map[Select[#, # > 0 &] &, Table[B[n], {n, 0, nn}] CoefficientList[Series[1/e[-u z]*1/e[-z], {z, 0, nn}], {z, u}]] // Grid

Crossrefs

Cf. A339934 (row sums), A003024 (column k=0 and main diagonal).

Sequence in context: A287463 A288404 A287986 * A190959 A038018 A108658

Adjacent sequences: A380333 A380334 A380335 * A380337 A380338 A380339

Keyword

nonn,tabl

Author

Geoffrey Critzer, Jan 21 2025

Status

approved