A002031 Number of labeled connected digraphs on n nodes where every node has indegree 0 or outdegree 0 and no isolated nodes.

2, 6, 38, 390, 6062, 134526, 4172198, 178449270, 10508108222, 853219059726, 95965963939958, 15015789392011590, 3282145108526132942, 1005193051984479922206, 432437051675617901246918, 261774334771663762228012950, 223306437526333657726283273822

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

Also number of labeled connected graphs with 2-colored nodes with no isolated nodes where black nodes are only connected to white nodes and vice versa.

In- or outdegree zero implies loops are not admitted. Multi-arcs are not admitted. - R. J. Mathar, Nov 18 2023

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 2..100
• R. C. Read, E. M. Wright, Colored graphs: A correction and extension, Canad. J. Math. 22 1970 594-596.
• N. J. A. Sloane, Transforms

Crossrefs

Cf. A001831, A001832, A002032, A047863, A052332, A007776 (unlabeled case). Essentially the same as A002027.

Programs

Maple

logtr:= proc(p) local b; b:=proc(n) option remember; local k; if n=0 then 1 else p(n)- add(k *binomial(n,k) *p(n-k) *b(k), k=1..n-1)/n fi end end: digr:= n-> add(binomial(n,k) *(2^k-2)^(n-k), k=0..n): a:= logtr(digr): seq(a(n), n=2..25);  # Alois P. Heinz, Sep 14 2008

Mathematica

terms = 17; s = Log[Sum[Exp[(2^n - 2)*x]*(x^n/n!), {n, 0, terms+2}]] + O[x]^(terms+2); Drop[CoefficientList[s, x]*Range[0, terms+1]!, 2] (* Jean-François Alcover, Nov 08 2011, after Vladeta Jovovic, updated Jan 12 2018 *)

Formula

Logarithmic transform of A052332.

E.g.f.: log(Sum(exp((2^n-2)*x)*x^n/n!, n=0..infinity)). - Vladeta Jovovic, May 28 2004

a(n) = f(n,2) using functions defined in A002032. - Sean A. Irvine, May 29 2013

Extensions

More terms, formula and new title from Christian G. Bower, Dec 15 1999

Corrected by Vladeta Jovovic, Apr 12 2003