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

1, 1, 1, 4, 31, 347, 4956, 85102, 1698712, 38562309, 980107840, 27559801736, 849285938304, 28459975589311, 1030366840792576, 40079074477640850, 1666985134587145216, 73827334760713500233, 3468746291121007607808, 172335499299097826575564, 9027150377126199463936000

Offset: 0

Author

Washington Bomfim, May 10 2008

Keywords

• easy
• nonn

Comments

The majority of those graphs of order 4 are trees since we have 16 trees and only 9 unicycles. See example.

Also connected graphs covering n vertices with at most n edges. The unlabeled version is A005703. - Gus Wiseman, Feb 19 2024

Examples

			a(4) = 16 + 3*3 = 31.
From _Gus Wiseman_, Feb 19 2024: (Start)
The a(0) = 1 through a(3) = 4 graph edge sets:
  {}  .  {{1,2}}  {{1,2},{1,3}}
                  {{1,2},{2,3}}
                  {{1,3},{2,3}}
                  {{1,2},{1,3},{2,3}}
(End)
		

References

• J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..100
• Wikipedia, PseudoForest.

Crossrefs

Cf. A129137, A000272.

For any number of edges we have A001187, unlabeled A001349.

The unlabeled version is A005703.

The case of equality is A057500, covering A370317, cf. A370318.

The non-connected non-covering version is A133686.

The connected complement is A140638, unlabeled A140636, covering A367868.

The non-connected covering version is A367869 or A369191.

The version with loops is A369197, non-connected A369194.

A006125 counts graphs, A000088 unlabeled.

A006129 counts covering graphs, A002494 unlabeled.

A062734 counts connected graphs by number of edges.

Cf. A006649, A116508, A134964, A143543, A323818, A367862, A367863, A367867, A367916, A367917, A368951.

Programs

Maple

a := n -> `if`(n=0,1,((n-1)*exp(n)*GAMMA(n-1,n)+n^(n-2)*(3-n))/2):
seq(simplify(a(n)),n=0..16); # Peter Luschny, Jan 18 2016

Mathematica

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 *)

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

Formula

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)

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

a(n) = ((n-1)*e^n*GAMMA(n-1,n)+n^(n-2)*(3-n))/2 for n>=1. - Peter Luschny, Jan 18 2016

Extensions

Terms a(17) and beyond from Andrew Howroyd, Nov 07 2019