A350487 Triangle read by rows: T(n,k) is the number of acyclic digraphs on n labeled nodes with k arcs and a global source, n >= 1, k = 0..n*(n-1)/2.

1, 0, 2, 0, 0, 9, 6, 0, 0, 0, 64, 132, 96, 24, 0, 0, 0, 0, 625, 2640, 4850, 4900, 2850, 900, 120, 0, 0, 0, 0, 0, 7776, 55800, 186480, 379170, 516660, 491040, 328680, 152640, 46980, 8640, 720, 0, 0, 0, 0, 0, 0, 117649, 1286670, 6756120, 22466010

Offset

1,3

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)

Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.

Example

Triangle begins:
  [1] 1;
  [2] 0, 2;
  [3] 0, 0, 9,  6;
  [4] 0, 0, 0, 64, 132,   96,   24;
  [5] 0, 0, 0,  0, 625, 2640, 4850, 4900, 2850, 900, 120;
  ...

Prog

(PARI)
T(n)={my(a=vector(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1)*binomial(n, k)*((1+'y)^(n-k)-1)^k*a[n-k])); [Vecrev(p) | p <- a]}
{ my(A=T(6)); for(n=1, #A, print(A[n])) }

Crossrefs

Row sums are A003025.

Leading diagonal is A000169.

The unlabeled version is A350488.

Cf. A081064.

Sequence in context: A246714 A246708 A249387 * A258759 A350793 A181499

Adjacent sequences: A350484 A350485 A350486 * A350488 A350489 A350490

Keyword

nonn,tabf

Author

Andrew Howroyd, Jan 01 2022

Status

approved