cp's OEIS Frontend

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.

%I A073268 #17 May 18 2024 14:51:10
%S A073268 1,1,2,3,8,20,58,179,576,1902,6426,22092,77026,271702,967840,3476555,
%T A073268 12578728,45800278,167693698,617037126,2280467586,8461771342,
%U A073268 31510700712,117725789124,441141656810,1657559677646,6243810767912
%N 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.
%C A073268 The Catalan bijection A073286 fixes only these kinds of trees, so this occurs in A073202 as row 41.
%F A073268 a(0)=1, a(n) = Sum_{i=0..floor(log_2(n))} Cat(n-(2^i))
%F A073268 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 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 A073268 Cat := n -> binomial(2*n,n)/(n+1);
%t A073268 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 A073268 (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 A073268 (PARI)
%o A073268 N=66; x='x+O('x^N); lg=ceil(log(N)/log(2));
%o A073268 C(x)=(1-sqrt(1-4*x))/(2*x);
%o A073268 gf=1+sum(k=0, lg, x^(2^k)*C(x) );
%o A073268 Vec(gf)
%o A073268 /* _Joerg Arndt_, Jul 02 2012 */
%Y A073268 Occurs for first time in A073202 as row 41.
%K A073268 nonn
%O A073268 0,3
%A A073268 _Antti Karttunen_, Jun 25 2002