A125205 Irregular triangle read by rows 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).

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, 75, 420, 1385, 3015, 4800, 6365, 7170, 6705, 5065, 3009, 1365, 455, 105, 15, 1, 7, 126, 1050, 5355, 18690, 47880, 96796, 166890, 251370, 329945, 373947, 362292, 297115

Offset

1,2

Links

Table of n, a(n) for n=1..54.

Formula

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)*log(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+log(G(x,y)) is g.f. of A062734.

Example

Triangle begins:
  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;
  ...
T(3,1) = 6 since there are three different subgraphs of K_3 with one edge and each subgraph has two connected components.

Prog

(PARI) { G=sum(n=0, 6, (1+y)^(n*(n-1)/2)*x^n/n!); K=G*log(G); for(n=1, 6, print(Vecrev(n!*polcoeff(K, n, x)))) }

Crossrefs

Cf. A062734.

Cf. A125206 (row-reversed version), A125207 (row sums).

Keyword

nonn,tabf

Author

Max Alekseyev, Nov 23 2006

Status

approved

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,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

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

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

Cf. A001187, A125205, A125206, A143543.

Keyword

nonn

Author

Max Alekseyev, Nov 23 2006

Status

approved

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.

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, 15, 105, 455, 1365, 3009, 5065, 6705, 7170, 6365, 4800, 3015, 1385, 420, 75, 6, 1, 21, 210, 1330, 5985, 20349, 54271, 116385, 204225, 297115, 362292, 373947, 329945

Offset

1,3

Comments

Row-reversed version of A125205, see A125205 for further details

Links

Table of n, a(n) for n=1..54.

Example

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

Crossrefs

Cf. A125205 (row-reversed version), A125207 (row sums).

Keyword

nonn,tabf

Author

Max Alekseyev, Nov 23 2006

Status

approved

A125208 Irregular triangle read by rows: T(n,k) (n>=1, 0<=k<=n(n-1)/2) is such that Sum_k T(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.

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, 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, 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

Offset

1,6

Links

Table of n, a(n) for n=1..83.

Formula

G.f.: Sum_{n,k} T(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!).

Sum_k T(n,k)*p^k = Sum_k A125205(n,k)*p^(n*(n-1)/2-k)*(1-p)^k

Example

Triangle begins:
  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;
   ...
Sum_k T(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.

Prog

(PARI) { H=sum(n=0, 6, x^n/p^(n*(n-1)/2)/n!); A=H*log(H); for(n=1, 6, print(Vecrev(p^(n*(n-1)/2)*n!*polcoeff(A, n, x)))) }

Crossrefs

Cf. A125205, A125206, A125209 (row-reversed version), A125210 (dual version).

Keyword

sign,tabf

Author

Max Alekseyev, Jan 09 2007

Status

approved

A125210 Irregular triangle read by rows: T(n,k) (n>=1, 0<=k<=n(n-1)/2) is such that Sum_k T(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.

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, -15, 0, 20, 45, -18, -330, 60, 2445, -6485, 8712, -7260, 3925, -1350, 270, -24, 7, -21, 0, 35, 105, 42, -980, -1950, 11760, 12355, -182721, 589281, -1128820, 1502550, -1471305

Offset

1,2

Links

Table of n, a(n) for n=1..56.

Formula

G.f.: Sum_{n,k} T(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!).

Sum_k T(n,k)*q^k = Sum_k A125205(n,k)*(1-q)^(n*(n-1)/2-k)*q^k

Sum_k T(n,k)*q^k = Sum_k A125206(n,k)*q^(n*(n-1)/2-k)*(1-q)^k

Example

Triangle begins:
  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;
...
Sum_k T(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.

Prog

(PARI) { H=sum(n=0, 6, x^n/(1-q)^(n*(n-1)/2)/n!); B=H*log(H); for(n=1, 6, print(Vecrev((1-q)^(n*(n-1)/2)*n!*polcoeff(B, n, x)))) }

Crossrefs

Cf. A125205, A125206, A127258 (row-reversed version), A125208 (dual version).

Keyword

sign,tabf

Author

Max Alekseyev, Jan 09 2007

Status

approved

A255886 Number of orderings of the edges of the labeled complete graph K_n such that the graph induced by the first k edges is connected for every k = 1,2,...,binomial(n,2).

1, 1, 6, 576, 2073600, 498161664000, 12385682950717440000, 45484508287062207627264000000, 33297304775599549535597153400913920000000, 6298496203530014357849150420174490961843322880000000000, 387030157006015555733158587399026951851936435957496524308480000000000000

Offset

1,3

Links

G. C. Greubel, Table of n, a(n) for n = 1..30

Mathoverflow, Probability of a graph procedure.

Formula

a(n) = binomial(n,2)! * 2^(n-2) / A000108(n-1), for n > 1.

a(n) ~ Pi * n^(n^2-n+5/2) / (2^(n*(n+1)/2) * exp(n^2/2 - 1/4 - 1/(12*n))). - Amiram Eldar, Nov 16 2025

Mathematica

Join[{1}, Table[Binomial[n, 2]!*2^(n-2)*n/Binomial[2*n-2, n-1], {n, 2, 20}]] (* G. C. Greubel, Aug 03 2018 *)

Prog

(PARI) {a(n) = if( n<2, n>0, binomial(n, 2)! * 2^(n-2) * n / binomial(2*n-2, n-1))}; /* Michael Somos, Jul 23 2015 */
(Magma) [1] cat [Factorial(Binomial(n, 2))*2^(n-2)*n/Binomial(2*n-2, n-1): n in [2..20]]; // G. C. Greubel, Aug 03 2018

Crossrefs

Cf. A000108, A125205, A125206, A125207, A125208, A125209.

Keyword

nonn,nice

Author

Max Alekseyev, Mar 09 2015

Status

approved