A370317 -id:A370317 - cp's OEIS frontend

A057500 Number of connected labeled graphs with n edges and n nodes.

0, 0, 1, 15, 222, 3660, 68295, 1436568, 33779340, 880107840, 25201854045, 787368574080, 26667815195274, 973672928417280, 38132879409281475, 1594927540549217280, 70964911709203684440, 3347306760024413356032, 166855112441313024389625, 8765006377126199463936000

Offset: 1

Qing-Hu Hou and David C. Torney (dct(AT)lanl.gov), Sep 01 2000

Equivalently, number of connected unicyclic (i.e., containing one cycle) graphs on n labeled nodes. - Vladeta Jovovic, Oct 26 2004

a(n) is the number of trees on vertex set [n] = {1,2,...,n} rooted at 1 with one marked inversion (an inversion is a pair (i,j) with i > j and j a descendant of i in the tree). Here is a bijection from the title graphs (on [n]) to these marked trees. A title graph has exactly one cycle. There is a unique path from vertex 1 to this cycle, first meeting it at k, say (k may equal 1). Let i and j be the two neighbors of k in the cycle, with i the larger of the two. Delete the edge k<->j thereby forming a tree (in which j is a descendant of i) and take (i,j) as the marked inversion. To reverse this map, create a cycle by joining the smaller element of the marked inversion to the parent of the larger element. a(n) = binomial(n-1,2)*A129137(n). This is because, on the above marked trees, the marked inversion is uniformly distributed over 2-element subsets of {2,3,...,n} and so a(n)/binomial(n-1,2) is the number of trees on [n] (rooted at 1) for which (3,2) is an inversion. - David Callan, Mar 30 2007

			E.g., a(4)=15 because there are three different (labeled) 4-cycles and 12 different labeled graphs with a 3-cycle and an attached, external vertex.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.
C. L. Mallows, Letter to N. J. A. Sloane, 1980.
R. J. Riddell, Contributions to the theory of condensation, Dissertation, Univ. of Michigan, Ann Arbor, 1951.

Alois P. Heinz, Table of n, a(n) for n = 1..300 (terms n = 1..50 from Washington G. Bomfim)
Federico Ardila, Matthias Beck, Jodi McWhirter, The Arithmetic of Coxeter Permutahedra, arXiv:2004.02952 [math.CO], 2020.
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 133.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, arXiv:math/9310236 [math.PR], 1993.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
Younng-Jin Kim and Woong Kook, Winding number and Cutting number of Harmonic cycle, arXiv:1812.04930 [math.CO], 2018.
C. L. Mallows, Letter to N. J. A. Sloane, 1980
Marko Riedel et al., Non-isomorphic, connected, unicyclic graphs, Math Stackexchange, November 2018. (Proof of closed form by Cauchy Coefficient Formula / Lagrange Inversion.)
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.

A diagonal of A343088.
Cf. A000272 = labeled trees on n nodes; connected labeled graphs with n nodes and n+k edges for k=0..8: this sequence, A061540, A061541, A061542, A061543, A096117, A061544, A096150, A096224.
Cf. A001429 (unlabeled case), A052121.
For any number of edges we have A001187, unlabeled A001349.
This is the connected and covering case of A116508.
For #edges <= #nodes we have A129271, covering A367869.
For #edges > #nodes we have A140638, covering A367868.
This is the connected case of A367862 and A367863, unlabeled A006649.
The version with loops is A368951, unlabeled A368983.
This is the covering case of A370317.
Counting only covering vertices gives A370318.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
Cf. A062734, A098909, A123527, A129137, A133686, A143543, A323818, A367916, A367917, A369191, A369197.

egf:= -1/2*ln(1+LambertW(-x)) +1/2*LambertW(-x) -1/4*LambertW(-x)^2:
a:= n-> n!*coeff(series(egf, x, n+3), x, n):
seq(a(n), n=1..25);  # Alois P. Heinz, Mar 27 2013

nn=20; t=Sum[n^(n-1) x^n/n!, {n,1,nn}]; Drop[Range[0,nn]! CoefficientList[Series[Log[1/(1-t)]/2-t^2/4-t/2, {x,0,nn}], x], 1]  (* Geoffrey Critzer, Oct 07 2012 *)
a[n_] := (n-1)!*n^n/2*Sum[1/(n^k*(n-k)!), {k, 3, n}]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jan 15 2014, after Vladeta Jovovic *)
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[#]==n&&Length[csm[#]]<=1&]],{n,0,5}] (* Gus Wiseman, Feb 19 2024 *)

# Warning: Floating point calculation. Adjust precision as needed!
from mpmath import mp, chop, gammainc
mp.dps = 200; mp.pretty = True
for n in (1..100):
    print(chop((n^(n-2)*(1-3*n)+exp(n)*gammainc(n+1, n)/n)/2))
# Peter Luschny, Jan 27 2016

The number of labeled connected graphs with n nodes and m edges is Sum_{k=1..n} (-1)^(k+1)/k*Sum_{n_1+n_2+..n_k=n, n_i>0} n!/(Product_{i=1..k} (n_i)!)* binomial(s, m), s=Sum_{i..k} binomial(n_i, 2). - Vladeta Jovovic, Apr 10 2001
E.g.f.: (1/2) Sum_{k>=3} T(x)^k/k, with T(x) = Sum_{n>=1} n^(n-1)/n! x^n. R. J. Riddell's thesis contains a closed-form expression for the number of connected graphs with m nodes and n edges. The present series applies to the special case m=n.
E.g.f.: -1/2*log(1+LambertW(-x))+1/2*LambertW(-x)-1/4*LambertW(-x)^2. - Vladeta Jovovic, Jul 09 2001
Asymptotic expansion (with xi=sqrt(2*Pi)): n^(n-1/2)*[xi/4-7/6*n^(-1/2)+xi/48* n^(-1)+131/270*n^(-3/2)+xi/1152*n^(-2)+4/2835*n^(-5/2)+O(n^(-3))]. - Keith Briggs, Aug 16 2004
Row sums of A098909: a(n) = (n-1)!*n^n/2*Sum_{k=3..n} 1/(n^k*(n-k)!). - Vladeta Jovovic, Oct 26 2004
a(n) = Sum_{k=0..C(n-1,2)} k*A052121(n,k). - Alois P. Heinz, Nov 29 2015
a(n) = (n^(n-2)*(1-3*n)+exp(n)*Gamma(n+1,n)/n)/2. - Peter Luschny, Jan 27 2016
a(n) = A062734(n,n+1) = A123527(n,n). - Gus Wiseman, Feb 19 2024

More terms from Vladeta Jovovic, Jul 09 2001

A129271 Number of labeled n-node connected graphs with at most one cycle.

Original entry on oeis.org

1, 1, 1, 4, 31, 347, 4956, 85102, 1698712, 38562309, 980107840, 27559801736, 849285938304, 28459975589311, 1030366840792576, 40079074477640850, 1666985134587145216, 73827334760713500233, 3468746291121007607808, 172335499299097826575564, 9027150377126199463936000

Offset: 0

Washington Bomfim, May 10 2008

The majority of those graphs of order 4 are trees since we have 16 trees and only 9 unicycles. See example.

Also connected graphs covering n vertices with at most n edges. The unlabeled version is A005703. - Gus Wiseman, Feb 19 2024

			a(4) = 16 + 3*3 = 31.
From _Gus Wiseman_, Feb 19 2024: (Start)
The a(0) = 1 through a(3) = 4 graph edge sets:
  {}  .  {{1,2}}  {{1,2},{1,3}}
                  {{1,2},{2,3}}
                  {{1,3},{2,3}}
                  {{1,2},{1,3},{2,3}}
(End)

J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.

Andrew Howroyd, Table of n, a(n) for n = 0..100
Wikipedia, PseudoForest.

Cf. A129137, A000272.
For any number of edges we have A001187, unlabeled A001349.
The unlabeled version is A005703.
The case of equality is A057500, covering A370317, cf. A370318.
The non-connected non-covering version is A133686.
The connected complement is A140638, unlabeled A140636, covering A367868.
The non-connected covering version is A367869 or A369191.
The version with loops is A369197, non-connected A369194.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A062734 counts connected graphs by number of edges.
Cf. A006649, A116508, A134964, A143543, A323818, A367862, A367863, A367867, A367916, A367917, A368951.

a := n -> `if`(n=0,1,((n-1)*exp(n)*GAMMA(n-1,n)+n^(n-2)*(3-n))/2):
seq(simplify(a(n)),n=0..16); # Peter Luschny, Jan 18 2016

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

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(log(1/(1-t))/2 + t/2 - 3*t^2/4 + 1))} \\ Andrew Howroyd, Nov 07 2019

a(0) = 1, for n >=1, a(n) = A000272(n) + A057500(n) = n^{n-2} + (n-1)(n-2)/2Sum_{r=1..n-2}( (n-3)!/(n-2-r)! )n^(n-2-r)
E.g.f.: log(1/(1-T(x)))/2 + T(x)/2 - 3*T(x)^2/4 + 1, where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Mar 23 2013
a(n) = ((n-1)*e^n*GAMMA(n-1,n)+n^(n-2)*(3-n))/2 for n>=1. - Peter Luschny, Jan 18 2016

Terms a(17) and beyond from Andrew Howroyd, Nov 07 2019

A005703 Number of n-node connected graphs with at most one cycle.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 19, 44, 112, 287, 763, 2041, 5577, 15300, 42419, 118122, 330785, 929469, 2621272, 7411706, 21010378, 59682057, 169859257, 484234165, 1382567947, 3952860475, 11315775161, 32430737380, 93044797486, 267211342954, 768096496093, 2209772802169

Offset: 0

N. J. A. Sloane, R. K. Guy

a(n) is the number of pseudotrees on n nodes. - Eric W. Weisstein, Jun 11 2012

Also unlabeled connected graphs covering n vertices with at most n edges. For this definition we have a(1) = 0 and possibly a(0) = 0. - Gus Wiseman, Feb 20 2024

			From _Gus Wiseman_, Feb 20 2024: (Start)
Representatives of the a(0) = 1 through a(5) = 8 graphs:
  {}  .  {12}  {12,13}     {12,13,14}     {12,13,14,15}
               {12,13,23}  {12,13,24}     {12,13,14,25}
                           {12,13,14,23}  {12,13,24,35}
                           {12,13,24,34}  {12,13,14,15,23}
                                          {12,13,14,23,25}
                                          {12,13,14,23,45}
                                          {12,13,14,25,35}
                                          {12,13,24,35,45}
(End)

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Washington Bomfim, Table of n, a(n) for n = 0..500
R. K. Guy, Letters to N. J. A. Sloane and J. W. Moon, 1988
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
Eric Weisstein's World of Mathematics, Pseudotree
Wikipedia, Pseudoforest

Cf. A000055, A000081, A001429 (labeled A057500), A134964 (number of pseudoforests, labeled A133686).
The labeled version is A129271.
The connected complement is A140636, labeled A140638.
Non-connected: A368834 (labeled A367869) or A370316 (labeled A369191).
A001187 counts connected graphs, unlabeled A001349.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A062734 counts connected graphs by number of edges.
Cf. A000272, A006649, A116508, A140637, A143543, A367862, A367863, A368951, A369197, A370317, A370318.

Needs["Combinatorica`"]; nn = 20; t[x_] := Sum[a[n] x^n, {n, 1, nn}];
a[0] = 0;
b = Drop[Flatten[
    sol = SolveAlways[
      0 == Series[
        t[x] - x Product[1/(1 - x^i)^a[i], {i, 1, nn}], {x, 0, nn}],
      x]; Table[a[n], {n, 0, nn}] /. sol], 1];
r[x_] := Sum[b[[n]] x^n, {n, 1, nn}]; c =
Drop[Table[
    CoefficientList[
     Series[CycleIndex[DihedralGroup[n], s] /.
       Table[s[i] -> r[x^i], {i, 1, n}], {x, 0, nn}], x], {n, 3,
     nn}] // Total, 1];
d[x_] := Sum[c[[n]] x^n, {n, 1, nn}]; CoefficientList[
Series[r[x] - (r[x]^2 - r[x^2])/2 + d[x] + 1, {x, 0, nn}], x] (* Geoffrey Critzer, Nov 17 2014 *)

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(t=TreeGf(n)); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); Vec(1 + g(1) + (g(2) - g(1)^2)/2 + sum(k=3, n, sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/k + if(k%2, g(1)*g(2)^(k\2), (g(1)^2+g(2))*g(2)^(k/2-1)/2))/2)}; \\ Andrew Howroyd and Washington Bomfim, May 15 2021

a(n) = A000055(n) + A001429(n).

More terms from Vladeta Jovovic, Apr 19 2000 and from Michael Somos, Apr 26 2000

a(27) corrected and a(28) and a(29) computed by Washington Bomfim, May 14 2008

A140638 Number of connected graphs on n labeled nodes that contain at least two cycles.

Original entry on oeis.org

0, 0, 0, 7, 381, 21748, 1781154, 249849880, 66257728763, 34495508486976, 35641629989151608, 73354595357480683904, 301272202621204113362497, 2471648811029413368450098688, 40527680937730440155535277704046, 1328578958335783199341353852258282496

Offset: 1

Washington Bomfim, May 21 2008

nonn

These are the connected graphs that are neither trees nor unicyclic.

Also connected non-choosable graphs covering n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The unlabeled version is A140636. The complement is counted by A129271. - Gus Wiseman, Feb 20 2024

J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.

Andrew Howroyd, Table of n, a(n) for n = 1..50

The unlabeled version is A140636.
Cf. A000272 (trees), A001187 (connected graphs), A057500 (connected unicyclic graphs).
The complement is counted by A129271, unlabeled A005703.
The non-connected complement is A133686, covering A367869.
The non-connected version is A367867, unlabeled A140637.
The non-connected covering version is A367868.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A143543 counts simple labeled graphs by number of connected components.
Cf. A001349, A116508, A355740, A367769, A367863, A367901, A367903, A370317.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]<=1&&Select[Tuples[#],UnsameQ@@#&]=={}&]],{n,0,5}] (* Gus Wiseman, Feb 19 2024 *)

seq(n)={my(A=O(x*x^n), t=-lambertw(-x + A)); Vec(serlaplace( log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, A)) - log(1/(1-t))/2 - t/2 + 3*t^2/4), -n)} \\ Andrew Howroyd, Jan 15 2022

a(n) = A001187(n) - A129271(n).

a(n) = A001187(n) - A000272(n) - A057500(n).

Definition clarified by Andrew Howroyd, Jan 15 2022

A368951 Number of connected labeled graphs with n edges and n vertices and with loops allowed.

Original entry on oeis.org

1, 1, 2, 10, 79, 847, 11436, 185944, 3533720, 76826061, 1880107840, 51139278646, 1530376944768, 49965900317755, 1767387701671424, 67325805434672100, 2747849045156064256, 119626103584870552921, 5533218319763109888000, 270982462739224265922466

Offset: 0

Andrew Howroyd, Jan 10 2024

nonn

Exponential transform appears to be A333331. - Gus Wiseman, Feb 12 2024

			From _Gus Wiseman_, Feb 12 2024: (Start)
The a(0) = 1 through a(3) = 10 loop-graphs:
  {}  {11}  {11,12}  {11,12,13}
            {22,12}  {11,12,23}
                     {11,13,23}
                     {22,12,13}
                     {22,12,23}
                     {22,13,23}
                     {33,12,13}
                     {33,12,23}
                     {33,13,23}
                     {12,13,23}
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Graph Loop.

Cf. A000169, A333331, A063170, A053506.
This is the connected covering case of A014068.
The case without loops is A057500, covering case of A370317.
Allowing any number of edges gives A062740, connected case of A322661.
This is the connected case of A368597.
The unlabeled version is A368983, connected case of A368984.
For at most n edges we have A369197.
A000085 counts set partitions into singletons or pairs.
A006129 counts covering graphs, connected A001187.
Cf. A000272, A000666, A054780, A116508, A136556, A367863, A368600.

egf:= (L-> 1-L/2-log(1+L)/2-L^2/4)(LambertW(-x)):
a:= n-> n!*coeff(series(egf, x, n+1), x, n):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 10 2024

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(-log(1-t)/2 + t/2 - t^2/4 + 1))}

a(n) = A000169(n) + A057500(n) for n > 0.
E.g.f.: 1 - log(1-T(x))/2 + T(x)/2 - T(x)^2/4 where T(x) = -LambertW(-x) is the e.g.f. of A000169.
From Peter Luschny, Jan 10 2024: (Start)
a(n) = (exp(n)*Gamma(n + 1, n) - (n - 1)*n^(n - 1))/(2*n) for n > 0.
a(n) = (1/2)*(A063170(n)/n - A053506(n)) for n > 0.  (End)

A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

Original entry on oeis.org

0, 0, 0, 1, 19, 307, 5237, 99137, 2098946, 49504458, 1291570014, 37002273654, 1156078150969, 39147186978685, 1428799530304243, 55933568895261791, 2338378885159906196, 103995520598384132516, 4903038902046860966220, 244294315694676224001852, 12827355456239840407125363

Offset: 0

Gus Wiseman, Feb 18 2024

nonn

The case of an empty edge set is excluded.

Andrew Howroyd, Table of n, a(n) for n = 0..100

The covering case is A057500, which is also the covering case of A370317.
This is the connected case of A367862, covering A367863.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A062734 counts connected graphs by edge count.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A001429, A006649, A061540, A116508, A323818, A367916, A368951, A369197.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}], Length[Intersection@@s[[#]]]>0&]},If[c=={},s, csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Length[#]==Length[Union@@#] && Length[csm[#]]==1&]],{n,0,5}]

\\ Compare A370317; use A057500 for efficiency.
a(n)=n!*polcoef(polcoef(exp(x*y + O(x*x^n))*(-x+log(sum(k=0, n, (1 + y + O(y*y^n))^binomial(k, 2)*x^k/k!, O(x*x^n)))), n), n) \\ Andrew Howroyd, Feb 19 2024

Binomial transform of A057500 (if the null graph is not connected).

a(n) = n!*[x^n][y^n] exp(x*y)*(-x + log(Sum_{k>=0} (1 + y)^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Feb 19 2024

cp's OEIS Frontend

A057500 Number of connected labeled graphs with n edges and n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

A129271 Number of labeled n-node connected graphs with at most one cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A005703 Number of n-node connected graphs with at most one cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A140638 Number of connected graphs on n labeled nodes that contain at least two cycles.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A368951 Number of connected labeled graphs with n edges and n vertices and with loops allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI