|
| |
|
|
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_]/; 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
Adjacent sequences: A073342 A073343 A073344 * A073346 A073347 A073348
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Antti Karttunen, Jul 31 2002
|
|
|
STATUS
|
approved
|
| |
|
|
