A036774 Number of labeled rooted unordered binary trees (each node has out-degree <= 2).

0, 1, 2, 9, 60, 540, 6120, 83790, 1345680, 24811920, 516650400, 11992503600, 307069963200, 8598348158400, 261387760233600, 8573572885878000, 301809119163552000, 11349727401396384000, 454104511068656448000, 19261139319649202976000

Offset

0,3

Links

Fung Lam, Table of n, a(n) for n = 0..394

B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019.

L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (14) with r = 2.

Index entries for sequences related to rooted trees

Formula

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

E.g.f. A(x) satisfies x*A(x)^2 + 2*(x-1)*A(x) + 2*x = 0, A(0)=0 and A(x) = x/(1-x-(x/2)*A(x)). - Michael Somos, Sep 06 2003

a(n) = n!*Sum_{k=0..floor((n-1)/2)} binomial(n-1, 2k)*binomial(2k, k)/(2^k*(k+1)). - Emanuele Munarini, Feb 06 2013

a(n) ~ sqrt(2-sqrt(2))*n^(n-1)/(exp(n)*(sqrt(2)-1)^(n+1)). - Vaclav Kotesovec, Sep 24 2013

Recurrence: (n+1)*a(n) = n*(n-1)*(n-2)*a(n-2) + n*(2*n-1)*a(n-1), n >= 3, a(1)=1, a(2)=2. - Fung Lam, Feb 24 2014

a(n) = n!*hypergeom([(1 - n)/2, 1 - n/2], [2], 2) for n >= 1. Peter Luschny, Apr 20 2020

Maple

# This is a crude Maple program based on Eq. (14), p. 4, in Takacs (1993). It calculates a(n) for n >= 2. Here, r = 2 is the maximum out-degree of each node.
ff := proc(r, n) simplify(subs(x = 0, diff(sum(x^k/k!, k = 0 .. r)^n, x$(n - 1)))); end;
seq(ff(2, i), i = 2 .. 40); # Petros Hadjicostas, Jun 09 2019

Mathematica

Range[0, 20]! CoefficientList[Series[(1 - x - ((x - 1)^2 - 2 x^2)^(1/2))/x, {x, 0, 20}], x] (* Geoffrey Critzer, Nov 22 2011 *)
f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
a[n_] := If[n == 1, 1, Derivative[n - 1][f[2, n]][0]];
a /@ Range[0, 19] (* Jean-François Alcover, Apr 20 2020, after Petros Hadjicostas *)
a[n_] := n! Hypergeometric2F1[1/2 - n/2, 1 - n/2, 2, 2]; a[0] = 0;
Array[a, 20, 0] (* Peter Luschny, Apr 20 2020 *)

Prog

(PARI) a(n)=if(n<1, 0, n!*polcoeff(2*x/(1-x+sqrt(1-2*x-x^2+O(x^n))), n))
(PARI) a(n)=if(n<1, 0, n!*polcoeff(serreverse(2*x/(2+2*x+x^2)+x*O(x^n)), n))
(Maxima) makelist(n!*sum(binomial(n-1, 2*k)*binomial(2*k, k)/(2^k*(k+1)), k, 0, floor((n-1)/2)), n, 0, 20); /* Emanuele Munarini, Feb 06 2013 */

Crossrefs

A071356(n) = a(n + 1) * 2^n/(n + 1)!.

Cf. A036775 (outdegree <= r = 3), A036776 (out-degree <= r = 4), A036777 (out-degree <= r = 5).

Sequence in context: A001193 A161391 A120014 * A306065 A166882 A268937

Adjacent sequences: A036771 A036772 A036773 * A036775 A036776 A036777

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Better description and formula from Christian G. Bower, Nov 29 2001

"unordered" added to the name by David Callan, Apr 22 2012

Status

approved