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.

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

Offset

0,8

Comments

The height of binary trees is computed here in the same way as in A073345, except that 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

Table of n, a(n) for n=0..93.

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 row k are all divisible by 2^k, thus dividing them out yields the array/triangle A074079/A074080.

Sequence in context: A255365 A256505 A337196 * A114099 A028613 A318381

Adjacent sequences: A073343 A073344 A073345 * A073347 A073348 A073349

Keyword

nonn,tabl

Author

Antti Karttunen, Jul 31 2002

Extensions

Sequence number in comments corrected

Status

approved