A125207 -id:A125207 - cp's OEIS frontend

A143543 Triangle read by rows: T(n,k) = number of labeled graphs on n nodes with k connected components, 1<=k<=n.

1, 1, 1, 4, 3, 1, 38, 19, 6, 1, 728, 230, 55, 10, 1, 26704, 5098, 825, 125, 15, 1, 1866256, 207536, 20818, 2275, 245, 21, 1, 251548592, 15891372, 925036, 64673, 5320, 434, 28, 1, 66296291072, 2343580752, 76321756, 3102204, 169113, 11088, 714, 36, 1

Offset: 1

Max Alekseyev, Aug 23 2008

The Bell transform of A001187(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 17 2016

			The triangle T(n,k) starts as:
n=1:     1;
n=2:     1,    1;
n=3:     4,    3,   1;
n=4:    38,   19,   6,   1;
n=5:   728,  230,  55,  10,  1;
n=6: 26704, 5098, 825, 125, 15, 1;
...

Alois P. Heinz, Rows n = 1..82, flattened (first 25 rows from Marko Riedel)
Marko Riedel, Maple implementation of memoized recurrence.
Marko Riedel et al., Proof of recurrence relation.

Cf. A001187 (first column), A006125 (row sums), A106240 (unlabeled variant).
Cf. A125207.
T(2n,n) gives A369827.

g:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-add(
      binomial(n, k)*2^((n-k)*(n-k-1)/2)*g(k)*k, k=1..n-1)/n)
    end:
b:= proc(n) option remember; `if`(n=0, 1, add(expand(
      b(n-j)*binomial(n-1, j-1)*g(j)*x), j=1..n))
    end:
T:= (n, k)-> coeff(b(n$2), x, k):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Feb 02 2024

a= Sum[2^Binomial[n,2] x^n/n!,{n,0,10}];
Rest[Transpose[Table[Range[0, 10]! CoefficientList[Series[Log[a]^n/n!, {x, 0, 10}], x], {n, 1, 10}]]] // Grid (* Geoffrey Critzer, Mar 15 2011 *)

T(n)={[Vecrev(p/y) | p <- Vec(serlaplace(exp(y*log(sum(k=0, n, 2^binomial(k,2)*x^k/k!, O(x*x^n))))))]}
{ foreach(T(8), row, print(row)) } \\ Andrew Howroyd, Jun 14 2025

# uses[bell_matrix from A264428, A001187]
# Adds a column 1,0,0,0, ... at the left side of the triangle.
bell_matrix(lambda n: A001187(n+1), 9) # Peter Luschny, Jan 17 2016

SUM[n,k=0..oo] T(n,k) * x^n * y^k / n! = exp( y*( F(x) - 1 ) ) = ( SUM[n=0..oo] 2^binomial(n, 2)*x^n/n! )^y, where F(x) is e.g.f. of A001187.
T(n,k) = Sum_{q=0..n-1} C(n-1, q) T(q, k-1) 2^C(n-q,2) - Sum_{q=0..n-2} C(n-1, q) T(q+1, k) 2^C(n-1-q, 2) where T(0,0) = 1 and T(0,k) = 0 and T(n,0) = 0. - Marko Riedel, Feb 04 2019
Sum_{k=1..n} k * T(n,k) = A125207(n) - Alois P. Heinz, Feb 02 2024

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

Original entry on oeis.org

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

Max Alekseyev, Nov 23 2006

			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.

Cf. A062734.

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

{ 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)))) }

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.

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.

Original entry on oeis.org

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

Max Alekseyev, Nov 23 2006

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

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

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

A223894 Triangular array read by rows: T(n,k) is the number of connected components with size k summed over all simple labeled graphs on n nodes; n>=1, 1<=k<=n.

Original entry on oeis.org

1, 2, 1, 6, 3, 4, 32, 12, 16, 38, 320, 80, 80, 190, 728, 6144, 960, 640, 1140, 4368, 26704, 229376, 21504, 8960, 10640, 30576, 186928, 1866256, 16777216, 917504, 229376, 170240, 326144, 1495424, 14930048, 251548592, 2415919104, 75497472, 11010048, 4902912, 5870592, 17945088, 134370432, 2263937328, 66296291072

Offset: 1

Geoffrey Critzer, Mar 28 2013

			Triangle T(n,k) begins:
       1;
       2,     1;
       6,     3,    4;
      32,    12,   16,    38;
     320,    80,   80,   190,   728;
    6144,   960,  640,  1140,  4368,  26704;
  229376, 21504, 8960, 10640, 30576, 186928, 1866256;
  ...

Alois P. Heinz, Rows n = 1..45, flattened

Cf. A001187, A006125, A123903 (column 1), A125207 (row sums), A182166 (column 2).

function b(n) // b = A001187
  if n eq 0 then return 1;
  else return 2^Binomial(n,2) - (&+[Binomial(n-1,j-1)*2^Binomial(n-j,2)*b(j): j in [0..n-1]]);
  end if; return b;
end function;
A223894:= func< n,k | Binomial(n,k)*2^Binomial(n-k,2)*b(k) >;
[A223894(n,k): k in [1..n], n in [1..12]]; // G. C. Greubel, Oct 03 2022

b:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
      add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*b(k), k=1..n-1)/n)
    end:
T:= (n, k)-> binomial(n, k)*b(k)*2^((n-k)*(n-k-1)/2):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Aug 26 2013

nn = 9; f[list_] := Select[list, # > 0 &]; g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn}]; a = Drop[Range[0, nn]! CoefficientList[Series[Log[g] + 1, {x, 0, nn}], x], 1]; Map[f, Drop[Transpose[Table[Range[0, nn]! CoefficientList[Series[a[[n]] x^n/n! g, {x, 0, nn}], x], {n, 1, nn}]], 1]] // Grid

@CachedFunction
def b(n): # b = A001187
    if (n==0): return 1
    else: return 2^binomial(n,2) - sum(binomial(n-1,j-1)*2^binomial(n-j,2)*b(j) for j in range(n))
def A223894(n,k): return binomial(n,k)*2^binomial(n-k,2)*b(k)
flatten([[A223894(n,k) for k in range(1,n+1)] for n in range(1,13)]) # G. C. Greubel, Oct 03 2022

E.g.f. for column k: A001187(n)*x^n/n!*A(x) where A(x) is the e.g.f. for A006125.
Sum_{k=0..n} T(n, k) = A125207(n).
T(n, 1) = A123903(n).
T(n, 2) = A182166(n).
T(n, n) = A001187(n). - G. C. Greubel, Oct 03 2022

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

Original entry on oeis.org

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

Offset: 1

Max Alekseyev, Mar 09 2015

G. C. Greubel, Table of n, a(n) for n = 1..30
Mathoverflow, Probability of a graph procedure.

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

[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

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

{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 */

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

A223889 The number of connected components of size > 1 over all simple labeled graphs on n nodes.

Original entry on oeis.org

0, 0, 1, 7, 66, 1078, 33812, 2124864, 269617328, 68809824944, 35197776962400, 36032789666289920, 73789365506598519808, 302234307608870314427904, 2475886847109430725963593728, 40564851077856428731075010538496

Offset: 0

Geoffrey Critzer, Mar 28 2013

nonn

Cf. A125207.

nn=15;g=Sum[2^Binomial[n,2]x^n/n!,{n,0,nn}];Range[0,nn]!CoefficientList[Series[(Log[g]-x)g,{x,0,nn}],x]

E.g.f.: (A(x) - x - 1)*B(x) where A(x) is the e.g.f. for A001187 and B(x) is the e.g.f. for A006125.

cp's OEIS Frontend

A143543 Triangle read by rows: T(n,k) = number of labeled graphs on n nodes with k connected components, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

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

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

A223894 Triangular array read by rows: T(n,k) is the number of connected components with size k summed over all simple labeled graphs on n nodes; n>=1, 1<=k<=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A223889 The number of connected components of size > 1 over all simple labeled graphs on n nodes.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula