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

Author

Antti Karttunen, Jul 31 2002

Keywords

• nonn
• tabl

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.

Examples

			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 ...
		

Links

• H. Bottomley and A. Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.

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.

Programs

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);

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?)

Extensions

Sequence number in comments corrected