cp's OEIS Frontend

A061540 Number of connected labeled graphs with n nodes and n+1 edges.

%I A061540 #46 Jun 22 2025 10:16:08
%S A061540 0,0,0,6,205,5700,156555,4483360,136368414,4432075200,154060613850,
%T A061540 5720327205120,226378594906035,9523895202838016,424814409531910125,
%U A061540 20037831121798963200,996964614369038858060,52198565072252054814720,2869621989939313379211204,165302832533722012508160000
%N A061540 Number of connected labeled graphs with n nodes and n+1 edges.
%D A061540 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 407, Eq. (6.5).
%H A061540 Sergey Serebryakov, <a href="/A061540/b061540.txt">Table of n, a(n) for n = 1..40</a>
%H A061540 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 A061540 S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, <a href="https://dx.doi.org/10.1002/rsa.3240040303">The Birth of the Giant Component</a>, Random Structures and Algorithms Vol. 4 (1993), 233-358.
%H A061540 S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, <a href="https://arxiv.org/abs/math/9310236">The Birth of the Giant Component</a>, arXiv:math/9310236 [math.PR], 1993.
%H A061540 E. M. Wright, <a href="http://dx.doi.org/10.1002/jgt.3190010407">The Number of Connected Sparsely Edged Graphs</a>, Journal of Graph Theory Vol. 1 (1977), 317-330.
%F A061540 E.g.f.: W1(x) := T(x)^4/24 * (6-T(x))/(1-T(x))^3 where T(x) is the e.g.f. for rooted labeled trees (A000169), i.e. T(x) = -LambertW(-x) = x*exp(T(x)).
%F A061540 a(n) ~ 5*n^(n+1)/24 * (1 - 7/5*sqrt(2*Pi/n)). - _Vaclav Kotesovec_, Jul 09 2013
%p A061540 A001864 := proc(n)
%p A061540     add(binomial(n,s)*s^s*(n-s)^(n-s),s=1..n-1) ;
%p A061540 end proc:
%p A061540 A061540 := proc(n)
%p A061540     (n-1)*(5*n^2+3*n+2)*n^(n-2)-14*A001864(n) ;
%p A061540     %/24 ;
%p A061540 end proc: # _R. J. Mathar_, May 10 2016 see Chapter 6.3 in Bona's Handbook of Combinatorics
%t A061540 max = 18; t[x_] := -ProductLog[-x]; w1[x_] := t[x]^4/24*(6-t[x])/(1-t[x])^3; Drop[ CoefficientList[ Series[ w1[x], {x, 0, max}], x]*Range[0, max]!, 1] (* _Jean-François Alcover_, Apr 02 2012, after e.g.f. *)
%o A061540 (Python)
%o A061540 from math import comb
%o A061540 def A061540(n): return 0 if n<2 else ((n*(n*(5*n - 2) - 1) - 2)*n**(n-2)-14*((sum(comb(n,k)*(n-k)**(n-k)*k**k for k in range(1,(n+1>>1)))<<1) + (0 if n&1 else comb(n,m:=n>>1)*m**n)))//24 # _Chai Wah Wu_, Apr 26 2023
%Y A061540 A diagonal of A343088.
%Y A061540 Cf. A000169, A000272, A057500, A061541, A061542, A061543, A096117, A061544, A096150, A096224.
%K A061540 easy,nice,nonn
%O A061540 1,4
%A A061540 RAVELOMANANA Vlady (vlad(AT)lri.fr), May 16 2001