login
A125207
Total number of connected components in all subgraphs obtained from the complete labeled graph K_n by removing zero or more edges.
7
1, 3, 13, 98, 1398, 39956, 2354240, 286394544, 71225744048, 35884971729760, 36419817759267072, 74221711070826087424, 303193538300703211111936, 2480118087478081928075065344, 40601989279034990139321984265216, 1329877330680067685563700135615633408
OFFSET
1,2
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
LINKS
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
EXAMPLE
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).
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 *)
PROG
(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)
CROSSREFS
KEYWORD
nonn
AUTHOR
Max Alekseyev, Nov 23 2006
STATUS
approved