A129271 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

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

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.

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

EXAMPLE

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)

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

PROG

(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

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.