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,3

Comments

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

Links

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

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]

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 *)

Prog

(MIT/GNU Scheme) (define (A073268 n) (if (zero? n) 1 (let sumloop ((i (floor->exact (/ (log n) (log 2)))) (s 0)) (cond ((negative? i) s) (else (sumloop (-1+ i) (+ s (A000108 (- n (expt 2 i))))))))))
(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 */

Crossrefs

Occurs for first time in A073202 as row 41.

Sequence in context: A095341 A167123 A029895 * A073190 A066051 A056971

Adjacent sequences: A073265 A073266 A073267 * A073269 A073270 A073271

Keyword

nonn

Author

Antti Karttunen, Jun 25 2002

Status

approved