VOOZH about

URL: https://oeis.org/A073268

⇱ A073268 - OEIS

login
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.
6
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.
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
(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
KEYWORD
nonn
AUTHOR
Antti Karttunen, Jun 25 2002
STATUS
approved