connected components in subgraphs of the complete graph: A125205 - A125207

[Max A.]

SeqFans,

I've just sent to Neil the following three sequences that you may find
interesting.

It would be also interesting to compute unlabeled variants of these
sequences. If you like to contribute, please do.

Regards,
Max


%I A125205
%S A125205 1,2,1,3,6,3,1,4,18,30,24,15,6,1,5,40,135,250,295,282,215,120,45,10,1,6,
%T A125205 75,420,1385,3015,4800,6365,7170,6705,5065,3009,1365,455,105,15,1,7,126,
%U A125205 1050,5355,18690,47880,96796,166890,251370,329945,373947,362292,297115
%N A125205 Triangular array T(n,k) (n>=1, 0<=k<=n(n-1)/2) giving the
total number
           of connected components in all subgraphs (V,E') with |E'|=k of
           the complete labeled graph K_n=(V,E).
%F A125205 g.f.: Sum_{n,k}
T(n,k)*x^n/n!*y^k=(F(x,y)-1)*exp(F(x,y)-1)=G(x,y)*ln(G(x,y))
           where G(x,y)=Sum_{n=0..oo} (1+y)^(n(n-1)/2)*x^n/n!, and
F(x,y)=1+ln(G(x,y))
           is g.f. of A062734.
%e A125205 The array starts with
           1
           2, 1
           3, 6, 3, 1
           4, 18, 30, 24, 15, 6, 1
           5, 40, 135, 250, 295, 282, 215, 120, 45, 10, 1
           ...
%e A125205 T(3,1)=6 since there are three different subgraphs of K_3
with one edge,
           and each subgraph has two connected components.
%o A125205 (PARI) { reverse(v)=vector(length(v),i,v[length(v)+1-i]) }
           G=sum(n=0,6,(1+y)^(n*(n-1)/2)*x^n/n!); K=G*log(G);
           for(n=1,6,print(reverse(Vec(n!*polcoeff(K,n,x)))))
%Y A125205 Cf. A062734
%Y A125205 Cf. A125206 (row-reversed version), A125207 (row sums)
%K A125205 nonn,tabf
%O A125205 1,2
%A A125205 Max Alekseyev (maxal(AT)cs.ucsd.edu), Nov 23 2006



%I A125206
%S A125206 1,1,2,1,3,6,3,1,6,15,24,30,18,4,1,10,45,120,215,282,295,250,135,40,5,1,
%T A125206 15,105,455,1365,3009,5065,6705,7170,6365,4800,3015,1385,420,75,6,1,21,210,
%U A125206 1330,5985,20349,54271,116385,204225,297115,362292,373947,329945,251370
%N A125206 Triangular array T(n,k) (n>=1, 0<=k<=n(n-1)/2) giving the
total number
           of connected components in all subgraphs obtained from the complete
           labeled graph K_n by removing k edges.
%C A125206 Row-reversed version of A125205, see A125205 for further details
%e A125206 The array starts with
           1
           1, 2
           1, 3, 6, 3
           1, 6, 15, 24, 30, 18, 4
           1, 10, 45, 120, 215, 282, 295, 250, 135, 40, 5
           ...
%Y A125206 Cf. A125205 (row-reversed version), A125207 (row sums)
%K A125206 nonn,tabf
%O A125206 1,3
%A A125206 Max Alekseyev (maxal(AT)cs.ucsd.edu), Nov 23 2006




%I A125207
%S A125207 1,3,13,98,1398,39956,2354240,286394544,71225744048,35884971729760,36419817759267072,
%T A125207 74221711070826087424,303193538300703211111936,2480118087478081928075065344,
%U A125207 40601989279034990139321984265216,1329877330680067685563700135615633408
%N A125207 The total number of connected components in all subgraphs
obtained from
           the complete labeled graph K_n by removing zero or more edges.
%F A125207 E.g.f.: (F(x)-1)*exp(F(x)-1) = G(x)*ln(G(x)) where
           G(x)=Sum_{n=0..oo} 2^(n(n-1)/2)*x^n/n! and F(x)=1+ln(G(x))
is e.g.f. of A001187
%e A125207 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).
%o A125207 (PARI) G=sum(n=0,30,2^(n*(n-1)/2)*x^n/n!) + O(x31); v=Vec(G*log(G));
           for(i=1,length(v),v[i]*=i!); print(v)
%Y A125207 Cf. A001187, A125205, A125206
%K A125207 nonn
%O A125207 1,2
%A A125207 Max Alekseyev (maxal(AT)cs.ucsd.edu), Nov 23 2006