A125207 Total number of connected components in all subgraphs obtained from the complete labeled graph K_n by removing zero or more edges.

1, 3, 13, 98, 1398, 39956, 2354240, 286394544, 71225744048, 35884971729760, 36419817759267072, 74221711070826087424, 303193538300703211111936, 2480118087478081928075065344, 40601989279034990139321984265216, 1329877330680067685563700135615633408

Offset: 1

Author

Max Alekseyev, Nov 23 2006

Keywords

• nonn

Comments

a(n)/A006125(n) is the expected number of connected components in a simple labeled graph on n vertices. - Geoffrey Critzer, May 09 2011

Examples

			For n=2, we have two graph on two vertices: complete and empty, the former has one connected component while the latter has two connected components. The total number of connected components is 3, which is a(2).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..82

Crossrefs

Cf. A001187, A125205, A125206, A143543.

Programs

Mathematica

f[list_]:= Total[Table[i list[[i]],{i,1,Length[list]}]];
a= Sum[2^Binomial[n,2] x^n/n!,{n,0,20}];
Map[f, Transpose[Table[Rest[Range[0, 20]! CoefficientList[Series[Log[a]^k/k!, {x, 0, 20}],x]], {k, 1, 20}]]] (* Geoffrey Critzer, May 09 2011 *)

PARI

G=sum(n=0,30,2^(n*(n-1)/2)*x^n/n!) + O(x^31); v=Vec(G*log(G)); for(i=1,length(v),v[i]*=i!); print(v)

Formula

E.g.f.: (F(x)-1)*exp(F(x)-1) = G(x)*log(G(x)) where G(x) = Sum_{n>=0} 2^(n(n-1)/2) * x^n/n! and F(x) = 1+log(G(x)) is the e.g.f. of A001187.

a(n) = Sum_{k=1..n} k * A143543(n,k). - Alois P. Heinz, Feb 02 2024