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

1, 2, 12, 216, 10600, 1306620, 384471444, 261548825328, 402632012394000, 1381332938730123060, 10440873023366019273820, 172308823347127690038311496, 6163501139185639837183141411320, 474942255590583211554917995123517868, 78430816994991932467786587093292327531620

Offset

1,2

Links

Andrew Howroyd, Table of n, a(n) for n = 1..50

Antoine Genitrini, Martin Pépin, and Alfredo Viola, Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling, hal-03029381 [math.CO], [cs.DM], [cs.DS], 2020.

Ira Gessel, Counting Acyclic Digraphs by Sources and Sinks

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.

Mathematica

nn = 10; B[n_] := n! 2^Binomial[n, 2]; e[z_] := Sum[z^n/B[n], {n, 0, nn}];
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 *)

Prog

(PARI) \\ see Marcel et al. link. B(n) is A003025 as vector.
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}
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

Crossrefs

The unlabeled version is A345258.

Cf. A003024, A003025, A049524, A361210.

Sequence in context: A123118 A367051 A182161 * A208651 A083667 A092124

Adjacent sequences: A165947 A165948 A165949 * A165951 A165952 A165953

Keyword

nonn

Author

Vladeta Jovovic, Oct 01 2009

Extensions

a(1)=1 inserted and terms a(13) and beyond from Andrew Howroyd, Jan 01 2022

Status

approved