This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A057500 Number of connected labeled graphs with n edges and n nodes. 26
0, 0, 1, 15, 222, 3660, 68295, 1436568, 33779340, 880107840, 25201854045, 787368574080, 26667815195274, 973672928417280, 38132879409281475, 1594927540549217280, 70964911709203684440, 3347306760024413356032, 166855112441313024389625, 8765006377126199463936000 (list; graph; refs; listen; history; text; internal format)



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 = 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) = binom(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)/binom(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


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.


Washington G. Bomfim and Alois P. Heinz, Table of n, a(n) for n = 1..300 (terms n = 1..50 from Washington G. Bomfim)

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 133.

S. Janson, D. E. Knuth, T. Luczak and B. Pittel, The Birth of the Giant Component, arXiv:math/9310236 [math.PR], 1993.

S. Janson, D. E. Knuth, T. Luczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.

Younng-Jin Kim, 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.


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


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.


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



# Warning: Floating point calculation. Adjust precision as needed!

from mpmath import *

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


Cf. A000272 = labeled trees on n nodes; connected labeled graphs with n nodes and n+k edges for k=0..8: A057500 A061540 A061541 A061542 A061543 A096117 A061544 A096150 and A096224.

Cf. A001429 (unlabeled case), A052121.

Sequence in context: A027843 A027840 A279530 * A137916 A218696 A297669

Adjacent sequences:  A057497 A057498 A057499 * A057501 A057502 A057503




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


More terms from Vladeta Jovovic, Jul 09 2001



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 18:19 EDT 2019. Contains 328269 sequences. (Running on oeis4.)