The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A073345 Table T(n,k) (listed antidiagonalwise in order T(0,0), T(1,0), T(0,1), T(2,0), T(1,1), ...) giving the number of rooted plane binary trees of size n and height k. 12
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 0,13 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 H. Bottomley and A. Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346. Andrew Odlyzko, Analytic methods in asymptotic enumeration. 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 EXAMPLE 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. 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_]/; k2^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}] (* 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) CROSSREFS Variant: A073346. Column sums: A000108. Row sums: A001699. 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. A073429 gives the upper triangular region of this array. Cf. also A065329, A001263. Sequence in context: A279372 A086077 A178408 * A216511 A138088 A112765 Adjacent sequences: A073342 A073343 A073344 * A073346 A073347 A073348 KEYWORD nonn,tabl AUTHOR Antti Karttunen, Jul 31 2002 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 28 05:31 EDT 2023. Contains 361577 sequences. (Running on oeis4.)