%I #106 Aug 23 2024 03:14:20
%S 0,0,1,15,222,3660,68295,1436568,33779340,880107840,25201854045,
%T 787368574080,26667815195274,973672928417280,38132879409281475,
%U 1594927540549217280,70964911709203684440,3347306760024413356032,166855112441313024389625,8765006377126199463936000
%N Number of connected labeled graphs with n edges and n nodes.
%C Equivalently, number of connected unicyclic (i.e., containing one cycle) graphs on n labeled nodes. - _Vladeta Jovovic_, Oct 26 2004
%C 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 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.
%D C. L. Mallows, Letter to N. J. A. Sloane, 1980.
%D R. J. Riddell, Contributions to the theory of condensation, Dissertation, Univ. of Michigan, Ann Arbor, 1951.
%H 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 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 S. R. Finch, <a href="https://arxiv.org/abs/2408.12440">An exceptional convolutional recurrence</a>, arXiv:2408.12440 [math.CO], 22 Aug 2024.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 133.
%H S. Janson, D. E. Knuth, T. Luczak 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 S. Janson, D. E. Knuth, T. Luczak 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 Younng-Jin Kim, 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 C. L. Mallows, <a href="/A006543/a006543.pdf">Letter to N. J. A. Sloane, 1980</a>
%H 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 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 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 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 E.g.f.: -1/2*log(1+LambertW(-x))+1/2*LambertW(-x)-1/4*LambertW(-x)^2. - _Vladeta Jovovic_, Jul 09 2001
%F 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 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 a(n) = Sum_{k=0..C(n-1,2)} k*A052121(n,k). - _Alois P. Heinz_, Nov 29 2015
%F a(n) = (n^(n-2)*(1-3*n)+exp(n)*Gamma(n+1,n)/n)/2. - _Peter Luschny_, Jan 27 2016
%F a(n) = A062734(n,n+1) = A123527(n,n). - _Gus Wiseman_, Feb 19 2024
%e 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 egf:= -1/2*ln(1+LambertW(-x)) +1/2*LambertW(-x) -1/4*LambertW(-x)^2:
%p a:= n-> n!*coeff(series(egf, x, n+3), x, n):
%p seq(a(n), n=1..25); # _Alois P. Heinz_, Mar 27 2013
%t 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 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 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 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 (Sage)
%o # Warning: Floating point calculation. Adjust precision as needed!
%o from mpmath import mp, chop, gammainc
%o mp.dps = 200; mp.pretty = True
%o for n in (1..100):
%o print(chop((n^(n-2)*(1-3*n)+exp(n)*gammainc(n+1, n)/n)/2))
%o # _Peter Luschny_, Jan 27 2016
%Y A diagonal of A343088.
%Y 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 Cf. A001429 (unlabeled case), A052121.
%Y For any number of edges we have A001187, unlabeled A001349.
%Y This is the connected and covering case of A116508.
%Y For #edges <= #nodes we have A129271, covering A367869.
%Y For #edges > #nodes we have A140638, covering A367868.
%Y This is the connected case of A367862 and A367863, unlabeled A006649.
%Y The version with loops is A368951, unlabeled A368983.
%Y This is the covering case of A370317.
%Y Counting only covering vertices gives A370318.
%Y A006125 counts graphs, A000088 unlabeled.
%Y A006129 counts covering graphs, A002494 unlabeled.
%Y Cf. A062734, A133686, A143543, A323818, A367916, A367917, A369191, A369197.
%K easy,nonn
%O 1,4
%A Qing-Hu Hou and David C. Torney (dct(AT)lanl.gov), Sep 01 2000
%E More terms from _Vladeta Jovovic_, Jul 09 2001