A073773 Number of plane binary trees of size n+2 and height n.

0, 0, 0, 6, 40, 152, 480, 1376, 3712, 9600, 24064, 58880, 141312, 333824, 778240, 1794048, 4096000, 9273344, 20840448, 46530560, 103284736, 228065280, 501219328, 1096810496, 2390753280, 5192548352, 11240734720, 24259854336

Offset

0,4

Links

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

Henry Bottomley & Antti Karttunen Derivations of the formulas for the diagonals of A073345 & A073346.

Formula

a(n) = A073345(n+2, n).

a(n < 3) = 0, a(n) = ((n^2 - 6)*2^(n-2)).

Example

a(3) = 6 because there exists only these six binary trees of size 5 and height 3:
_\/\/_______\/\/_\/_\/_____\/_\/_\/___\/___V_V___
__\/_\/___\/_\/___\/_\/___\/_\/___\/_\/___\/_\/__
___\./_____\./_____\./_____\./_____\./_____\./___

Maple

A073773 := n -> `if`((n < 3), 0, ((n^2 - 6)*2^(n-2)));

Crossrefs

Cf. A014480, A073345, A073774, A028878.

Sequence in context: A318169 A027777 A227013 * A001919 A342404 A005553

Adjacent sequences: A073770 A073771 A073772 * A073774 A073775 A073776

Keyword

nonn

Author

Antti Karttunen, Aug 11 2002

Status

approved