cp's OEIS Frontend

A165950 Number of acyclic digraphs on n labeled nodes with one source and one sink.

%I A165950 #15 Apr 15 2023 14:27:43
%S A165950 1,2,12,216,10600,1306620,384471444,261548825328,402632012394000,
%T A165950 1381332938730123060,10440873023366019273820,
%U A165950 172308823347127690038311496,6163501139185639837183141411320,474942255590583211554917995123517868,78430816994991932467786587093292327531620
%N A165950 Number of acyclic digraphs on n labeled nodes with one source and one sink.
%H A165950 Andrew Howroyd, <a href="/A165950/b165950.txt">Table of n, a(n) for n = 1..50</a>
%H A165950 Antoine Genitrini, Martin Pépin, and Alfredo Viola, <a href="https://hal.sorbonne-universite.fr/hal-03029381v2">Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling</a>, hal-03029381 [math.CO], [cs.DM], [cs.DS], 2020.
%H A165950 Ira Gessel, <a href="http://people.brandeis.edu/~gessel/homepage/papers/acyclic.pdf">Counting Acyclic Digraphs by Sources and Sinks</a>
%H A165950 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.
%t A165950 nn = 10; B[n_] := n! 2^Binomial[n, 2];e[z_] := Sum[z^n/B[n], {n, 0, nn}];
%t A165950 egf[ggf_] := Normal[Series[ggf, {z, 0, nn}]] /. Table[z^i -> z^i*2^Binomial[i, 2], {i, 1, nn + 1}]; Map[ Coefficient[#, u v] &,Table[n!, {n, 0, nn}] CoefficientList[ Series[Exp[(u - 1) (v - 1) z] egf[e[(u - 1) z]*1/e[-z]*e[(v - 1) z]], {z, 0, nn}], z]] (* _Geoffrey Critzer_, Apr 15 2023 *)
%o A165950 (PARI) \\ see Marcel et al. link. B(n) is A003025 as vector.
%o A165950 B(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)*(2^(n-k)-1)^k*a[n-k])); a}
%o A165950 seq(n)={my(a=vector(n), b=B(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1) * binomial(n,k) * k * (2^(n-k)-1)^k * b[n-k])); a} \\ _Andrew Howroyd_, Jan 01 2022
%Y A165950 The unlabeled version is A345258.
%Y A165950 Cf. A003024, A003025, A049524, A361210.
%K A165950 nonn
%O A165950 1,2
%A A165950 _Vladeta Jovovic_, Oct 01 2009
%E A165950 a(1)=1 inserted and terms a(13) and beyond from _Andrew Howroyd_, Jan 01 2022