login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
OFFSET
0,3
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
KEYWORD
nonn
AUTHOR
Alex Postnikov (apost(AT)math.mit.edu)
EXTENSIONS
More terms from Franklin T. Adams-Watters, May 24 2010
STATUS
approved