|
Search: id:A073346
|
|
|
| A073346 |
|
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 "contracted height" k. |
|
+0
12
|
|
| 1, 1, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 4, 0, 0, 0, 0, 2, 4, 0, 0, 0, 0, 1, 0, 8, 8, 0, 0, 0, 0, 0, 0, 12, 16, 0, 0, 0, 0, 0, 0, 2, 12, 40, 16, 0, 0, 0, 0, 0, 0, 2, 12, 80, 48, 0, 0, 0, 0, 0, 0, 0, 0, 12, 136, 144, 32, 0, 0, 0, 0, 0, 0, 0, 2, 20, 224, 384, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16
(list; table; graph; listen)
|
|
|
OFFSET
|
0,8
|
|
|
COMMENT
|
The height of binary trees is computed here otherwise as with A073245, but whenever a complete binary tree of (2^k)-1 nodes with all its leaves at the same level, i.e. one of the following trees:
____________________\/\/\/\/_
_____________\/__\/__\/__\/__
______________\__/____\_ /___
____.____\/____\/______\/____ etc.
is encountered as a terminating subtree, it is regarded just a variant of . (an empty tree, a single leaf) and contributes nothing to the height of the tree.
|
|
LINKS
|
H. Bottomley and A. Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.
|
|
FORMULA
|
(See the Maple code below. Note that here we use the same convolution recurrence as with A073345, but only the initial conditions for the first two rows (k=0 and k=1) are different. Is there a nicer formula?)
|
|
EXAMPLE
|
The top-left corner of this square array:
1 1 0 1 0 0 0 1 ...
0 0 2 0 2 2 0 0 ...
0 0 0 4 4 8 12 12 ...
0 0 0 0 8 16 40 80 ...
|
|
MAPLE
|
A073346 := n -> A073346bi(A025581(n), A002262(n));
A073346bi := proc(n, k) option remember; local i, j; if(0 = k) then RETURN(A036987(n)); fi; if(0 = n) then RETURN(0); fi; 2 * add(A073346bi(n-i-1, k-1) * add(A073346bi(i, j), j=0..(k-1)), i=0..floor((n-1)/2)) + 2 * add(A073346bi(n-i-1, k-1) * add(A073346bi(i, j), j=0..(k-2)), i=(floor((n-1)/2)+1)..(n-1)) - (`mod`(n, 2))*(A073346bi(floor((n-1)/2), k-1)^2) - (`if`((1=k), 1, 0))*A036987(n); 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);
|
|
CROSSREFS
|
Variant: A073345. The first row: A036987. Column sums: A000108. Diagonals: T(n, n) = A000007(n), T(n+1, n) = A000079(n), T(n+2, n) = A058922(n), T(n+3, n) = A074092(n) - [see the attached notes.].
A073430 gives the upper triangular region of this array. Used to compute A073431. Entries on the row k are all divisible by 2^k, thus dividing them out yields the array/triangle A074079/A074080.
Sequence in context: A138045 A004530 A084863 this_sequence A114099 A028613 A024362
Adjacent sequences: A073343 A073344 A073345 this_sequence A073347 A073348 A073349
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Antti Karttunen Jul 31 2002
|
|
|
Search completed in 0.003 seconds
|
