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,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.

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.

Sequence in context: A122400 A107725 A145160 * A136728 A321031 A102757

Adjacent sequences: A129268 A129269 A129270 * A129272 A129273 A129274

Keyword

easy,nonn

Author

Washington Bomfim, May 10 2008

Extensions

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

Status

approved