cp's OEIS Frontend

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

%I A057500 #114 Jun 22 2025 09:18:47
%S A057500 0,0,1,15,222,3660,68295,1436568,33779340,880107840,25201854045,
%T A057500 787368574080,26667815195274,973672928417280,38132879409281475,
%U A057500 1594927540549217280,70964911709203684440,3347306760024413356032,166855112441313024389625,8765006377126199463936000
%N A057500 Number of connected labeled graphs with n edges and n nodes.
%C A057500 Equivalently, number of connected unicyclic (i.e., containing one cycle) graphs on n labeled nodes. - _Vladeta Jovovic_, Oct 26 2004
%C A057500 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
%D A057500 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.
%D A057500 C. L. Mallows, Letter to N. J. A. Sloane, 1980.
%D A057500 R. J. Riddell, Contributions to the theory of condensation, Dissertation, Univ. of Michigan, Ann Arbor, 1951.
%H A057500 Alois P. Heinz, <a href="/A057500/b057500.txt">Table of n, a(n) for n = 1..300</a> (terms n = 1..50 from Washington G. Bomfim)
%H A057500 Federico Ardila, Matthias Beck, Jodi McWhirter, <a href="https://arxiv.org/abs/2004.02952">The Arithmetic of Coxeter Permutahedra</a>, arXiv:2004.02952 [math.CO], 2020.
%H A057500 Steven R. Finch, <a href="https://arxiv.org/abs/2408.12440">An exceptional convolutional recurrence</a>, arXiv:2408.12440 [math.CO], 22 Aug 2024.
%H A057500 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 133.
%H A057500 S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, <a href="http://arxiv.org/abs/math/9310236">The Birth of the Giant Component</a>, arXiv:math/9310236 [math.PR], 1993.
%H A057500 S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, <a href="http://dx.doi.org/10.1002/rsa.3240040303">The Birth of the Giant Component</a>, Random Structures and Algorithms Vol. 4 (1993), 233-358.
%H A057500 Younng-Jin Kim and Woong Kook, <a href="https://arxiv.org/abs/1812.04930">Winding number and Cutting number of Harmonic cycle</a>, arXiv:1812.04930 [math.CO], 2018.
%H A057500 C. L. Mallows, <a href="/A006543/a006543.pdf">Letter to N. J. A. Sloane, 1980</a>
%H A057500 Marko Riedel et al., <a href="https://math.stackexchange.com/questions/2992385/">Non-isomorphic, connected, unicyclic graphs</a>, Math Stackexchange, November 2018. (Proof of closed form by Cauchy Coefficient Formula / Lagrange Inversion.)
%H A057500 Chris Ying, <a href="https://arxiv.org/abs/1902.06192">Enumerating Unique Computational Graphs via an Iterative Graph Invariant</a>, arXiv:1902.06192 [cs.DM], 2019.
%F A057500 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
%F A057500 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.
%F A057500 E.g.f.: -1/2*log(1+LambertW(-x))+1/2*LambertW(-x)-1/4*LambertW(-x)^2. - _Vladeta Jovovic_, Jul 09 2001
%F A057500 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
%F A057500 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
%F A057500 a(n) = Sum_{k=0..C(n-1,2)} k*A052121(n,k). - _Alois P. Heinz_, Nov 29 2015
%F A057500 a(n) = (n^(n-2)*(1-3*n)+exp(n)*Gamma(n+1,n)/n)/2. - _Peter Luschny_, Jan 27 2016
%F A057500 a(n) = A062734(n,n+1) = A123527(n,n). - _Gus Wiseman_, Feb 19 2024
%e A057500 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.
%p A057500 egf:= -1/2*ln(1+LambertW(-x)) +1/2*LambertW(-x) -1/4*LambertW(-x)^2:
%p A057500 a:= n-> n!*coeff(series(egf, x, n+3), x, n):
%p A057500 seq(a(n), n=1..25);  # _Alois P. Heinz_, Mar 27 2013
%t A057500 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 *)
%t A057500 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_ *)
%t A057500 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]]]]]]]]];
%t A057500 Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[#]==n&&Length[csm[#]]<=1&]],{n,0,5}] (* _Gus Wiseman_, Feb 19 2024 *)
%o A057500 (Sage)
%o A057500 # Warning: Floating point calculation. Adjust precision as needed!
%o A057500 from mpmath import mp, chop, gammainc
%o A057500 mp.dps = 200; mp.pretty = True
%o A057500 for n in (1..100):
%o A057500     print(chop((n^(n-2)*(1-3*n)+exp(n)*gammainc(n+1, n)/n)/2))
%o A057500 # _Peter Luschny_, Jan 27 2016
%Y A057500 A diagonal of A343088.
%Y A057500 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.
%Y A057500 Cf. A001429 (unlabeled case), A052121.
%Y A057500 For any number of edges we have A001187, unlabeled A001349.
%Y A057500 This is the connected and covering case of A116508.
%Y A057500 For #edges <= #nodes we have A129271, covering A367869.
%Y A057500 For #edges > #nodes we have A140638, covering A367868.
%Y A057500 This is the connected case of A367862 and A367863, unlabeled A006649.
%Y A057500 The version with loops is A368951, unlabeled A368983.
%Y A057500 This is the covering case of A370317.
%Y A057500 Counting only covering vertices gives A370318.
%Y A057500 A006125 counts graphs, A000088 unlabeled.
%Y A057500 A006129 counts covering graphs, A002494 unlabeled.
%Y A057500 Cf. A062734, A098909, A123527, A129137, A133686, A143543, A323818, A367916, A367917, A369191, A369197.
%K A057500 easy,nonn
%O A057500 1,4
%A A057500 Qing-Hu Hou and David C. Torney (dct(AT)lanl.gov), Sep 01 2000
%E A057500 More terms from _Vladeta Jovovic_, Jul 09 2001