A073268 Number of plane binary trees whose right (or respectively: left) subtree is a unique "complete" tree of (2^m)-1 nodes with all the leaf-nodes at the same depth m and the left (or respectively: right) subtree is any plane binary tree of size n - 2^m + 1.

1, 1, 2, 3, 8, 20, 58, 179, 576, 1902, 6426, 22092, 77026, 271702, 967840, 3476555, 12578728, 45800278, 167693698, 617037126, 2280467586, 8461771342, 31510700712, 117725789124, 441141656810, 1657559677646, 6243810767912

Offset: 0

Author

Antti Karttunen, Jun 25 2002

Keywords

• nonn

Comments

The Catalan bijection A073286 fixes only these kinds of trees, so this occurs in A073202 as row 41.

Crossrefs

Occurs for first time in A073202 as row 41.

Programs

Maple

A073268 := proc(n) local i; if(0=n) then 1 else add(Cat(n-2^i),i=0..floor(evalf(log[2](n)))); fi; end;
Cat := n -> binomial(2*n,n)/(n+1);

Mathematica

a[0] = 1; a[n_] := Sum[CatalanNumber[n - 2^i], {i, 0, Log[2, n]}]; Table[ a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 05 2016 *)

PARI

N=66; x='x+O('x^N); lg=ceil(log(N)/log(2));
C(x)=(1-sqrt(1-4*x))/(2*x);
gf=1+sum(k=0, lg, x^(2^k)*C(x) );
Vec(gf)
/* Joerg Arndt, Jul 02 2012 */

Formula

a(0)=1, a(n) = Sum_{i=0..floor(log_2(n))} Cat(n-(2^i))

G.f.: 1 + Sum_{k>=0} x^(2^k)*C(x) where C(x) = (1-sqrt(1-4*x))/(2*x) is the g.f. of the Catalan numbers (A000108). [Joerg Arndt, Jul 02 2012]