login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003692 Number of trees on n labeled vertices with degree at most 3. 4
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

Table of n, a(n) for n=0..17.

Math.Stackexchange.com, Marko Riedel et al., Number of labeled trees

Marko Riedel, Maple code for three closed forms and enumeration by Pruefer codes.

Index entries for sequences related to trees

FORMULA

E.g.f.: ((1-x)*(2-x-x^2) - (2-x+x^2)*sqrt(1-2*x-x^2)) / (3*x^3).

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

Cf. A000272, A274056, A274081, A274083.

Sequence in context: A187735 A200318 A120015 * A166883 A145158 A132070

Adjacent sequences:  A003689 A003690 A003691 * A003693 A003694 A003695

KEYWORD

nonn

AUTHOR

apost(AT)math.mit.edu (Alex Postnikov)

EXTENSIONS

More terms and g.f. edited by 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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 19 04:05 EST 2017. Contains 294912 sequences.