A226773 Number of ways to select a simple labeled graph on n nodes and then select a subset of its connected components.

1, 2, 6, 28, 216, 3008, 82944, 4774912, 575299584, 142633336832, 71796623671296, 72847596766363648, 148448195686743146496, 606392780411924463484928, 4960249711027691772375465984, 81204042297885177526853243502592, 2659755256932431408054237587983826944

Offset: 0

Author

Geoffrey Critzer, Jun 17 2013

Keywords

• nonn

Comments

Since almost all such graphs are connected a(n) is asymptotic to 2*A006125.

Links

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

Programs

Maple

b:= n-> 2^(n*(n-1)/2):
a:= n-> (t-> add(`if`(j=t, 1, 2)*b(j)*b(n-j)
             *binomial(n, j), j=0..t))(n/2):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 01 2016

Mathematica

nn=15; g=Sum[2^Binomial[n,2] x^n/n!, {n,0,nn}]; Range[0,nn]! CoefficientList[Series[g^2, {x,0,nn}], x]

Formula

E.g.f.: A(x)^2 = B(x,y) (evaluated at y = 2) where A(x) is the e.g.f. for A006125 and B(x,y) is the e.g.f. for A143543.