A003027 Number of weakly connected digraphs with n labeled nodes.

1, 3, 54, 3834, 1027080, 1067308488, 4390480193904, 72022346388181584, 4721717643249254751360, 1237892809110149882059440768, 1298060596773261804821355107253504, 5444502293680983802677246555274553481984, 91343781554246596956424128384394531707099632640

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

References

• R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n=1..30
• A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.

Crossrefs

The unlabeled case is A003085.

Row sums of A062735.

Cf. A053763 (not necessarily connected), A003030 (strongly connected).

Programs

Maple

b:= n-> 2^(n^2-n):
a:= proc(n) option remember; local k; `if`(n=0, 1,
      b(n)- add(k*binomial(n,k) *b(n-k)*a(k), k=1..n-1)/n)
    end:
seq(a(n), n=1..20);  # Alois P. Heinz, Oct 21 2012

Mathematica

Range[0, 20]! CoefficientList[Series[D[1 + Log[Sum[2^(n^2 - n) x^n/n!, {n, 0, 20}]], x], {x, 0,20}], x]
c[n_]:=2^(n(n-1))-Sum[k Binomial[n,k]c[k] 2^((n-k)(n-k-1)),{k,1,n-1}]/n;c[0]=1;Table[c[i],{i,0,20}]  (* Geoffrey Critzer, Oct 24 2012 *)

PARI

v=Vec(log(sum(n=0, default(seriesprecision), 2^(n^2-n)*x^n/n!))); for(i=1, #v, v[i]*=(i-1)!); v \\ Charles R Greathouse IV, Feb 14 2011

Sage

b = lambda n: 2^(n^2-n)
@cached_function
def A003027(n):
    return b(n) - sum(k*binomial(n, k)*b(n-k)*A003027(k) for k in (1..n-1)) / n
[A003027(n) for n in (1..13)] # Peter Luschny, Jan 18 2016

Formula

a(n) = A062738(n)/2^n, since binary relations = digraphs with loops. - Ralf Stephan and Vladeta Jovovic, Mar 24 2004

E.g.f.: log(sum n>=0, 2^(n^2-n)*x^n/n!).

a(n) = A053763(n) - (1/n) * Sum_{k=1..n-1} k*C(n,k)*a(k)*A053763(n-k). - Geoffrey Critzer, Oct 24 2012

Extensions

Corrected and extended by Vladeta Jovovic, Goran Kilibarda