cp's OEIS Frontend

A073345 Table T(n,k), read by ascending antidiagonals, giving the number of rooted plane binary trees of size n and height k.

%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, <a href="/A073345/b073345.txt">Antidiagonals n = 0..200, flattened</a>
%H A073345 Henry Bottomley and Antti Karttunen, <a href="/A073345/a073345.txt">Notes concerning diagonals of the square arrays A073345 and A073346</a>.
%H A073345 Andrew Odlyzko, <a href="http://www.dtc.umn.edu/~odlyzko/doc/enumeration.html">Analytic methods in asymptotic enumeration</a>.
%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<n||k>2^n-1 := 0; a[n_, k_]/;1 <= n <= k <= 2^n-1 := a[n, k] = Sum[a[n-1, k-1-i](2Sum[ a[j, i], {j, 0, n-2}]+a[n-1, i]), {i, 0, k-1}]; Table[a[n, k], {n, 0, 9}, {k, 0, 9}]
%t A073345 (* or *) a[0] = 0; a[1] = 1; a[n_]/;n>=2 := a[n] = Expand[1 + x a[n-1]^2]; gfT[n_] := a[n]-a[n-1]; Map[CoefficientList[ #, x, 8]&, Table[gfT[n], {n, 9}]/.{x^i_/;i>=9 ->0}] (Callan)
%Y A073345 Variant: A073346. Column sums: A000108. Row sums: A001699.
%Y A073345 Diagonals: A073345(n, n) = A011782(n), A073345(n+3, n+2) = A014480(n), A073345(n+2, n) = A073773(n), A073345(n+3, n) = A073774(n) - _Henry Bottomley_ and AK, see the attached notes.
%Y A073345 A073429 gives the upper triangular region of this array. Cf. also A065329, A001263.
%K A073345 nonn,tabl
%O A073345 0,13
%A A073345 _Antti Karttunen_, Jul 31 2002