login
This site is supported by donations 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. 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 March 24 07:54 EDT 2017. Contains 283985 sequences.