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