Dear Henry,
CC: Neil,
here follows now my complete re-edits of the sequences
A073345, A073346, A014480, A036987, A058922
and an addition to the %Y-line of A001787,
and as an attachment comes your file A073345.txt which
I further edited, and which Neil should then save
to his system as to be accessible with the URL:
http://www.research.att.com/~njas/sequences/A073345.txt
Please see that everything is as you like it,
and then notify Neil if he can submit the changes,
or do your own fine-tuning below, and send them
to Neil. Now I start preparing myself mentally for
the week-end and my two-week holiday.
(that is, forget everything about the binary trees
and their automorphisms...)
Yours,
Antti Karttunen
%I A073345
%S A073345 1,0,0,0,1,0,0,0,0,0,0,0,2,0,0,0,0,1,0,0,0,0,0,0,4,0,0,0,0,0,0,6,0,0,0,
%T A073345 0,0,0,0,6,8,0,0,0,0,0,0,0,4,20,0,0,0,0,0,0,0,0,1,40,16,0,0,0,0,0,0,0,
%U A073345 0,0,68,56,0,0,0,0,0,0,0,0,0,0,94,152,32,0,0,0,0,0,0,0,0,0,0,114,376
%N A073345 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 height k.
%F A073345 (See the Maple code below. Is there a nicer formula?)
%H A073345 H. Bottomley, Explanation for the super-diagonal.
%e A073345 The top-left corner of this square array:
%e A073345 1 0 0 0 0 0 0 0 0 ...
%e A073345 0 1 0 0 0 0 0 0 0 ...
%e A073345 0 0 2 1 0 0 0 0 0 ...
%e A073345 0 0 0 4 6 6 4 1 0 ...
%e A073345 0 0 0 0 8 20 40 68 94 ...
%e A073345 E.g. we have A000108(3) = 5 binary trees built from 3 non-leaf (i.e. branching) nodes:
%e A073345 _______________________________3
%e A073345 ___\/__\/____\/__\/____________2
%e A073345 __\/____\/__\/____\/____\/_\/__1
%e A073345 _\/____\/____\/____\/____\./___0
%e A073345 The first four have height 3, and the last one has height 2, thus T(3,3) = 4, T(3,2) = 1, and T(3,any other value of k) = 0.
%p A073345 A073345 := n -> A073345bi(A025581(n),A002262(n));
%p A073345 A073345bi := proc(n,k) option remember; local i,j; if(0 = n) then if(0 = k) then RETURN(1); else RETURN(0); fi; fi; if(0 = k) then RETURN(0); fi; 2 * add(A073345bi(n-i-1,k-1) * add(A073345bi(i,j),j=0..(k-1)),i=0..floor((n-1)/2)) + 2 * add(A073345bi(n-i-1,k-1) * add(A073345bi(i,j),j=0..(k-2)),i=(floor((n-1)/2)+1)..(n-1)) - (`mod`(n,2))*(A073345bi(floor((n-1)/2),k-1)^2); end;
%p A073345 A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1);
%p A073345 A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);
%Y A073345 Variant: A073346. Column sums: A000108. Row sums: A001699.
%Y A073345 Super-diagonal A073345(n,n-1) = A014480(n-3). - Henry Bottomley (se16@btinternet.com), see the attached explanation.
%Y A073345 A073429 gives the upper triangular region of this array. Cf. also A065329, A001263.
%K A073345 nonn,tabl,new
%O A073345 0,13
%A A073345 Antti Karttunen (my_firstname.my_surname@iki.fi) Jul 31 2002
%I A073346
%S A073346 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,
%T A073346 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,
%U A073346 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 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.
%C A073346 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:
%C A073346 ____________________\/\/\/\/_
%C A073346 _____________\/__\/__\/__\/__
%C A073346 ______________\__/____\_ /___
%C A073346 ____.____\/____\/______\/____ etc.
%C A073346 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 A073346 H. Bottomley, Explanation for the occurrence of A058922.
%e A073346 The top-left corner of this square array:
%e A073346 1 1 0 1 0 0 0 1 ...
%e A073346 0 0 2 0 2 2 0 0 ...
%e A073346 0 0 0 4 4 8 12 12 ...
%e A073346 0 0 0 0 8 16 40 80 ...
%F A073346 (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 lines (k=0 and k=1) are different. Is there a nicer formula?)
%p A073346 A073346 := n -> A073346bi(A025581(n),A002262(n));
%p A073346 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 A073346 A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1);
%p A073346 A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);
%Y A073346 Variant: A073345. The first row: A036987. Column sums: A000108. The diagonal over the super-diagonal: A073346(n, n-2) = A058922(n-2). - Henry Bottomley (se16@btinternet.com), see the attached explanation.
%Y A073346 A073430 gives the upper triangular region of this array. Used to compute A073431.
%K A073346 nonn,tabl,new
%O A073346 0,8
%A A073346 Antti Karttunen (my_firstname.my_surname@iki.fi) Jul 31 2002
%I A014480
%S A014480 1,6,20,56,144,352,832,1920,4352,9728,21504,47104,102400,
%T A014480 221184,475136,1015808,2162688,4587520,9699328,20447232,
%U A014480 42991616,90177536,188743680,394264576,822083584,1711276032
%N A014480 Expansion of (1+2x)/(1-2x)^2.
%F A014480 a(n) = (2n+1)*2^n = 4a(n-1)-4a(n-2) = 4*A052951(n-1) = a(n-1)+A052951(n) = a(n-1)*(2+4/(2n-1)) = A054582(n,n) - Henry Bottomley (se16@btinternet.com), May 16 2001
%Y A014480 Super-diagonal of the square array A073345.
%K A014480 nonn
%O A014480 0,2
%A A014480 njas
%I A036987
%S A036987 1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,
%T A036987 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,
%U A036987 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
%N A036987 Fredholm-Rueppel sequence.
%D A036987 H. Niederreiter and M. Vielhaber, Tree complexity and a doubly ..., J. Complexity, 12 (1996), 187-198.
%H A036987 David Kohel (kohel@math.nus.edu.sg), San Ling and Chaoping Xing (dingcs@comp.nus.edu.sg), Explicit Sequence Expansions
%H A036987 E. Sheppard, net.math post (1985)
%F A036987 1 followed by a string of 2^k - 1 0's. Also a(n)=1 iff n = 2^m - 1.
%Y A036987 The first row of A073346. Occurs for first time in A073202 as the row 6 (and 8).
%Y A036987 Equal to any of the sequences A000108, A007460, A007461, A007463, A007464, A061922 reduced modulo 2. Characteristic function of A000225.
%Y A036987 If interpreted with offset=1 instead of 0 (i.e. a(1)=1, a(2)=1, a(3)=0, a(4)=1, ...) then this is the characteristic function of 2^n (A000079), and as such occurs as the first row of A073265. Also, in that case the INVERT transform will result A023359.
%K A036987 nonn
%p A036987 A036987 := n -> `if`(((2^floor_log_2(n+1)) = (n+1)),1,0);
%p A036987 floor_log_2 := proc(n) local nn,i; nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi; nn := floor(nn/2); od; end;
%O A036987 0,1
%A A036987 njas
%I A058922
%S A058922 0,4,16,48,128,320,768,1792,4096,9216,20480,45056,98304,212992,
%T A058922 458752,983040,2097152,4456448,9437184,19922944,41943040,88080384,
%U A058922 184549376,385875968,805306368,1677721600,3489660928,7247757312
%N A058922 n*2^n - 2^n.
%C A058922 A hierarchical sequence (S(W'2{2}*c) - see A059126).
%H A058922 J. Wallgren, Hierarchical sequences
%Y A058922 A001787(n) = A058922(n+1)/4. A073346(n,n-2) = A058922(n-2).
%K A058922 nonn
%O A058922 1,2
%A A058922 njas, Jan 12 2001
----------------------------------------------------------------------------------
Here I added just the identity A058922(n+1) = 4*A001787(n) to the end of %Y-line:
%I A001787 M3444 N1398
%S A001787 0,1,4,12,32,80,192,448,1024,2304,5120,11264,24576,53248,114688,245760,
%N A001787 n*2^(n-1).
%Y A001787 Partial sums of A001792. Cf. A053109, A001788, A001789. A058922(n+1) = 4*A001787(n).
----------------------------------------------------------------------------------
(Proof: A001787(n) = n*(2^n) - 2^n = (n-1)*(2^n),
and if we compute this from offset 0 instead of 1,
so that y ranging from 0,1,2,3,... corresponds to
n ranging from 1,2,3,4,... i.e. y = n-1,
we get y*(2^(y+1)) = 4*y*(2^(y-1)) = 4*A001787(y) = 4*A001787(n-1).
Just to clarify myself...)