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

%I #17 Feb 02 2024 17:55:46

%S 1,2,6,28,216,3008,82944,4774912,575299584,142633336832,

%T 71796623671296,72847596766363648,148448195686743146496,

%U 606392780411924463484928,4960249711027691772375465984,81204042297885177526853243502592,2659755256932431408054237587983826944

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

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

%H Alois P. Heinz, <a href="/A226773/b226773.txt">Table of n, a(n) for n = 0..81</a>

%F 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.

%p b:= n-> 2^(n*(n-1)/2):

%p a:= n-> (t-> add(`if`(j=t, 1, 2)*b(j)*b(n-j)

%p *binomial(n, j), j=0..t))(n/2):

%p seq(a(n), n=0..20); # _Alois P. Heinz_, Aug 01 2016

%t 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]

%K nonn

%O 0,2

%A _Geoffrey Critzer_, Jun 17 2013