A026586 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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

MATHEMATICA

a[0]=1; 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 *)

CROSSREFS

Sequence in context: A264820 A194534 A331712 * A298064 A298713 A058173