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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A073345 Table T(n,k), read by ascending antidiagonals, 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
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_]/; 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}]
(* 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
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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 11:14 EDT 2024. Contains 371278 sequences. (Running on oeis4.)