# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a073345
Showing 1-1 of 1
%I A073345 #20 Mar 02 2024 10:37:21
%S A073345 1,0,0,0,1,0,0,0,0,0,0,0,2,0,0,0,0,1,0,0,0,0,0,0,4,0,0,0,0,0,0,6,0,0,
%T A073345 0,0,0,0,0,6,8,0,0,0,0,0,0,0,4,20,0,0,0,0,0,0,0,0,1,40,16,0,0,0,0,0,0,
%U A073345 0,0,0,68,56,0,0,0,0,0,0,0,0,0,0,94,152,32,0,0,0,0,0,0,0,0,0,0,114,376,144,0,0,0,0,0,0,0
%N A073345 Table T(n,k), read by ascending antidiagonals, giving the number of rooted plane binary trees of size n and height k.
%D A073345 Luo Jian-Jin, Catalan numbers in the history of mathematics in China, in Combinatorics and Graph Theory, (Yap, Ku, Lloyd, Wang, Editors), World Scientific, River Edge, NJ, 1995.
%H A073345 Alois P. Heinz, Antidiagonals n = 0..200, flattened
%H A073345 Henry Bottomley and Antti Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.
%H A073345 Andrew Odlyzko, Analytic methods in asymptotic enumeration.
%F A073345 (See the Maple code below. Is there a nicer formula?)
%F A073345 This table was known to the Chinese mathematician Ming An-Tu, who gave the following recurrence in the 1730s. a(0, 0) = 1, a(n, k) = Sum[a(n-1, k-1-i)( 2*Sum[ a(j, i), {j, 0, n-2}]+a(n-1, i) ), {i, 0, k-1}]. - _David Callan_, Aug 17 2004
%F A073345 The generating function for row n, T_n(x):=Sum[T(n, k)x^k, k>=0], is given by T_n = a(n)-a(n-1) where a(n) is defined by the recurrence a(0)=0, a(1)=1, a(n) = 1 + x a(n-1)^2 for n>=2. - _David Callan_, Oct 08 2005
%e A073345 The top-left corner of this square array is
%e A073345 1 0 0 0 0 0 0 0 0 ...
%e A073345 0 1 0 0 0 0 0 0 0 ...
%e A073345 0 0 2 1 0 0 0 0 0 ...
%e A073345 0 0 0 4 6 6 4 1 0 ...
%e A073345 0 0 0 0 8 20 40 68 94 ...
%e A073345 E.g. we have A000108(3) = 5 binary trees built from 3 non-leaf (i.e. branching) nodes:
%e A073345 _______________________________3
%e A073345 ___\/__\/____\/__\/____________2
%e A073345 __\/____\/__\/____\/____\/_\/__1
%e A073345 _\/____\/____\/____\/____\./___0
%e A073345 The first four have height 3 and the last one has height 2, thus T(3,3) = 4, T(3,2) = 1 and T(3,any other value of k) = 0.
%p A073345 A073345 := n -> A073345bi(A025581(n), A002262(n));
%p A073345 A073345bi := proc(n,k) option remember; local i,j; if(0 = n) then if(0 = k) then RETURN(1); else RETURN(0); fi; fi; if(0 = k) then RETURN(0); fi; 2 * add(A073345bi(n-i-1,k-1) * add(A073345bi(i,j),j=0..(k-1)),i=0..floor((n-1)/2)) + 2 * add(A073345bi(n-i-1,k-1) * add(A073345bi(i,j),j=0..(k-2)),i=(floor((n-1)/2)+1)..(n-1)) - (`mod`(n,2))*(A073345bi(floor((n-1)/2),k-1)^2); end;
%p A073345 A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1);
%p A073345 A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);
%t A073345 a[0, 0] = 1; a[n_, k_]/;k