UNIVERSITY OF ILLINOIS LIBRARY Digitized by the Internet Archive in 2013 http://archive.org/details/enumerationsofor970ders 576- ft TJtU fto. f7<)UIUCSCS-R-79-970 Enumerations of Ordered Trees by Nachum Dershowitz and Shmuel Zaks \.j UILU-ENG 79 1717 June, 1979 D8iytSARY^ thfe JUN 2 9 1979 NIVEKSjfV OF ILLINOIS «ffi8AM^HAMP/U6* Th is ^lu me f s bo URBANA, ILLINOIS wh uod without no. 97^ ab/e. ho. ^UIUCSCS-R-79-970 COf>, <2v June, 1979 Enumerations of Ordered Trees by Nachum Dershowitz and Shmuel Zaks UILU-ENG 79 1717 Qfifhk J UN 2 9 1979 WNIVEHSjrv OF ILLINOIS DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN I IZTClkl Enumerations of Ordered Trees Dershowitz & Zaks ERRATA page 2, line -2: V •*■ L. page 6, line 14: mxn ■*■ nxn. page 7, Figure 3.5: (8,0) ■> (8,8). page 19, Example: R,(2) -»■ R,(2)=5. page 29, line 6, should be: A) We first prove that the number of inadmissible paths page 30, missing at end: By the observation in Section 3.2, the total number of paths from (0,0) to (n,n) with k corners is C)C )> while the total number of paths from (1,-1) to (n,n) with k corners is (,)(,) . It follows that K. K. page 31, figure: y=x+ -*■ y=x+£. Enumerations of Ordered Trees Nachum Dershowitz and Shmuel Zaks Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 61801 May 1979 Research supported under NSF Grant MCS77-22830. ->/V oL ABSTRACT We deal with the class T of ordered trees with n edges. n Several enumeration problems concerning T and some of its combinatorial properties are studied. Closed-form expressions for the following enumerations are given: (1) the number of trees in T with k leaves, (2) the number of nodes in T n n with d sons, and (3) the number of nodes in T on level I with d sons. n 1. INTRODUCTION Mathematical trees (as well as their natural counterparts) come in a variety of forms. There are rooted trees and unrooted ones; some rooted trees are ordered, others are not; some trees come with labels, others do not. And there are restricted classes of trees, e.g. binary, full binary, k-ary, complete k-ary, etc. In this paper we concentrate on unlabelled ordered trees with no restrictions on the degrees of the nodes, and study several combinatorial properties of this class of trees. For the class T of all ordered trees with n edges, the following enumeration functions are defined: 1. L (k) = number of such trees with exactly k leaves. n 2. V (d) = total number of nodes of degree d in these trees. n ° 3. R (r) = number of such trees in which the root has degree r. 4. N (£,d) = total number of nodes of degree d that reside on n level I in these trees. The next section presents the basic definitions and several one-to-one correspondences among ordered trees and other combinatorial objects that are used in subsequent sections. In Section 3 we investigate the functions L, V , R; we show that 1. L (k) = - 0, then 1 I m — t = is also an ordered tree. The trees t, ,t„,...,t are subtrees of the LI m distinguished node — called the root of t — connecting them. The roots of the subtrees are sons of the root of the tree. The trees are ordered in the sense that the order among subtrees (or sons) is significant. With each node x in a tree t we associate two values: its degree and level. The degree of x is the number of sons it has, and the level of x is its distance (the number of edges separating it) from the root of t. A node of degree is termed a leaf , otherwise it is called an internal node. The root is the only node on level 0. (See Figure 1.) 2.2 Correspondences Let T (n >_ 0) denote the set of ordered trees with n edges. As can be seen in Figure 2, the sizes of these sets form a series 1,1,2,5,14,42,... . These are the well-known Catalan numbers C : n | T | « C = 4H 2n ) 1 n ' n n+1 n (see, for example, Gardner [1976]). level b - - f - -g - level 1 c - -d - - - h ----- - level 2 level 3 internal nodes leaves (nodes of degree 0) f of degree 1 ( of degree 2 l^ of degree 3 root (level 0) level 1 level 2 level 3 c,e,f ,i d,g,h b a a b,f,g c,d,h e,i Figure 1. An ordered tree with eight edges V I . t { A AM A A AA A A A A A A A-. Figure 2 . T = {ordered trees with n edges} 6 There are numerous one-to-one correspondences between elements of these sets of ordered trees and other combinatorial objects (see Kuchinski [1977]). Among them, the correspondences between the following sets will help in our enumerations: T : the set of ordered trees with n edges, n P : the set of legal sequences of n open and n close parentheses. A parenthetic expression is called "legal" if each open parenthesis has a matching close parenthesis. I : the set of dominating sequences of n+1 nonnegative n integers (a . ) , such that E a. = n and J ° j=0 J i E a. _> i f° r a H i> £ i £ n. j=o J ■ L : the set of admissible paths from the point (0,0) to (n,n) in n an mxn lattice. All steps in a lattice path are either up or to the right; a path is "admissible" if it does not pass below the diagonal y = x. B : the set of full binary trees with n internal nodes, n An ordered tree is "full binary" if all nodes are either of degree (a leaf) or 2 (has a left son and a right son) . The correspondences between these five sets are described below and illustrated in Figure 3 using a tree t e T ft (Figure 3.1) and its reflection t* e T Q (Figure 3.2). We shall alternate between the two o trees t and t* for a reason that will become apparent later. T *-»" P , I : Given a tree t c T , traverse it in preorder n n n n' * (visit the root, then traverse its subtrees from left to right), writing an open parenthesis for each edge passed on the way down and a close parenthesis for each edge passed on the way up. For the tree t in t = 3.1 An ordered tree t. P(t) = (()(()))()((())) 3. 3 A legal parenthetic expression. t* = • • 3.2 Its reflection t*. i(t*) = 311002100 3.4 A dominating sequence of nonnegative integers. a(t) = (0,0) 1 ( ) ) y i ( ( ( y ( ) ) y ( ) .. , i—-.- 18, P) £'(t*) = (0,0) /o 1 /2 1 1 (8,8) 3. 5 An admissible lattice path corresponding to p(t). b(t) = U u/^ vU R A R \u IL \ R ?" R R / JJ R R R 3. 7 A full binary tree corresponding to l(t) 3. 6 An admissible lattice path corresponding to i(t*). b'(t*) = R R 3.8 A full binary tree corresponding to £'(t*) Figure 3. Correspondences between T , P , I , L , and B . — n n n n n Figure 3.1, this yields the legal parenthetic expression p(t) e P Q shown o in Figure 3.3. Similarly, if the degree of each node in t* is recorded on the way down, then the dominating sequence i(t*) c I shown in Figure 3.4 o is obtained. In general, if t. ,t„,...,t are the subtrees of a tree t, then l Z m p(t) = (p(t 1 ))(p(t 9 ))...(p(t )) and i(t) = m i (t. ) i (t_) . . . i(t ). l i m 1 / m P , I -*->■ L : Lattice paths may be easily obtained from sequences n n n ^ of parentheses or integers. Given a legal parenthetic expression p e P , we n start at (0,0) and go up one coordinate for each open parenthesis and go right one coordinate for each close parenthesis. This yields a path £(t) that remains in the upper left half of the lattice and ends at (n,n) . Alternatively, given a dominating sequence i e I , the function £' defines n an admissible lattice path by letting each integer in i determine the number of coordinates to move up before moving right one coordinate. The paths £(t) in Figure 3.5 and &'(t*) in Figure 3.6 may be obtained in such a manner from Figures 3.3 and 3.4, respectively. L -«-v B : Given an admissible lattice path I e L corresponding n n n to an ordered tree t e T , a unique full binary tree b(t) e B is n n constructed in the following manner: Build the binary tree in preorder, each step up on the path corresponding to an internal node and each step to the right corresponding to a leaf. A final leaf must be added. In the same manner, the function b' defines a full binary tree based on the path £'. See Figures 3.7 and 3.8. By this construction, if t = then b(t) = (note that this is the same as the full binary tree obtained from the binary- tree representation given in Knuth [1968], Section 2.3.2). while b'(t) = 10 It follows by induction that First Reflection Lemma: The ordered trees t, t* e T are n reflections of each other, if and only if the full binary trees b(t), b'(t*) £ B are reflections of each other, n For example, the ordered tree t* in Figure 3.2 is the reflection of the tree t in Figure 3.1, and the full binary tree b r (t*) in Figure 3.8 is the reflection of the full binary tree b(t) in Figure 3.7. Each of the above correspondences is one-to-one and can be used in either direction. Four properties follow directly from these correspondences, and are summarized in the following: Characterization Lemma : (1) The number of leaves in a tree t = the number of Q_ patterns in p(t) = the number of corners (i.e. path segments of the form J ) in £(t) = the number of left leaves in b(t). (2) The number of internal nodes in a tree t = one more than the number of (J^ (or equivalent ly )_)_) patterns in p(t) = one more than the number of • (or equivalently • — • — • ) path segments in £(t) = the number of right leaves in b(t). (3) The number of nodes of degree d in a tree t = the number of occurrences of d in i(t) = the number of vertical path segments of length exactly d in fc'(t). 11 (4) The number of nodes of degree d in all the trees in T t> n = the number of occurrences of d in all the sequences in I n = the number of occurrences of runs of exactly d (J s (or equivalently d )'s) in all the expressions in P . — n 2.3 The Cycle Lemma A sequence p of open and close parentheses is called a legal prefix if it is a prefix of a legal parenthetic expression, but neither p nor any initial segment of p is a legal parenthetic expression. In other words, a prefix consisting of n _('s and m )_'s, n > m, is legal if at any point within the prefix the number of _('s to the left is greater than the number of Vs. For example, ((()(() is a legal prefix; )((()( and ()(()(( are not. The following lemma has been rediscovered a number of times; it is a powerful tool in enumeration arguments. (See Zaks and Dershowitz [1979] for a history and proof.) Cycle Lemma (Motzkin [1948]): For any sequence p p ...p of n open parentheses and m close parentheses, where n > m, there exist exactly n-m cyclic permutations P j P j+r-' P mfn P r-' P j-l that are legal prefixes. For example, of the six cyclic permutations of the sequence )((()( , only two are legal prefixes: ((() (() and (() (() (. 12 We can use this lemma to determine the number of admissible lattice paths f(i,j) from (0,0) to (i,j). The obvious recurrence for the function f is: n if i = o f(i,j) = I If j < i f(i,j-l) + f(i-l,j) otherwise. Each admissible path corresponds to a legal prefix of j+1 open parentheses and i close parentheses: just drop the first open parenthesis in the prefix (the resultant sequence is still a prefix of a legal parenthetic expression, though it may itself be a legal expression) and construct the corresponding lattice path. The total number of ways to arrange the i+j+1 parentheses on a line is ( ) ; by the Cycle Lemma, exactly ...... of these 1 j+i+1 arrangements are legal. Hence, the total number of legal sequences is f(i,j) = 4^^ ( j+i+1 ) = ^r^ ( i+j ). If i=j, then we get the Catalan J j+i+1 i j+1 i 1 * numbers — r ( . ). (See Figure 4.) 13 6 20 48 90 132 132 5 14 28 42 42 /o 4 9 14 14 / 3 5 5 / 2 2 / ° 1 / ° i- » 1 n i < V— 1 » i 1 1 1 ► (0,0) Figure 4 . The lattice function f(i,j) 14 3. L_(k), P , (d), and R (r) _ n n n 3.1 Introduction In this section we study the number L (k) of trees with n edges and exactly k leaves, the number V (d) of nodes of degree d among the trees with n edges, and the number R (r) of trees with n edges and root- degree r. Our main results are closed-form expressions for these numbers. Some consequences and additional statistical properties of T are discussed . 3.2 I (k) — n The following closed-form expression for L (k) was given by Narayana [1959] in connection with partial orders on partitions: Theorem 1: The number L (k) of ordered trees with n edges and n k leaves is L n (k) " n ( k )( k-l } = k ( k-l )( k-l } = nTT ( k-l )( k } ' Examples : Of the 14 ordered trees with 4 edges, L,(2) = 6 have 2 leaves and L . (3) = 6 have 3 leaves. (See Figure 2.) We present here a new combinatorial proof of this result. The proof makes use of the correspondence between trees and admissible lattice paths along with the following observation: the number of lattice paths (admissible or not) from (0,0) to (m,n) with exactly k corners is • To see this, choose k x.'s such that <_ x < x < . . . < x^ < m and k y.'s such that < y, < y„ < . . . < y, < n; the k corners are at the i 7 1 '2 -'k — points (x.,y.). If in addition we insist that x = (the first corner 15 is on the leftmost column) and y, = n (the last corner is on the uppermost row) , then the number of such paths is ( m )( n ) . Proof: The number of trees in T with k leaves is equal to the n number of admissible lattice paths from (0,0) to (n,n) with k corners (Characterization Lemma) , which in turn equals to the number of lattice paths from (0,-1) through (0,0) and (n-l,n) to (n,n), with k corners, that do not cross the diagonal y = x other than at (0,0). By the Cycle Lemma, of the k possible cyclic arrangements of a given lattice path from (0,-1) through (0,0) and (n-l,n) to (n,n), with k corners, exactly one does not cross y = x. By the previous observation, the total number of such paths is C_-i)(v. -t ) ; thus L n«-k-i>Ci> • An alternative lattice-path proof of this theorem is given in the appendix. 3.3 Expected Number of Leaves From Theorem 1 it follows that L (k) = —(,)(, , ) = L (n+l-k) , which n n k k-1 n proves Theorem 2: The number of trees in T with k leaves is equal to n the number of trees in T with n+l-k leaves. n Corollary 2.1 : The expected number of leaves in a tree in T is — r— ; the expected number of internal nodes is also — — . 16 in T is n n+1 Corollary 2.2 : The expected degree of an internal node in a tree 2n We present two additional proofs of Theorem 2; they are both direct and constructive. The two proofs are then related to each other by a second reflection lemma. Second Proof : Consider the following recursively defined one-to-one correspondence within T between trees with k internal nodes (i.e. n-'-l-k n leaves) and trees with k leaves: t = where t ',t ',..., t' are the trees corresponding to the m subtrees of t. Every internal node x in the tree t corresponds to a leaf x' in the tree t' and vice-versa. D Third Proof : We define a one-to-one correspondence between trees with k leaves and trees with n+l-k leaves in three steps: given a tree t e T with k leaves, the corresponding full binary tree b(t) e B has k left n n leaves and n+l-k right leaves (by the Characterization Lemma). Thus, the reflection of 17 b(t) has n+l-k left leaves, corresponding to a tree t' e T with exactly n+l-k leaves. □ We extend the First Reflection Lemma of Section 2.2 with a Second Reflection Lemma : Two ordered trees t and t' correspond to each other in the manner of the second proof (above), if and only if the full binary trees b(t), b(t') e B are reflections of each other. Proof: Behold! second proof < > I t) - = b(t') 18 Note that the third proof uses the three correspondences t «-> b(t) ■*-> b(t') «-> t', whereas the second proof uses the short-cut t ■*•*■ t' . 3.4 V (d) and R (r) — n n In this subsection we present closed-form expressions for V (d) — the number of nodes in T of degree d, and R (r) — the nuinber of n n n trees in T with root of degree r. n Theorem 3: The total number V (d) of nodes in T of degree d is n n V (d) - C 2 "" 1 ^) . n n-x Ex ample : There are V . (1) = 20 unary nodes in the trees in T. . (See Figure 2.) Proof : V (d) = the total number of runs of exactly d )'s in the n — parenthetic expressions in P (Characterization Lemma) n = the total number of runs of exactly d ]_'s on cycles of n+1 _('s and n ]_'s (Cycle Lemma) = the number of ways to arrange n-1 _('s and n-d )_' s on a line (that is what remains after placing () ( on the cycle) ,n-l+n-d. _ .2n-l-d. K n-1 ; " K n-1 '" Note that if an expression contains t occurrences of ) , it will be counted exactly t times, as desired. Q Corollary 3.1 : The expected number of nodes of degree d in a tree • m ij u ^ n+1 , n+1 in T lies between — t— - and — r- . n „d+l „d 19 f) (a\ /2n— 1— dv p f " < n-1 ; _ n(n-l)...(n-d+l)n f ... £±°°L- c " x 2n , ' 2n(2n-l)...(2n-d+l)(2n-d) ^ n+i; * ^T ( n ) This is bounded from above by (-r-) • (n+1) = — -r- and from below by 2 1 A d / .in n+1 _ 2n" ( 2 } n(n+1) = IS ' D This demonstrates the extreme rarity of nodes of high degree: the expected number V (k) , , n+1 , ,. , n v n+1 < of nodes of degree = Z — < „d+l - w " "~™ — »wo*ww « c ,_ 1 2 not less than d k>d n 2 Theorem 4: The number R (r) of trees with n edges and root of n ° degree r is n n n-l Example : ^/(2) of the 14 trees in T, have a root of degree 2. (See Figure 2.) Proof: Suppose a tree t e T has a root of degree r. Then the n ° lattice path V (t) begins with (0,0) ■*• (0,r) ■»■ (l,r) (see Section 2.2). The number of admissible paths (l,r) ■> (n,n) is equal to the number of admissible _i_ /n an / n r-l+l / 2n-l-r N r / 2n-l-r. . _ .. „ „ N n paths (0,0) ■*■ (n-r,n-l): — r— r( ) = — ( .. ) (see Section 2.3). u n-1+1 n-r n n-l Note that R (r) = — P (r) , i.e. exactly — of the ( . ) nodes of degree r n n n J n n-l in T are roots, n Corollary 4.1 : The expected root degree of trees in T is n n+2 Proof : We must evaluate E r R (r) ± I r 2 ^ 1 ^) r=0 n n r=0 n " 1 T C n 1 n But z r ( ) = — — ( ) (this may be derived from the formula r=0 20 t > and I, s > 0; see Knuth [1968]) _ , x, m Jt+m+l — — — 0 n-£ (4) W n+1 (0,0) = 0. Together, they form a recurrence relation (1) in the three variables n,£, and d and boundary conditions (2,3,4), thus defining W (£,d) for all n, I, d 2l 0- Note that n and £ are increasing while d is decreasing. (The reader should convince himself that the boundary conditions suffice.) (1) Let x be a node with d sons on level £+1 of some tree in T . 22 If x has an older sibling (to its left) , then the following correspondence holds between x and a node x' with one more son (and therefore at least one son) on the same level in another tree in T : n < > All the s ub trees / a\ , / b\ , et level £+1 c. in this proof are arbitrary, b. If x has no older sibling, then it corresponds to a node x' with an additional son one level up in some (perhaps the same) tree in T : n level £ - _ level £+1 Since x either has an older sibling (a) or does not (b) , and the above correspondences are one-to-one, it follows that W (£+l,d) - N (£+l,d+l) + W (£,d+l) . n n n (2) We prove, more generally, that W n+1 (£,d+l) = W n+1 (£,d+2) + W n (£,d) Let x be a node with d+1 sons on level £ of some tree in T n+1' 23 If x has at least one grandson from his eldest son, then it corresponds to a node x' with an additional son (and therefore at least two sons) on the same level in another tree in T , , : n+1 - - - level £ b. If x's eldest son is childless (a leaf), then it corresponds to a node x' with one less son in a tree with one less edge: level I Since x's eldest son either has children (a) or does not (b) , and the above correspondences are one-to-one, it follows that W ^U,d+1) = N ,.,(£, d+2) + W (£,d) . n+l nH-l n (3) Clearly, it takes at least I edges to reach level £, leaving no more than n-Ji edges for the rest of the tree. So, if the degree of a node x on level I is n-£, we have the single possibility: 24 ) £ edge; — — - - - level I n-i leaves (4) Obviously the root must be of degree greater than zero if there is at least one edge in the tree. e- -u r „• 2M-d ,2n-d. , . c . Since the function j ( ) also satisfies the recurrence Zn— a n+x. relation (1) together with the boundary conditions (2,3,4), it follows that WU,d) = |«±f ( 2n " d ) . n 2n-d n+i n Recall that the function f(i,i) ■ ...., (" . ), used at the end j+i+1 l of Section 2 to yield the number of admissible lattice paths from (0,0) to (i,j), was based on the recurrence f(i,j) = f(i,j-l) + f(i-l,j) with the boundary conditions f(0,j) = 1 and f(i,j) = if j < i. It turns out that »i /a ,\ 2£+d/2n— d. ,. , , . , „ x N (l,d) =-Z—T( n . ) = f(n-d-l,n+l) . n zn-d n+£ With this in mind, it is easy to construct a Pascal-like half-triangle (Figure 5) giving the values of W. 25 14 28 20 v 7 42 48 27 > 8 /* * /* 7< fi \ 12 3 4 ree V*_ J level N (2,1) -|(J) - 5 Figure 5 . W U,d). 26 Each entry in the triangle is the sum of the two entries above it. Also, W (£,d) = W J _.(H-l,d+2) = W ,(£+1,01-2) = ... . n n+1 n-1 Together, these two facts yield various relations among the values of W, e.g. W (£,d) + W (£+l,d) = N in (£,d+l) . n n n+1 Some consequences of this theorem are: Corollary 5.1 : The number of leaves in T residing on level £ . £, 2n . is — ( .) n n-Jr Proof : M(£,0) = £( 2n ) . n n n-£ Corollary 5.2 : The number of internal nodes in T residing on . „ . 1+1, 2n . level £ is ( „ , ) . n n-£-l Proof: We have seen (Property (1)) that W (£+l,d) = N (£+l,d+l) + W (£,d+l) ; n n n thus, N (£,d+l) = N (£+l,d) - N (£+l,d+l) n n n Hence, n E N (£,d) = M (£+1,0) - W (£+l,n) = W (£+1,0) , . n n n n a=l 2£+2. 2n = £+1. 2n . _. 2n ^n+£+i ; n ^n-£-i ; ' Corollary 5.3 : The total number of nodes in T residing on level £ . 2£+l / 2n+l N 1S 2n+T ( n-£ } ' 27 Proof: n n £ N (£,d) = M (£,0) + E N (£,d) = N (£,0) + N (£+1,0) = N ^(i.l) . _ n n , n n n n n+l d=U d=l 2£+l ,2n+l. 2n+l^ n-£ ; * D Alternative lattice-path arguments for these results are given in the appendix. Corollary 5 . 4 : The total number V (d) of nodes of degree d in T n fo n . ,2n-l-d N Proof: v (d) = z n (£,d> = i f^( 2n ~ d ) = i 2(n+£) - (2n - d) c 2n - d ) £>0 n £>0 a** 1 *"' £ > 2n " d '*+*' £>0 - * [( 2 r:i d '-( 2 ;;v d )] - < 2n „:r> • £>0 Corollary 5 .5: The number of trees R (r) in T with root of n n , . r / 2n-l-r. degree r is — ( .. ) . n n-1 Proof : Since the number of such trees equals the number of roots of degree r, we have R (r) = N (0,r) = - ( ) = — ( , ). n n n 2n-r n n n-1 " The last two results have already been independently and directly proved in the last section. 28 DISCUSSION We have investigated various enumerations of the class T of n ordered trees with n edges. Our main result was the closed-form expression -r — j( ) for the number W (£,d) of nodes of degree d on zn— a n+x, n level I in trees in T . Other results were derived from this formula, n to some of which we also gave independent direct proofs. In searching for closed-form expressions, we made considerable use of computer-generated data and of the handbook of sequences by Sloane [1973]. 29 APPENDIX In this appendix we give alternative lattice-path proofs for the A) number L (k) of trees in T with k leaves (Theorem 1) and B) for n n the total number of leaves and of internal nodes on level £ in T n (Corollaries 5.1 and 5.2). A) A more general result is proved: the number of illegal paths from (i,j) to (n,n), with k corners, where <_ i <_ j <_ n, is equal to the number of paths from (j+l,i-l) to (n,n) with k corners. Note that the point (j+l,i-l) is symmetric to the point (i,j) with respect to the line y = x-1. The proof is by induction on the number of corners, k. Consider the illegal paths from (i,j) to (n,n) with k _> corners that begin with (i,j) -> (i',j) -* (i',j+l), where i' > j. They are in one-to-one correspondence with the paths beginning with (j+l,i-l) ■*■ (i',i-l) -> (i',j+l) and continuing with the same k corners to (n,n): (n,n) (This serves as the base case of the induction.) 30 Now consider those inadmissible paths from (i,j) to (n,n) with k > corners that begin with (i,j) "* (i'-l.j) ■* (l'-l.J 1 ) "*" (i',j')> where i' - 1 <. j < j 1 . They are in one-to-one correspondence with the paths from (j+l,i~l) to (n,n) with k corners beginning with (j+l,i-l) ■*■ (j',i-l) ■* (j*,i'-l) ■* (j'+l,i'-l), since, by the inductive hypothesis, the number of inadmissible paths from (i',j') to (n,n) with the remaining k-1 corners is equal to the number of paths from (j'+l,i'-l) to (n,n) with k-1 corners: (i,j) (i'-l,j) (j',i'-l) (n,n) (j'+l,i'-l) a+1 b-1 (j+1,1-1) (j',i-D 31 B) Recall that a leaf is characterized by a corner in the lattice path (Characterization Lemma). Accordingly, a leaf on level i corresponds to a corner on the £-th diagonal above y = x, i.e. a path segment (i,i+£-l) -> (i,i+£) ■> (i+l,i+£): (n-£,n) y=x+ (n,n) (0,0) Recall further (Section 2.3) that the number of legal paths from (0,0) to (i,j)~ denote that by [ (0,0)->(i, j) ]— is j T^ 1 ( 1+ j ) . Thus, number of leaves on level 2. n-Z = I [(0,0) + (i,i+£-l)].[(i+l,i+O->(n,n)] i=0 =E [(0,0)-Ki,i+Jl-l)] •[(0,0)-Kn-i-£,n-i-l) (by symmetry) SrkP i ' n-i^ n-i-l 32 n l £ f l+2± \ l /2n-2i-£. * £+2i C i ' 2n-2i-£ (l n-i ' = £ 2n n^n-£ ; ' using the identity (see, e.g. Knuth [1968], §1.2.6, Eq. (31)) r .r-kt. s ,s-mt+kt>, _ r+s ,r+s-mt. , A r-kt k s-mt+kt m-k " r+s-mt ^ m ' ' k=0 where m >_ and r ^ kt ^ s for < k £ m , with i, £, £, -2, and n-£ substituted for k, r, s, t, and m, respectively. Similarly, since an internal node on level i is characterized by a vertical crossing of y = x+£, we have n-£ number of internal nodes „ r , n _ x ,. , . . , N , r , . . ,. , on level £ = Z [ (0,0)-v(i,i+£-l) ]• [ (i,i+£+l) + (n,n) ] i=0 _2^ r 2i+£-l £+2 2n-2i-£-l> JH-i*- i ) n-i+l ( n-i-£-l ; U ~ l i+1 ( i+2± i+2 2n-2i-£. . n £+2i (l i ; 2n-2i-£ C n-i+1 ; i=0 £+1 2n n n v n-£-r ' 33 REFERENCES M. Gardner [June 1976] , Mathematical Games: Catalan Numbers , Scientific American, vol. 234, no. 6, pp. 120-125. D. E. Knuth [1968], The Art of Computer Programming , vol. 1: "Fundamental Algorithms," Addison-Wesley , Reading, MA. M. J. Kuchinski [May 1977], Catalan Structures and Correspondences , M.S. Thesis, Dept . of Mathematics, West Virginia Univ., Morgantown, WV. Th. Motzkin [April 1948], Relations Between Hypersurface, Cross Ratios , and a Combinatorial Formula for Partitions of a Polygon, for Permanent Preponderance, and for Non-associative Products , Bull. AMS, vol. 54, pp. 352-360. T. V. Narayana [1959], A Partial Order and its Application to Probability , Sankhya, vol. 21, pp. 91-98. F. Ruskey and T. C. Hu [1977], Generating Binary Trees Lexicographically , SIAM J. Computing, vol. 6, no. 4, pp. 745-758. N. J. A. Sloane [1973], A Handbook of Integer Sequences , Academic Press, New York, NY. S. Zaks and N. Dershowitz [1979], The Cycle Lemma and Some Applications , in preparation. BIBLIOGRAPHIC DATA SHEET 1. Report No. UIUCDCS-R-79-970 3. Recipient's Accession No. 4. Title and Subt itle Enumerations of Ordered Trees 5. Report Date June, 1979 7. Author(s) Nachum Dershowitz and Shmuel Zaks 8. Performing Organization Rept. No. 9. Performing Organization Name and Address Department of Computer Science University of Illinois Urbana, IL 61801 10. Project/Task/Work Unit No. 11. Contract /Grant No. NSF MCS77-22830 12. Sponsoring Organization Name and Address National Science Foundation Washington, DC 13. Type of Report & Period Covered 14. 15. Supplementary Notes 16. Abstracts We deal with the class T of ordered trees with n edges. Several enumeration problems concerning T and some of its combinatorial n properties are studied. Closed-form expressions for the following enumerations are given: (1) the number of trees in T with k leaves, (2) the number of nodes in T with d sons, and (3) the number of nodes in T on level I with d sons n n 17. Key Words and Document Analysis. 17a. Descriptors ordered trees, tree enumeration 17b. Identifiers/Open-Ended Terms 17c. COSATI Field/Group 18. Availability Statement FORM NTIS-35 (10-70) 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 33 22. Price USCOMM-DC 40329-P7I m 2 o n