A036770 Number of labeled rooted trees with a degree constraint: (2*n)!/(2^n) * C(2*n+1, n).

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

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 46.

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.

Index entries for sequences related to rooted trees

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

Cf. A001190, A036771, A036772, A036773, A052510.

Sequence in context: A081854 A085990 A202065 * A201699 A006821 A165626

Adjacent sequences: A036767 A036768 A036769 * A036771 A036772 A036773

Keyword

nonn

Author

N. J. A. Sloane

Status

approved