A026586 Number of labeled essential directed acyclic graphs (DAGs).

1, 1, 1, 4, 59, 2616, 306117, 87716644, 58874478231, 90018247082416, 307775459402071913, 2322338398654088751036, 38293189001166839643861795, 1369158635491114830895696234696, 105480725505896171175318367295035341, 17416945807332261902008739771330860775380

Offset

0,4

Links

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

Bertran Steinsky, Enumeration of labelled chain graphs and labeled essential directed acyclic graphs, Discrete Mathematics, 270 (2003), 267-278.

Formula

a(0)=1, a(n) = Sum_{k=1..n} (-1)^(k+1) * binomial(n, k) * (2^(n-k)-n+k)^k * a(n-k) [from Steinsky]. - Sean A. Irvine, Oct 06 2019

A003024(n)/a(n) ~ 13.65179785877679224078127260356664922274658604... [Steinsky, p. 271]. - Vaclav Kotesovec, Feb 07 2026

a(n) ~ c * d^n * n! * 2^(n^2/2), where d = 0.47518108723325255291622736502756019698156787... and c = 0.12753346799475902640954064813977558377430986... - Vaclav Kotesovec, Feb 07 2026

Mathematica

a[0]=1; a[n_]:= a[n] = Sum[(-1)^(k+1)Binomial[n, k](2^(n-k)-n+k)^k a[n-k], {k, n}]; Array[a, 16, 0] (* Stefano Spezia, May 28 2024, accelerated by Vaclav Kotesovec, Feb 07 2026 *)

Crossrefs

Cf. A003024.

Sequence in context: A264820 A194534 A331712 * A298064 A298713 A058173

Adjacent sequences: A026583 A026584 A026585 * A026587 A026588 A026589

Keyword

nonn

Author

Detlef Pauly (dettodet(AT)yahoo.de), Aug 22 2003

Extensions

a(0)=1 inserted by Sean A. Irvine, Oct 06 2019

a(15) from Stefano Spezia, May 28 2024

Status

approved