Notes concerning diagonals of the square arrays A073345 and A073346.
- Henry Bottomley (se16@btinternet.com), Aug 02 2002.
------------------------------------------------------------------------
A073345(n,k) is the number of rooted binary trees of size n and height k.
........................................................................
Proposition:
A073345(n,n) = 2^(n-1) for n>0.
Proof:
Taking the proposition as an inductive hypothesis and noting:
A073345(1,1) = 1,
and
A073345(n+1,n+1) = 2*A073345(n,n)
since each rooted binary tree (of size n and height n) may have only
two leaves at the topmost level n. There are four ways to put
the extra node to increase both the size and height by one,
namely either to add \/ to the left or the right hand side top leaf,
or to add \/ below the root, so that the old tree sprouts either
from the left or righthand side branch. However, any tree of
size n+1, height n+1 constructed by growing from the root, can be
also constructed by growing another (or the same) tree from the top,
and vice versa, thus we need to consider only one possibility,
leaving us just two ways (left or right) of growing unique trees.
So the hypothesis is true by induction.
........................................................................
Proposition:
A073345(n,n-1) = (2n-5)*2^(n-3) = A014480(n-3) for n>2.
Proof:
A073345(n,n-1) = (n-2)*A073345(n-1,n-1)-(1/2)*A073345(n-1,n-1) =
for n>2
since for each rooted binary tree of size (n-1) and height (n-1)
there are (n-2) places to put the extra node which does not increase
the height, but not all of these each new rooted binary trees are
unique (when the extra node is put as high as possible, then a set
of pairs of identical new trees is produced), so
A073345(n,n-1) = (n-2)*2^(n-2)-(1/2)*2^(n-2)
= (2n-5)*2^(n-3)
= (2*(n-3)+1)*2^(n-3)
= A014480(n-3).
------------------------------------------------------------------------
A073346(n,k) is the number of rooted binary trees of size n and
"contracted" height k.
........................................................................
Proposition:
A073346(n,n-1) = 2^(n-1) for n>0.
Proof:
A073346(n,n-1) = A073345(n,n) = 2^(n-1) for n>0
since the only rooted binary trees of size n and "contracted height"
n-1 are rooted binary trees of size n and height n with the top node
contracted by 1, and there is a direct correspondence between them.
........................................................................
Proposition:
A073346(n,n-2) = (n-3)*2^(n-2) = A058922(n-2) for n>2.
Proof:
A073346(n,n-2) = A073345(n,n-1)-2*A073345(n-3,n-3) for n>2
since the only rooted binary trees of size n and "contracted height"
n-2 are rooted binary trees of size n and height n-1 with the top
node contracted by 1 (those trees with only 2 leaves at the topmost
level), so from A073345(n,n-1) trees of size n and height n-1 we
have to subtract those cases where the topmost subtree is the
complete binary tree of 3 nodes:
\./ \./
\./
(as their contracted height is 2 less than their real height),
and because that tree can be grafted to _either_ of the topmost
leaves of any size n-3, height n-3 tree (to get size n, height n-1
trees), of which there are 2*A073345(n-3,n-3), so:
A073346(n,n-2) = (2n-5)*2^(n-3)-2*2^(n-4)
= (2n-6)*2^(n-3)
= (n-3)*2^(n-2)
= A058922(n-2).
------------------------------------------------------------------------
Addendum, concerning the diagonals T(n+2,n) and T(n+3,n) of A073345.
- Antti Karttunen (my_firstname.my_secondname@iki.fi), Aug 11 2002,
following on Henry's footsteps.
........................................................................
Proposition:
A073345(n+2,n) = (n^2 - 6)*2^(n-2) for n>=3.
Proof:
There are 2^(n-1) rooted binary trees of size n and
height n. These contain n+1 leaves, of which n-2
are open for the first single extra node \/ to be grafted,
and n-3 for the second, so that neither of them reaches
the top. These can be grafted in either order, so we have
(n-2)*(n-3)/2 possibilities to extend each distinct
main trunk with two separate \/ nodes, so that there
will be only two leaves on the height n.
Furthermore, if the other \/ is grafted to the next-to-top
leaf, so that its leaves do reach the top-level, then the
second \/ can be grafted to n-2 leaves below it.
However, these all allow duplicate solutions, so we
got (n-2)/2 ways to extend each main trunk this way.
\/ \/
Then there is (n-3) ways to graft either \/ or \/ so that
its top-leaves do not reach the height of the main trunk,
and one way to graft either of them so that they reach the
top level, but these are all duplicated, so we got
2*(n-3) + 2/2 ways more.
So altogether, we got
2^(n-1) * (((n-2)*(n-3))/2 + (n-2)/2 + 2*(n-3) + 1)
= (n^2 - 6) * 2^(n-2)
solutions for n >= 3. This sequence has now been stored as A073773
in OEIS.
........................................................................
Proposition:
A073345(n,n-3)
(n - 4) 3 2
= 1/12 2 (2 n - 9 n - 23 n + 18) for all n >= 7.
or put in another way
A073345(n+3,n)
(n - 1) 3 2
= 1/12 2 (2 n + 9 n - 23 n - 78) for all n >= 4.
Proof:
If we construct a binary tree of size n and height n-3,
we know it contains as a "main trunk" a binary tree
of size n-3 and height n-3, of which there are
2^(n-4) different kinds, as was noted above.
Again, we are going to graft to it various branches of
subtrees, taking care that we don't grow the
height, and that we avoid duplicate solutions.
First, we graft 3 separate single nodes \/
to different places:
The binary tree of size n-3 has n-2 leaves,
but of these the two topmost are forbidden
in any case, and also the next-topmost one
if we want to be sure that the grafted node
does not reach the top, so there is n-4 leaves
allowed for the first node, n-5 for the
second and n-6 for the third. These could
be grafted in any order, so there are
((n-4)*(n-5)*(n-6)/6) = binomial(n-4,3) solutions.
Then, if the first node comes to the second topmost position, where
its leaves do reach the top, there are then (n-5) free leaves where
to graft the second node, and (n-6) free leaves for the third one.
These can come in either order, and also, we cannot be sure which
one of the two topmost nodes belongs to the original (n-3,n-3) tree
and which one was grafted later (i.e. there are duplicate solutions),
so we have (n-5)*(n-6)/4 solutions here.
Then, if we have either variant of the two-node
binary tree \/ or \/
\/ \/
and one \/, we can graft the two-node tree to
(n-6) places where its topmost leaves do not
reach the top, and the remaining \/ also to
(n-6) positions where it doesn't reach the
top, so there are 2*(n-6)^2 solutions here.
Then, if the two-node tree comes to the leaf
where it reaches the top, the \/ can come
to any of the (n-6) remaining positions where
it doesn't reach the top, and also, if the
single node comes to the leaf where its leaves
reach the top, the two node tree can come
to (n-6) remaining positions, and both of
these cases have duplicate solutions, so
we have
2*(n-6) cases here.
(We can ignore the case where the both subtrees
reach the top, because these are duplicated
by the cases where a complete binary tree
of 3 nodes reaches the top, handled below).
Then, there are four different binary trees
of size 3 and height 3, namely:
\/ \/ \/ \/
\/ \/ \/ \/
\/ \/ \/ \/
and these can be grafted to (n-7) positions
where their top-leaves do not reach the top
of the tree, so we have 4*(n-7) solutions,
and there is just one position to graft any of
them so that it reaches the top, but these
are all duplicated solutions, so we have only
4/2 = 2 solutions more.
Then there is the complete binary tree of
3 nodes:
\/\/
\/
which can be grafted to (n-5) positions in the
tree, regardless of whether its leaves reach
the top or not, because even when on the top,
the solution cannot be duplicated if we start
from a different main trunk.
So altogether, we got
(2^(n-4)) * # Number of the different main trunks of the size and height n+3
(((n-5)*(n-6)*(n-7)/6) # 3 \/'s to differ. places, none reaching the top.
+ ((n-5)*(n-6)/4) # One \/ reaching the top, 2 \/'s to elsewhere.
+ 2*(n-6)^2 # One two-node tree (2 variants) anywhere where
# it doesn't reach the top, and also \/ to anywhere
# where it doesn't reach the top.
+ 2*(n-6) # Either the 2-node or 1-node subtree reach the top
# (but not both!)
+ 4*(n-7) # (n-7) ways to graft any of the four 3 node trees
# of height 3, so that it doesn't reach the top.
+ 2 # One way to place those four trees to position
# where they reach the top, of which half is
# duplicate solutions.
+ (n-5) # (n-5) ways to graft a complete bin tree of
) # 3 nodes, regardless of whether it reaches
# the top or not.
(n - 4) 3 2
= 1/12 2 (2 n - 9 n - 23 n + 18)
solutions for the binary trees of size n and height n-3, valid for
all sizes >= 7,
which, with the substitution n -> x+3, results:
(x - 1) 3 2
x -> 1/12 2 (2 x + 9 x - 23 x - 78)
the formula used in A073774, for the binary trees of size x+3 and height x,
valid for all heights x >= 4.
------------------------------------------------------------------------
Addendum 2, concerning the diagonal T(n+3,n) of A073346.
- Antti Karttunen (my_firstname.my_secondname@iki.fi), Aug 19 2002.
........................................................................
Proposition:
A073346(n+3,n) = 2^(n-1) * (n+2) * (n-1)
= 2^n * (C(n,n-2)+C(n-1,n-2))
for all n >= 2. (where C(r,c) is the binomial coefficient).
Proof:
The only rooted binary trees of size n+3 and contracted height n
are either
a) rooted binary trees of size n+3 and height n+1 with either
one or two nodes (i.e. 2 or 4 leaves) reaching the top
contracted by 1, from which we have to exclude the trees
with two \/-nodes at the top _next to each other_ (with a
common parent), because they form a complete binary tree
of size 3, which contracts by 2, so this
case contributes A073345((n+1)+2,n+1) - 2^n * ((n+1)-2)/2, i.e.:
2^n * (((n-1)*(n-2))/2 + 2*(n-2) + 1)
or
\/\/
b) rooted binary trees of size n+3 and height n+2, with \/ occurring
as the topmost subtree, thus contracted by 2 steps.
So we have to add further 2^n trees because the crown shown
above can be grafted to the either of the topmost leaf of any
2^(n-1) binary trees of size n and height n binary trees.
(These are exactly those same 2*2^(n-4) trees that
were excluded when we computed the case A073346(n,n-2)).
So we got A073346(n+3,n) =
2^n * (((n-1)*(n-2))/2 + 2*(n-2) + 1) + 2^n
= 2^(n-1) * (n^2 + n - 2)
= 2^(n-1) * (n+2) * (n-1)
= 2^n * ((n-1)*(n+2)/2)
= 2^n * A000096(n-1)
= 2^n * (C(n,n-2)+C(n-1,n-2))
for all n >= 2.
(This is now stored as the sequence A074092 in OEIS,
with the terms a(0)=1 and a(1)=2 also included).
This implies also that a diagonal in A074079,
A074079(n+3,n) = A000096(n-1) for all n >= 2.
------------------------------------------------------------------------
Summa summarum:
Each diagonal A073345(n+k,n) giving the number of rooted plane
binary trees of size n+k, and height n, (and correspondingly a
diagonal A073346(n+k+1,n) concerning the contracted heights) can be
computed from n > k onward with a twos power multiplied by a
polynomial of the kth degree (the leading term comes from the case
where k \/-nodes are grafted to separate places in the main trunk, in
a such way that none of them reach the top).
If one developed an automatic method of determining these
polynomials, then it would be nice to have a triangle
giving the coefficients of each. These are rational values,
but could be probably made integral by multiplying
by a k! or another appropriate value.
........................................................................