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

%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