login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A036774 Number of labeled rooted unordered binary trees (each node has out-degree <= 2). 14
0, 1, 2, 9, 60, 540, 6120, 83790, 1345680, 24811920, 516650400, 11992503600, 307069963200, 8598348158400, 261387760233600, 8573572885878000, 301809119163552000, 11349727401396384000, 454104511068656448000, 19261139319649202976000 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 8 11:48 EST 2021. Contains 341948 sequences. (Running on oeis4.)