login
Number of connected labeled graphs with n edges and n nodes.
67

%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