A243014 Number of acyclic digraphs (DAGS) on n labeled nodes, where the indegree and outdegree of each node is at most 1.

1, 1, 3, 13, 61, 321, 1951, 13693, 109593, 986401, 9864091, 108505101, 1302061333, 16926797473, 236975164791, 3554627472061, 56874039553201, 966858672404673, 17403456103284403, 330665665962403981, 6613313319248079981, 138879579704209680001

Offset

0,3

Comments

a(n) is the number of acyclic digraphs (DAGS) on n labeled nodes, where the indegree and outdegree of each node is at most 1. For example, with vertex set {A,B,C} the possible ways are: one 3-component graph {A,B,C}, six 2-component graph {{A->B,C},{B->A,C},{A->C,B},{C->A,B},{C->B,A},{B->C,A}}, and six 1-component graph {{A->B->C},{B->A->C},{A->C->B},{C->A->B},{C->B->A},{B->C->A}}.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..449

Eric Weisstein's World of Mathematics, Acyclic Digraph.

Index entries for sequences related to digraphs (or directed graphs)

Formula

a(n) = (n!*Sum(1/k!))+1, k=0..n-2.

a(n) = (n*(a(n-1)+n-2))+1, for n>1, a(1)=1.

a(n) = A038154(n)+1.

E.g.f.: exp(x)*(x^2-x+1)/(1-x). - Alois P. Heinz, Aug 21 2017

Prog

(MATLAB) @(n)(factorial(n)*sum(1./(factorial(0:n-2)))+1)

Crossrefs

Cf. A003024, A038154.

Sequence in context: A200215 A074548 A367059 * A258799 A375651 A246689

Adjacent sequences: A243011 A243012 A243013 * A243015 A243016 A243017

Keyword

nonn

Author

Shuaib Ahmed S, May 29 2014

Extensions

a(0)=1 prepended, one term corrected, more terms added by Alois P. Heinz, Aug 21 2017

Status

approved