login
A036770
Number of labeled rooted trees with a degree constraint: (2*n)!/(2^n) * C(2*n+1, n).
8
1, 3, 60, 3150, 317520, 52390800, 12843230400, 4382752374000, 1986847742880000, 1155153277710432000, 838011196011749760000, 742058914068404412480000, 787724078011075453248000000, 987468397792455300321600000000, 1443283810213452666950050560000000
OFFSET
0,2
COMMENTS
a(n) is the number of rooted labeled strictly binary trees (each vertex has exactly two children or none) on 2*n + 1 vertices. - Geoffrey Critzer, Nov 13 2011
LINKS
Lajos Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10; see Eqs. (12) and (13) on p. 4.
Eric Weisstein's World of Mathematics, Strongly Binary Tree.
FORMULA
Recurrence (with interpolated zeros): Define (b(n): n >= 0) by b(2*m+1) = a(m) and b(2*m) = 0 for m >= 0. Then the sequence (b(n): n >= 0) satisfies the recurrence (-2*n^3 - 6*n^2 - 4*n)*b(n) + (n + 3)*b(n+2) = 0 for n >= 0 with b(0) = 0 and b(1) = 1. [Corrected by Petros Hadjicostas, Jun 07 2019]
E.g.f. with interpolated zeros: G(x) = Sum_{n >= 0} b(n)*x^n/n! = Sum_{m >= 0} a(m)*x^(2*m + 1)/(2*m + 1)! = 1/x * (1 - (1 - 2*x^2)^(1/2)) for 0 < |x| < 1/sqrt(2). [Edited by Petros Hadjicostas, Jun 07 2019]
E.g.f. with interpolated zeros satisfies G(x)= x*(1 + G(x)^2/2). - Geoffrey Critzer, Nov 13 2011
D-finite with recurrence (with no interpolated zeros): -2*a(n)*(n + 1)*(2*n + 1)*(2*n + 3) + (n + 2)*a(n+1) = 0 with a(0) = 1. - Petros Hadjicostas, Jun 08 2019
G.f.: 4F1(1,1,1/2,3/2;2;8*x). - R. J. Mathar, Jan 28 2020
MAPLE
spec := [S, {S=Union(Z, Prod(Z, Set(S, card=2)))}, labeled]: seq(combstruct[count](spec, size=n)
MATHEMATICA
Range[0, 19]! CoefficientList[Series[(1 - (1 - 2 x^2)^(1/2))/x, {x, 0, 20}], x] (* Geoffrey Critzer, Nov 13 2011 *)
PROG
(Magma) [Factorial(2*n)/(2^n) * Binomial(2*n+1, n): n in [0..15]]; // Vincenzo Librandi, Jan 29 2020
CROSSREFS
KEYWORD
nonn
STATUS
approved