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

%I #23 Feb 02 2024 18:31:56

%S 1,3,13,98,1398,39956,2354240,286394544,71225744048,35884971729760,

%T 36419817759267072,74221711070826087424,303193538300703211111936,

%U 2480118087478081928075065344,40601989279034990139321984265216,1329877330680067685563700135615633408

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

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

%H Alois P. Heinz, <a href="/A125207/b125207.txt">Table of n, a(n) for n = 1..82</a>

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

%F a(n) = Sum_{k=1..n} k * A143543(n,k). - _Alois P. Heinz_, Feb 02 2024

%e 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).

%t f[list_]:= Total[Table[i list[[i]],{i,1,Length[list]}]];

%t a= Sum[2^Binomial[n,2] x^n/n!,{n,0,20}];

%t 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 *)

%o (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)

%Y Cf. A001187, A125205, A125206, A143543.

%K nonn

%O 1,2

%A _Max Alekseyev_, Nov 23 2006