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

Author

Shuaib Ahmed S, May 29 2014

Keywords

• nonn

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)

Crossrefs

Cf. A003024, A038154.

Programs

MATLAB

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

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

Extensions

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