login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003692 Number of trees on n labeled vertices with degree at most 3. 3
1, 1, 3, 16, 120, 1170, 14070, 201600, 3356640, 63730800, 1359666000, 32212857600, 839350512000, 23860289653200, 734964075846000, 24388126963200000, 867393811956672000, 32919980214689568000 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
LINKS
Mathematics Stack Exchange, Marko Riedel et al., Number of labeled trees
FORMULA
E.g.f.: ((1-x)*(2-x-x^2) - (2-x+x^2)*sqrt(1-2*x-x^2)) / (3*x^3). [edited by Franklin T. Adams-Watters, May 24 2010]
The number of labeled trees with d[i] vertices of degree i for i=1,2,3 is (n-2)! * n! / (2^d[3] * d[3]! * d[2]! * d[1]!). Now sum over d[1]+d[2]+d[3]=n, d[1]+2*d[2]+3*d[3] = 2n-2. - Brendan McKay, May 24 2010; corrected Sep 17 2012.
From Georgi Guninski, May 24 2010: (Start)
The following relation seems to hold up to 3000 terms:
a(n+1) = (-a(n-1)*a(n) - (-3*a(n)^2 + (2/3)*a(n-2)*a(n)*n+ (-4/3)*a(n-1) *a(n)*n+ (-4/3)*a(n)^2*n+ (-1/3)*a(n-2)*a(n)*n^2+ (-2/3)*a(n-1)*a(n)* n^2)) / (a(n-1)+ (-1/3)*a(n) -2*a(n-2)*n+ 2*a(n-1)*n+a(n-2)*n^2). (End)
Recurrence: (n+3)*a(n) = (n+1)*(2*n+1)*a(n-1) + (n-2)*n*(n+1)*a(n-2). - Vaclav Kotesovec, Oct 07 2013
a(n) ~ (2-sqrt(2))^(3/2) * (1+sqrt(2))^(n+3) * n^(n-1) / exp(n). - Vaclav Kotesovec, Oct 07 2013
a(n) = Sum_{q=0..floor((n-2)/2)} C(n,q)*C(n-q,n-2-2q)*(n-2)!/2^q, a(n) = (n-2)!/2^n * Sum_{q=0..n} C(n,q) C(2q,n-2), a(n) = (n-2)!/2^n [v^{n-2}] (2+2v+v^2)^n. - Marko Riedel, Jun 10 2016
MATHEMATICA
CoefficientList[Series[((1-x)*(2-x-x^2) - (2-x+x^2)*Sqrt[1-2*x-x^2]) / (3*x^3), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 07 2013 *)
PROG
(Sage)
gf = ((1-x)*(2-x-x^2) - (2-x+x^2)*(1-2*x-x^2)^(1/2)) / (3*x^3)
c = taylor(gf, x, 0, 12).coefficients()
sq = [a*factorial(b) for a, b in c]
sq
# D. S. McNeil, May 24 2010
CROSSREFS
Sequence in context: A187735 A200318 A120015 * A166883 A145158 A132070
KEYWORD
nonn
AUTHOR
Alex Postnikov (apost(AT)math.mit.edu)
EXTENSIONS
More terms from Franklin T. Adams-Watters, May 24 2010
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 04:13 EDT 2024. Contains 371235 sequences. (Running on oeis4.)