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,2

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

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.

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]

Crossrefs

Sequence in context: A305627 A006117 A118025 * A370926 A119966 A256599

Adjacent sequences: A226770 A226771 A226772 * A226774 A226775 A226776

Keyword

nonn

Author

Geoffrey Critzer, Jun 17 2013

Status

approved