A073268 - OEIS

%I #17 May 18 2024 14:51:10

%S 1,1,2,3,8,20,58,179,576,1902,6426,22092,77026,271702,967840,3476555,

%T 12578728,45800278,167693698,617037126,2280467586,8461771342,

%U 31510700712,117725789124,441141656810,1657559677646,6243810767912

%N 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.

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

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

%F 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]

%p 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;

%p Cat := n -> binomial(2*n,n)/(n+1);

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

%o (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))))))))))

%o (PARI)

%o N=66; x='x+O('x^N); lg=ceil(log(N)/log(2));

%o C(x)=(1-sqrt(1-4*x))/(2*x);

%o gf=1+sum(k=0, lg, x^(2^k)*C(x) );

%o Vec(gf)

%o /* _Joerg Arndt_, Jul 02 2012 */

%Y Occurs for first time in A073202 as row 41.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jun 25 2002