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
KEYWORD
easy,nonn
AUTHOR
Washington Bomfim, May 10 2008
EXTENSIONS
Terms a(17) and beyond from Andrew Howroyd, Nov 07 2019
STATUS
approved