login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A129271 Number of labeled n-node connected graphs with at most one cycle. 5
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.

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.

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, A005703, A000272, A057500.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 6 20:37 EST 2021. Contains 341850 sequences. (Running on oeis4.)