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.

........................................................................