|
%I #14 Apr 01 2017 20:57:58
%S 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,
%T 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,
%U 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
%N 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.
%C 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:
%C ____________________\/\/\/\/_
%C _____________\/__\/__\/__\/__
%C ______________\__/____\_ /___
%C ____.____\/____\/______\/____ etc.
%C 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.
%H H. Bottomley and A. Karttunen, <a href="/A073345/a073345.txt">Notes concerning diagonals of the square arrays A073345 and A073346.</a>
%F (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?)
%e The top-left corner of this square array:
%e 1 1 0 1 0 0 0 1 ...
%e 0 0 2 0 2 2 0 0 ...
%e 0 0 0 4 4 8 12 12 ...
%e 0 0 0 0 8 16 40 80 ...
%p A073346 := n -> A073346bi(A025581(n), A002262(n));
%p 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;
%p A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1);
%p A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);
%Y 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.].
%Y 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.
%K nonn,tabl
%O 0,8
%A _Antti Karttunen_, Jul 31 2002
%E Sequence number in comments corrected
|
