cp's OEIS Frontend

A129271 Number of labeled n-node connected graphs with at most one cycle.

%I A129271 #22 Feb 21 2024 22:48:49
%S A129271 1,1,1,4,31,347,4956,85102,1698712,38562309,980107840,27559801736,
%T A129271 849285938304,28459975589311,1030366840792576,40079074477640850,
%U A129271 1666985134587145216,73827334760713500233,3468746291121007607808,172335499299097826575564,9027150377126199463936000
%N A129271 Number of labeled n-node connected graphs with at most one cycle.
%C A129271 The majority of those graphs of order 4 are trees since we have 16 trees and only 9 unicycles. See example.
%C A129271 Also connected graphs covering n vertices with at most n edges. The unlabeled version is A005703. - _Gus Wiseman_, Feb 19 2024
%D A129271 J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.
%H A129271 Andrew Howroyd, <a href="/A129271/b129271.txt">Table of n, a(n) for n = 0..100</a>
%H A129271 Wikipedia, <a href="http://en.wikipedia.org/wiki/Pseudoforest">PseudoForest</a>.
%F A129271 a(0) = 1, for n >=1, a(n) = A000272(n) + A057500(n) = n^{n-2} + (n-1)(n-2)/2Sum_{r=1..n-2}( (n-3)!/(n-2-r)! )n^(n-2-r)
%F A129271 E.g.f.: log(1/(1-T(x)))/2 + T(x)/2 - 3*T(x)^2/4 + 1, where T(x) is the e.g.f. for A000169. - _Geoffrey Critzer_, Mar 23 2013
%F A129271 a(n) = ((n-1)*e^n*GAMMA(n-1,n)+n^(n-2)*(3-n))/2 for n>=1. - _Peter Luschny_, Jan 18 2016
%e A129271 a(4) = 16 + 3*3 = 31.
%e A129271 From _Gus Wiseman_, Feb 19 2024: (Start)
%e A129271 The a(0) = 1 through a(3) = 4 graph edge sets:
%e A129271   {}  .  {{1,2}}  {{1,2},{1,3}}
%e A129271                   {{1,2},{2,3}}
%e A129271                   {{1,3},{2,3}}
%e A129271                   {{1,2},{1,3},{2,3}}
%e A129271 (End)
%p A129271 a := n -> `if`(n=0,1,((n-1)*exp(n)*GAMMA(n-1,n)+n^(n-2)*(3-n))/2):
%p A129271 seq(simplify(a(n)),n=0..16); # _Peter Luschny_, Jan 18 2016
%t A129271 nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[Series[ Log[1/(1-t)]/2+t/2-3t^2/4+1,{x,0,nn}],x]  (* _Geoffrey Critzer_, Mar 23 2013 *)
%o A129271 (PARI) seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(log(1/(1-t))/2 + t/2 - 3*t^2/4 + 1))} \\ _Andrew Howroyd_, Nov 07 2019
%Y A129271 Cf. A129137, A000272.
%Y A129271 For any number of edges we have A001187, unlabeled A001349.
%Y A129271 The unlabeled version is A005703.
%Y A129271 The case of equality is A057500, covering A370317, cf. A370318.
%Y A129271 The non-connected non-covering version is A133686.
%Y A129271 The connected complement is A140638, unlabeled A140636, covering A367868.
%Y A129271 The non-connected covering version is A367869 or A369191.
%Y A129271 The version with loops is A369197, non-connected A369194.
%Y A129271 A006125 counts graphs, A000088 unlabeled.
%Y A129271 A006129 counts covering graphs, A002494 unlabeled.
%Y A129271 A062734 counts connected graphs by number of edges.
%Y A129271 Cf. A006649, A116508, A134964, A143543, A323818, A367862, A367863, A367867, A367916, A367917, A368951.
%K A129271 easy,nonn
%O A129271 0,4
%A A129271 _Washington Bomfim_, May 10 2008
%E A129271 Terms a(17) and beyond from _Andrew Howroyd_, Nov 07 2019