A073345 Table T(n,k), read by ascending antidiagonals, giving the number of rooted plane binary trees of size n and height k.
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, 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, 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
Offset: 0
Examples
The top-left corner of this square array is 1 0 0 0 0 0 0 0 0 ... 0 1 0 0 0 0 0 0 0 ... 0 0 2 1 0 0 0 0 0 ... 0 0 0 4 6 6 4 1 0 ... 0 0 0 0 8 20 40 68 94 ... E.g. we have A000108(3) = 5 binary trees built from 3 non-leaf (i.e. branching) nodes: _______________________________3 ___\/__\/____\/__\/____________2 __\/____\/__\/____\/____\/_\/__1 _\/____\/____\/____\/____\./___0 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.
References
- 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.
Links
- Alois P. Heinz, Antidiagonals n = 0..200, flattened
- Henry Bottomley and Antti Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.
- Andrew Odlyzko, Analytic methods in asymptotic enumeration.
Crossrefs
Programs
-
Maple
A073345 := n -> A073345bi(A025581(n), A002262(n)); 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; A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1); A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);
-
Mathematica
a[0, 0] = 1; a[n_, k_]/;k
Formula
(See the Maple code below. Is there a nicer formula?)
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
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
Comments