A001858 -id:A001858 - cp's OEIS frontend

A101313 Number of painted forests - exactly one of its trees is painted - on labeled vertex set [n].

1, 3, 12, 68, 525, 5262, 65674, 987408, 17426565, 353759300, 8127640224, 208600774032, 5917247520457, 183872561612040, 6212370268252950, 226762373954676608, 8893485959056048521, 372980176625914811568, 16656844860594186642100, 789196576594282265505600

Offset: 1

Joseph G. Moser (jmoser(AT)wcupa.edu), Jan 26 2005

nonn

			a(5) = 291 + (16*4*1)+(3*6*3)+(1*4*12)+(1*1*68) = 525.

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

B:= n-> exp(add(k^(k-2) *x^k/k!, k = 1..n )): b:= n-> coeff(series(B(n), x,n+1), x,n)*n!: a:= n-> add(binomial(n,k) *k^(k-2) *b(n-k), k=1..n): seq(a(n), n=1..25);  # Alois P. Heinz, Sep 10 2008

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Drop[Range[0,nn]!CoefficientList[Series[D[Exp[y(t-t^2/2)],y]/.y->1,{x,0,nn}],x],1]  (* Geoffrey Critzer, Nov 04 2012 *)

a(n) = f(n) + SUM{((n-i)^(n-i-2))*C((n-1), i)*a(i):i=1, 2, ..(n-1)}, where f(n)=number of forests on labeled vertex set [n], A001858.
Exponential convolution of A000272 and A001858: a(n) = Sum_{k=1..n} binomial(n, k)*k^(k-2)*A001858(n-k). E.g.f.: B(x)*exp(B(x)), where B(x) is e.g.f. for A000272. - Vladeta Jovovic, May 24 2005
a(n) = Sum_{m=1..n} A105599(n,m)*m. -  Geoffrey Critzer, Nov 04 2012

More terms from Alois P. Heinz, Sep 10 2008

A137352 Number of labeled graphs with at least one cycle in which every connected component has at most one cycle.

Original entry on oeis.org

1, 19, 317, 5592, 108839, 2356175, 56590729, 1499304898, 43532688017, 1376491137807, 47122376352941, 1737338689842008, 68657874376063231, 2896049933653455241, 129892644397271578571, 6173717934189145195530, 309998781844881257871161, 16399060640250318161199785

Offset: 3

Washington Bomfim, May 17 2008

nonn

			a(6)=5592 because we have several cases of one unicyclic graph or two. Namely,
-One triangle and a forest of order 3. The unique triangle can be relabeled in C(6,3)=20 ways, we have 20*7= 140 graphs.
-One unicyclic graph with 4 nodes and a forest of order 2. The 15 distinct unicyclic graphs of 4 nodes can be relabeled in C(6,4) ways, so we have 2*15C(6,2), or 450 graphs.
-One unicyclic graph with 5 nodes and an isolated vertex. There are 222 different graphs that can be relabeled in C(6,5) ways, so 6 * 222 = 1332 graphs.
-One unicyclic graph with 6 nodes, so 3660 graphs.
-Two triangles. The triangles can be relabeled in C(6,3)/2 ways. So 10 graphs.
The total of all cases is 5592.

Alois P. Heinz, Table of n, a(n) for n = 3..150
Wikipedia, Pseudoforest.

Cf. A140144, A001858, A057500.

cy:= proc(n) option remember; local t; binomial(n-1, 2) *add ((n-3)! /(n-2-t)! *n^(n-2-t), t=1..n-2) end: T:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n add (T(n,k), k=0..n): a2:= proc(n) option remember; if n=0 then 1 else add (binomial (n-1, j) *(j+1)^(j-1) *a2(n-1-j), j=0..n-1) fi end: a:= n-> a1(n)-a2(n): seq (a(n), n=3..25); # Alois P. Heinz, Sep 15 2008

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Drop[Range[0,nn]!CoefficientList[Series[ Exp[Log[1/(1-t)]/2+t/2-3t^2/4]-Exp[t-t^2/2],{x,0,nn}],x],3]  (* Geoffrey Critzer, Mar 23 2013 *)

a(n) = A133686(n) - A001858(n).

Corrected and extended by Alois P. Heinz, Sep 15 2008

A143900 Number of simple graphs on n labeled nodes containing at least one cycle subgraph, also row sums of A143899.

Original entry on oeis.org

0, 0, 0, 1, 26, 733, 29836, 2060191, 267873508, 68709450231, 35184166480296, 36028792251523289, 73786976171465003256, 302231454900131663566437, 2475880078570650265515241808, 40564819207303337099536803011071, 1329227995784915872766249150185503728

Offset: 0

Alois P. Heinz, Sep 04 2008

nonn

			a(3) = 1, because 1 simple graph on 3 nodes with 3 edges contains a cycle subgraph:
..1-2..
..|/...
..3....

Robert G. Wilson v, Table of n, a(n) for n = 0..82 (first 51 terms from Alois P. Heinz)

Row sums of A143899.

Cf. A006125, A001858, A007318.

graphs:= n-> 2^binomial(n,2): forests:= n-> add(add(binomial(m,j) *binomial(n-1, n-m-j) *n^(n-m-j) *(m+j)!/ (-2)^j/ m!, j=0..m), m=0..n): a:= n-> graphs(n) -forests(n): seq(a(n), n=0..18);

graphs[n_] := 2^Binomial[n, 2]; forests[n_] := Sum[Binomial[m, j]* Binomial[n-1, n-m-j]*n^(n-m-j)*(m+j)!/(-2)^j/m!, {m, 0, n}, {j, 0, m}]; a[0] = 0; a[n_] := graphs[n] - forests[n]; Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Feb 25 2017, after Alois P. Heinz *)

a(n) = A006125(n) - A001858(n).

a(n) = Sum_{k=3..C(n,2)} A143899(n,k).

A143911 Triangle read by rows: T(n,k) = number of forests on n labeled nodes, where k is the maximum of the number of edges per tree (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 9, 12, 16, 1, 25, 60, 80, 125, 1, 75, 330, 480, 750, 1296, 1, 231, 1680, 3920, 5250, 9072, 16807, 1, 763, 9408, 33600, 49000, 72576, 134456, 262144, 1, 2619, 56952, 254016, 598500, 762048, 1210104, 2359296, 4782969, 1, 9495, 348120

Offset: 1

Alois P. Heinz, Sep 04 2008

			T(4,1) = 9, because 9 forests on 4 labeled nodes have 1 as the maximum of the number of edges per tree:
  .1-2. .1.2. .1.2. .1.2. .1.2. .1.2. .1-2. .1.2. .1.2.
  ..... ...|. ..... .|... ..\.. ../.. ..... .|.|. ..X..
  .4.3. .4.3. .4-3. .4.3. .4.3. .4.3. .4-3. .4.3. .4.3.
Triangle begins:
  1;
  1,  1;
  1,  3,   3;
  1,  9,  12,  16;
  1, 25,  60,  80, 125;
  1, 75, 330, 480, 750, 1296;

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

Columns k=0-1 give: A000012, A001189.
Row sums give A001858.
Rightmost diagonal gives A000272.
Cf. A138464.

A:= (n,k)-> coeff(series(exp(add(j^(j-2) *x^j/j!, j=1..k)), x, n+1), x,n)*n!: T:= (n,k)-> A(n,k+1)-A(n,k): seq(seq(T(n,k), k=0..n-1), n=1..11);

A[n_, k_] := SeriesCoefficient[Exp[Sum[j^(j-2)*x^j/j!, {j, 1, k}]], {x, 0, n}]*n!; T[n_, k_] := A[n, k+1] - A[n, k];
Table[T[n, k], {n, 1, 11}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, May 31 2016, translated from Maple *)

See program.

A220690 Number of acyclic graphs on {1,2,...,n} such that the node with label 1 is in the same connected component (tree) as the node with label 2.

Original entry on oeis.org

0, 0, 1, 4, 24, 198, 2110, 27768, 436656, 8003950, 167779068, 3961727820, 104102329504, 3013887239454, 95338047836520, 3272043459321328, 121106541865151040, 4808924948167249302, 203931444227955436816, 9198925314402386788500, 439809753701222702598528

Offset: 0

Geoffrey Critzer, Apr 13 2013

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A221864.

b:= proc(n) option remember; `if`(n=0, 1,
      add(binomial(n-1, j) *(j+1)^(j-1) *b(n-1-j), j=0..n-1))
    end:
a:= n-> add(binomial(n-2, k)*(k+2)^k*b(n-k-2), k=0..n-2):
seq(a(n), n=0..20);  # Alois P. Heinz, Apr 13 2013

nn=20;u=Sum[n^(n-2)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[Integrate[Integrate[D[D[u,x],x]Exp[u],x],x],{x,0,nn}],x]

N = 66;  x = 'x + O('x^N);
U = sum(n=1,N,n^(n-2)*x^n/n!);
egf = intformal(intformal( deriv(deriv(U)) * exp(U) ));
gf = serlaplace(egf) + 'c0;
v = Vec(gf);  v[1]-='c0;  v
/* Joerg Arndt, Apr 13 2013 */

E.g.f.: Double integral of U''(x)*exp(U(x)) dx^2 where U(x) is the e.g.f. for A000272.

a(n) = Sum_{k=0..n-2} binomial(n-2,k)*(k+2)^k*A001858(n-k-2).

A323673 Expansion of e.g.f. log(1 - LambertW(-x)*(2 + LambertW(-x))/2).

Original entry on oeis.org

0, 1, 0, 2, 7, 69, 696, 9400, 148506, 2753793, 58255840, 1388008566, 36768832200, 1072407094693, 34151921130432, 1179292944433500, 43892264744070736, 1751768399754149025, 74633720517351765504, 3380997879130123703818, 162286529338732345488000, 8227876237310253918100581

Offset: 0

Ilya Gutkovskiy, Jan 23 2019

nonn

Cf. A000272, A001858, A001865, A133297.

seq(n!*coeff(series(log(1-LambertW(-x)*(2+LambertW(-x))/2),x=0,22),x,n),n=0..21); # Paolo P. Lava, Jan 28 2019

nmax = 21; CoefficientList[Series[Log[1 - LambertW[-x] (2 + LambertW[-x])/2], {x, 0, nmax}], x] Range[0, nmax]!
a[n_] := a[n] = n^(n - 2) - Sum[Binomial[n, k] (n - k)^(n - k - 2) k a[k], {k, 1, n - 1}]/n; a[0] = 0; Table[a[n], {n, 0, 21}]

E.g.f.: log(1 + Sum_{k>=1} k^(k-2)*x^k/k!).
a(0) = 0; a(n) = A000272(n) - (1/n)*Sum_{k=1..n-1} binomial(n,k)*A000272(n-k)*k*a(k).
a(n) ~ 2 * n^(n-2) / 3. - Vaclav Kotesovec, Jan 24 2019

A378324 Number of cyclic edge cuts in the complete graph K_n.

Original entry on oeis.org

0, 0, 0, 0, 0, 10, 840, 57428, 4323760, 428530774, 66698370662, 19304350714396, 11435576322977378, 13998454986272457974, 34730539006860778387488, 172307954877667746584363616, 1699711619922134215461075979752, 33269167602899548362529088074829390

Offset: 1

Eric W. Weisstein, Nov 23 2024

nonn

Eric W. Weisstein, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Complete Graph.
Eric Weisstein's World of Mathematics, Cyclic Edge Cut.

Cf. A000272, A001187, A006125, A001858.

With[{n = 20},
 B[x_] := 1 + Log[Sum[2^Binomial[k, 2] x^k/k!, {k, 0, n}]];
 T[x_] := 1 - LambertW[-x] - LambertW[-x]^2/2;
 Rest@CoefficientList[Series[(Exp[B[x] - T[x]] - (B[x] - T[x]) - 1) Exp[T[x] - 1], {x, 0, n}], x] Range[n]!
]

seq(n)={my(t=sum(k=1, n, k^(k-2)*x^k/k!, O(x*x^n)), c=log(sum(k=0, n, 2^binomial(k,2)*x^k/k!, O(x*x^n)))-t); Vec(serlaplace((exp(c)-1-c)*exp(t)), -n)} \\ Andrew Howroyd, Nov 26 2024

E.g.f.: (exp(B(x)-T(x))-(B(x)-T(x))-1)*exp(T(x)-1) where B(x) is the e.g.f. of A001187 and T(x) is the e.g.f. of A000272. - Andrew Howroyd, Nov 26 2024

a(n) = A006125(n) - A001858(n) - Sum_{k=1..n} binomial(n,k)*(A001187(k)-A000272(k))*A001858(n-k). - Andrew Howroyd, May 27 2025

a(8) onwards from Andrew Howroyd, Nov 26 2024

A216413 Number of forests of trees on n labeled nodes in which each tree has a distinct number of vertices.

Original entry on oeis.org

1, 1, 1, 6, 28, 235, 2466, 31864, 488328, 8901981, 183417490, 4300791946, 111621409956, 3214239089659, 100662133475372, 3440691046061130, 126342964714732576, 4999000389915029881, 210671936366279249610, 9474491260037610708598, 450638933972015166026220

Offset: 0

Geoffrey Critzer, Sep 07 2012

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..150

Cf. A001858.

a:= n-> n!*coeff(series(mul(1+k^(k-2)*x^k/k!, k=1..n), x, n+1), x, n):
seq(a(n), n=0..20);  # Alois P. Heinz, Sep 07 2012

nn=20;p=Product[1+n^(n-2)x^n/n!,{n,1,nn}];Range[0,nn]! CoefficientList[Series[p,{x,0,nn}],x]

E.g.f.: Product_{n>=1} (1 + n^(n-2)*x^n/n!).

A332237 E.g.f.: -log(1 + LambertW(-x) * (2 + LambertW(-x)) / 2).

Original entry on oeis.org

1, 2, 8, 49, 409, 4356, 56734, 877094, 15742521, 322454800, 7434673036, 190792267128, 5398552673617, 167087263076384, 5617979017621650, 203987454978218416, 7957053981454827601, 331920300203780633856, 14746208516909980554736, 695208730205550274544000

Offset: 1

Ilya Gutkovskiy, Feb 07 2020

nonn

Cf. A000272, A001858, A001865, A057817, A133297, A218688, A323673, A332236.

nmax = 20; CoefficientList[Series[-Log[1 + LambertW[-x] (2 + LambertW[-x])/2], {x, 0, nmax}], x] Range[0, nmax]! // Rest
a[n_] := a[n] = n^(n - 2) + (1/n) Sum[Binomial[n, k] (n - k)^(n - k - 2) k a[k], {k, 1, n - 1}]; Table[a[n], {n, 1, 20}]

E.g.f.: -log(1 - Sum_{k>=1} k^(k-2) * x^k / k!).
a(n) = n^(n-2) + (1/n) * Sum_{k=1..n-1} binomial(n,k) * (n-k)^(n-k-2) * k * a(k).
a(n) ~ 2 * n^(n-2). - Vaclav Kotesovec, Feb 16 2020

A372153 Irregular triangular array read by rows. T(n,k) is the number of simple labeled graphs on [n] with circuit rank equal to k, n >= 1, 0 <= k <= binomial(n-1,2).

Original entry on oeis.org

1, 2, 7, 1, 38, 19, 6, 1, 291, 317, 235, 125, 45, 10, 1, 2932, 5582, 7120, 6915, 5215, 3057, 1371, 455, 105, 15, 1, 36961, 108244, 207130, 306775, 368046, 364539, 300342, 205940, 116910, 54362, 20356, 5985, 1330, 210, 21, 1, 561948, 2331108, 6176387, 12709760

Offset: 1

Geoffrey Critzer, Apr 20 2024

The circuit rank r(G) of a simple graph G is the minimum number of edges that must be removed to break all of its cycles. r(G) = m - n + c where m,n,c are the number of edges, vertices, and connected components respectively of G.

Equivalently, T(n,k) is the number of simple labeled graphs on [n] such that the incidence matrix has nullity equal to k where the incidence matrix is viewed as a matrix with entries in the field GF(2).

			Triangle T(n,k) begins:
     1;
     2;
     7,    1;
    38,   19,    6,    1;
   291,  317,  235,  125,   45,   10,   1;
  2932, 5582, 7120, 6915, 5215, 3057, 1371, 455, 105, 15, 1;
  ...

R. Diestel, Graph Theory, Springer, 2017, pp. 23-27.

Andrew Howroyd, Table of n, a(n) for n = 1..1160 (rows 1..20)
Wikipedia, Circuit rank.
Wikipedia, Incidence matrix.

Cf. A001858, A057500.

Needs["Combinatorica`"]; Map[Select[#, # > 0 &] &, Transpose[ Table[ Table[ Total[ Map[#[[1]] &,Select[Table[{n!/GraphData[{n, i}, "AutomorphismCount"], GraphData[{n, i}, "CyclomaticNumber"]}, {i, 1, NumberOfGraphs[n]}], #[[2]] == k &]]], {n, 1, 7}], {k, 0, 15}]]] // Grid

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

T(n,0) = A001858(n).
E.g.f. for T(n,1): f(x)*g(x) where f(x) is the e.g.f. for A001858 and g(x) is the e.g.f. for A057500.
E.g.f.: exp(y*log(Sum_{k>=0} (1+y)^binomial(k,2)*(x/y)^k/k!)). - Andrew Howroyd, Jun 09 2025

More terms from Andrew Howroyd, Jun 09 2025

cp's OEIS Frontend

A101313 Number of painted forests - exactly one of its trees is painted - on labeled vertex set [n].

Views

Author

Keywords

Examples

Links

Programs

Maple

Mathematica

Formula

Extensions

A137352 Number of labeled graphs with at least one cycle in which every connected component has at most one cycle.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A143900 Number of simple graphs on n labeled nodes containing at least one cycle subgraph, also row sums of A143899.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A143911 Triangle read by rows: T(n,k) = number of forests on n labeled nodes, where k is the maximum of the number of edges per tree (n>=1, 0<=k<=n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A220690 Number of acyclic graphs on {1,2,...,n} such that the node with label 1 is in the same connected component (tree) as the node with label 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A323673 Expansion of e.g.f. log(1 - LambertW(-x)*(2 + LambertW(-x))/2).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

A378324 Number of cyclic edge cuts in the complete graph K_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A216413 Number of forests of trees on n labeled nodes in which each tree has a distinct number of vertices.

Views

Author