login
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.
3

%I #12 Jan 08 2022 19:24:37

%S 1,0,2,0,0,9,6,0,0,0,64,132,96,24,0,0,0,0,625,2640,4850,4900,2850,900,

%T 120,0,0,0,0,0,7776,55800,186480,379170,516660,491040,328680,152640,

%U 46980,8640,720,0,0,0,0,0,0,117649,1286670,6756120,22466010

%N 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.

%H Andrew Howroyd, <a href="/A350487/b350487.txt">Table of n, a(n) for n = 1..1350</a> (rows 1..20)

%H Marcel et al., <a href="https://mathoverflow.net/q/395095">Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?</a>, MathOverflow, 2021.

%e Triangle begins:

%e [1] 1;

%e [2] 0, 2;

%e [3] 0, 0, 9, 6;

%e [4] 0, 0, 0, 64, 132, 96, 24;

%e [5] 0, 0, 0, 0, 625, 2640, 4850, 4900, 2850, 900, 120;

%e ...

%o (PARI)

%o 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]}

%o { my(A=T(6)); for(n=1, #A, print(A[n])) }

%Y Row sums are A003025.

%Y Leading diagonal is A000169.

%Y The unlabeled version is A350488.

%Y Cf. A081064.

%K nonn,tabf

%O 1,3

%A _Andrew Howroyd_, Jan 01 2022