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

[Max A.]

I've just sent the following 4 new related sequences to Neil.

BTW, there are some interesting properties to explore:
1) A125210(n,2)=0 for any n?
2) A125208(n,n-1)=n for n>=3 ?
3) For n>=4, the third non-zero coefficient in each row of A125208 is
A125208(n,2n-4) ?
4) For which n, A125208(n,2n-4) = -A125208(n,2n-3) ? It is so for n=5,7,8,9,10.
...
Max

%I A125208
%S A125208 1,1,1,1,0,3,-1,1,0,0,4,3,-6,2,1,0,0,0,5,0,10,-10,-15,20,-6,1,0,0,0,0,6,0,
%T A125208 0,15,-5,0,-60,25,90,-90,24,1,0,0,0,0,0,7,0,0,0,21,-21,35,0,-105,0,-105,
%U A125208 420,0,-630,504,-120,1,0,0,0,0,0,0,8,0,0,0,0,28,-28,0,56,35,-168,112,-280
%N A125208 Triangular array A(n,k) (n>=1, 0<=k<=n(n-1)/2) such that
SUM A(n,k)*p^k
           gives the expectation of the number of connected components
after deleting
           every edge of the complete graph on n labeled vertices with
probability p.
%F A125208 G.f.: Sum_{n,k} A(n,k)*x^n/(p^(n*(n-1)/2)*n!) =
H(x,p)*exp(H(x,p)) where
           H(x,p)=Sum_{n=1..oo} x^n/(p^(n*(n-1)/2)*n!).
%F A125208 Sum_k A(n,k)*p^k = Sum_k A125205(n,k)*p^(n*(n-1)/2-k)*(1-p)^k
%F A125210 Sum_k A(n,k)*p^k = Sum_k A125206(n,k)*(1-p)^(n*(n-1)/2-k)*p^k
%e A125208 The array starts with
%e A125208 1
%e A125208 1, 1
%e A125208 1, 0, 3, -1
%e A125208 1, 0, 0, 4, 3, -6, 2
%e A125208 1, 0, 0, 0, 5, 0, 10, -10, -15, 20, -6
%e A125208 ...
%e A125208 SUM A(3,k)*p^k = 1+3*p^2-p^3 is the expectation of the
number of connected
           components in a complete graph on 3 labeled vertices where
every edge is
           removed with probability p.
%o A125208 (PARI) { reverse(v)=vector(length(v),i,v[length(v)+1-i]) }
           H=sum(n=0,6,x^n/p^(n*(n-1)/2)/n!); A=H*log(H);
           for(n=1,6,print(reverse(Vec(p^(n*(n-1)/2)*n!*polcoeff(A,n,x)))))
%Y A125208 Cf. A125205, A125206, A125209 (row-reversed version),
A125210 (dual version).
%K A125208 nonn,sign,tabf
%O A125208 1,6
%A A125208 Max Alekseyev (maxal(AT)cs.ucsd.edu), Jan 09 2007


%I A125209
%S A125209 1,1,1,-1,3,0,1,2,-6,3,4,0,0,1,-6,20,-15,-10,10,0,5,0,0,0,1,24,-90,90,25,
%T A125209 -60,0,-5,15,0,0,6,0,0,0,0,1,-120,504,-630,0,420,-105,0,-105,0,35,-21,21,
%U A125209 0,0,0,7,0,0,0,0,0,1,720,-3360,5040,-1176,-3150,1680,140,560,-210,-280,112
%N A125209 Triangular array A(n,k) (n>=1, 0<=k<=n(n-1)/2) such that
SUM A(n,k)*p^(n*(n-1)/2-k)
           gives the expectation of the number of connected components
after deleting
           every edge of the complete graph on n labeled vertices with
probability p.
%C A125209 Row-reversed version of A125208, see A125208 for further details
%e A125209 The array starts with
%e A125209 1
%e A125209 1, 1
%e A125209 -1, 3, 0, 1
%e A125209 2, -6, 3, 4, 0, 0, 1
%e A125209 -6, 20, -15, -10, 10, 0, 5, 0, 0, 0, 1
%e A125209 ...
%Y A125209 Cf. A125208 (row-reversed version), A127258 (dual version).
%K A125209 nonn,sign,tabf
%O A125209 1,5
%A A125209 Max Alekseyev (maxal(AT)cs.ucsd.edu), Jan 09 2007



%I A125210
%S A125210 1,2,-1,3,-3,0,1,4,-6,0,4,3,-6,2,5,-10,0,10,15,-18,-60,130,-105,40,-6,6,
%T A125210 -15,0,20,45,-18,-330,60,2445,-6485,8712,-7260,3925,-1350,270,-24,7,-21,0,
%U A125210 35,105,42,-980,-1950,11760,12355,-182721,589281,-1128820,1502550,-1471305
%N A125210 Triangular array B(n,k) (n>=1, 0<=k<=n(n-1)/2) such that
SUM B(n,k)*q^k
           gives the expectation of the number of connected components
in a random
           graph on n labeled vertices where every edge is present
with probability q.
%F A125210 G.f.: Sum_{n,k} B(n,k)*x^n/((1-q)^(n*(n-1)/2)*n!) =
H(x,1-q)*exp(H(x,1-q))
           where H(x,p)=Sum_{n=1..oo} x^n/(p^(n*(n-1)/2)*n!).
%F A125210 Sum_k B(n,k)*q^k = Sum_k A125205(n,k)*(1-q)^(n*(n-1)/2-k)*q^k
%F A125210 Sum_k B(n,k)*q^k = Sum_k A125206(n,k)*q^(n*(n-1)/2-k)*(1-q)^k
%e A125210 The array starts with
%e A125210 1
%e A125210 2, -1
%e A125210 3, -3, 0, 1
%e A125210 4, -6, 0, 4, 3, -6, 2
%e A125210 5, -10, 0, 10, 15, -18, -60, 130, -105, 40, -6
%e A125210 ...
%e A125210 SUM B(3,k)*q^k = 3-3*q+q^3 is the expectation of the number
of connected
           components in a random graph on 3 labeled vertices where
every edge is
           present with probability q.
%o A125210 (PARI) { reverse(v)=vector(length(v),i,v[length(v)+1-i]) }
           H=sum(n=0,6,x^n/(1-q)^(n*(n-1)/2)/n!); B=H*log(H);
           for(n=1,6,print(reverse(Vec((1-q)^(n*(n-1)/2)*n!*polcoeff(B,n,x)))))
%Y A125210 Cf. A125205, A125206, A127258 (row-reversed version),
A125208 (dual version).
%K A125210 nonn,sign,tabf
%O A125210 1,2
%A A125210 Max Alekseyev (maxal(AT)cs.ucsd.edu), Jan 09 2007


%I A127258
%S A127258 1,-1,2,1,0,-3,3,2,-6,3,4,0,-6,4,-6,40,-105,130,-60,-18,15,10,0,-10,5,-24,
%T A127258 270,-1350,3925,-7260,8712,-6485,2445,60,-330,-18,45,20,0,-15,6,120,-2016,
%U A127258 15750,-75810,250950,-603435,1084104,-1471305,1502550,-1128820,589281,-182721
%N A127258 Triangular array B(n,k) (n>=1, 0<=k<=n(n-1)/2) such that
SUM B(n,k)*q^(n*(n-1)/2-k)
           gives the expectation of the number of connected components
in a random
           graph on n labeled vertices where every edge is present
with probability q.
%C A127258 Row-reversed version of A125210, see A125210 for further details.
%e A127258 The array starts with
%e A127258 1
%e A127258 -1, 2
%e A127258 1, 0, -3, 3
%e A127258 2, -6, 3, 4, 0, -6, 4
%e A127258 -6, 40, -105, 130, -60, -18, 15, 10, 0, -10, 5
%e A127258 ...
%Y A127258 Cf. A125210 (row-reversed version), A125209 (dual version).
%K A127258 nonn,sign,tabf
%O A127258 1,3
%A A127258 Max Alekseyev (maxal(AT)cs.ucsd.edu), Jan 09 2007





On 11/23/06, Max A. <maxale at gmail.com> wrote:
> 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
>