login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
The Catalan bijection A073286 fixes only these kinds of trees, so this occurs in A073202 as row 41.
LINKS
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 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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 07:41 EDT 2024. Contains 370958 sequences. (Running on oeis4.)