Digitized by the Internet Archive 
 in 2013 
 
 http://archive.org/details/onorderingenumer850troj 
 

 ■ 
 
 UIUCDCS-R-77-850 
 
 / J 
 
 ( 
 
 UILU-ENG 77 1706 
 
 February, 1977 
 
 ON THE ORDERING, ENUMERATION AND 
 RANKING OF k-ARY TREES 
 
 by 
 Anthony E. Trojanowski 
 
 ■ At Ubrwy of trie 
 
 APR 12 1977 
 
 University of Illinois 
 
UIUCDCS-R-77-850 
 
 On the Ordering, Enumeration and 
 Ranking of k-ary Trees* 
 
 Anthony E. Trojanowski 
 
 Department of Computer Science 
 University of Illinois at Urbana-Champaign 
 Urbana, IL 61801 
 
 February 1977 
 
 This work was supported in part by the National Science Foundation under 
 Grant Numbers DCR 74-02774 and MCS 73-03408, 
 
§1. Introduction : The main problem of classical combinatorics may be 
 described us follows: given a finite set X, evaluate N ■ |x| . Evaluation 
 of N implicitly defines N! set isomorphisms 
 
 *>: X * {0, 1, ... , N-l}. 
 Any choice of such a V induces a total order < on X, 
 
 x < y iff <£(x) < <p(y). 
 
 <fi is thus an order isomorphism between the ordered sets (X,< ) and {0, 1, 
 
 ... , N-l} with, the usual ordering. 
 
 With X and N as above, a somewhat different problem may be defined: 
 
 impose a total order < on X and construct an order isomorphism 
 
 x 
 
 *>:(X,< X ) + {0, 1, ... , N-l}. 
 
 Such a function is a ranking function on X with respect to < . Clearly «P is 
 
 unique, and also, for x e X 
 
 *>(x) = |{y e X: y < x X} | . 
 
 A converse problem may be defined: given X, < , N as above, compute <£ 
 
 In this paper, X will be the set of k-ary trees on n vertices, 
 
 k > 2, n _> 0. 
 
 1.1 Definition [k-ary tree] : Let k be an integer, k ^_ 2. 
 
 (i) <J>, the empty tree, is a k-ary tree with no root and with vertex 
 
 set V(<}>) = <}>; 
 (ii) if T , ... T are k-ary trees, then structure produced by joining 
 a new root r to the root of each non-empty T , 1 < j < k, is a 
 
 < 
 
 k-ary tree with root r and vertex set {r} U V(T ) U ... U V(T ) ; 
 (iii) there are no other k-ary trees. 
 
1.2 Definition [Subtree rooted atv] : Let T be a non-empty k-ary tree with 
 T 1 , ... , T k as in Definition 1.1 (ii) . Let v e V(t) . (i) If v = r, the su • 
 tree of T rooted at v is T; (ii) Otherwise, v e V(T.) for ycftne j , 1 < j < 
 
 and the subtree of T rooted at v is the subtree of T. rooted at . 
 
 1.3 Defintion [Parent, child, etc.] ; Let T be a non-empty k-ary tree, v e V( , 
 
 T the subtree of T rooted at v, with T -, ... T . as in Definition 1.1 (ii). 
 v vl' vk 
 
 The root of each non-empty T # is child of v, and v is the parent of such a 
 
 root. WeT is a descendent of v, and v is a ancestor of w. If w 4= v, the 
 
 descendant and ancestor relations are proper. A vertex with no proper descen 
 ants is a leaf. A vertex which is not a leaf is internal. 
 
 1.4 Definition [isomorphism] ; Let T , T be k-ary trees, 
 (i) If T = T = 4>, T and T 2 are isomorphic. 
 
 (ii) If T and T are non-empty and T , ... , T , T , ... T are as 
 
 in Definition 1.1 (ii) , T., and T„ are isomorphic iff T, . and T„. ar< 
 
 12 lj 2j 
 
 are isomorphic, 1 <_ j <_ k. 
 
 1.5 Definition [Full k-ary tree] ; A k-ary tree T is a full k-ary tree iff 
 (i) T is non-empty; and 
 
 (ii) each internal vertex of T has exactly k children. 
 
 There is a relationship between k-ary trees and full k-ary trees 
 given by the following lemma. 
 
 1.6 Lemma : The set of k-ary trees and the set of full k-ary trees are in 1-1 
 correspondence. 
 
 Proof: The correspondence is defined as follows: 
 
(i) 4> corresponds to the full k-ary tree with one vertex; 
 (Li) A non empty k-ary tree T corresponds to the ful] k-ary tree T' obtain- 
 ed from T by adding leaves to T so that every vertex of T has exactly 
 k children in T' . 
 
 It is clear that this correspondence is 1-1. 
 
 q. e. d 
 
 This correspondence is an obvious extension of the special case 
 k = 2 which is presented on p. 559 of [K], 
 
 1.7 Definition [ m-Inorder Labeling]: Let T be a non-empty k-ary tree with 
 
 root r; for v e V(T) , let T be the subtree of T rooted at v and let T , 
 
 v vl, 
 
 T , be as in Definition 1.1 (ii) . If T . 4= (j>, let r. be the root of T . . Let 
 vk vj 2 V J 
 
 1 m — k- The following algorithm labels T in m-inorder. 
 begin 
 
 procedure inorder (v,m); 
 begin 
 
 for j: = 1 until m do 
 
 if T . 4 <J> then inorder (r . ,m ); 
 — vj j 
 
 label [ v] : = i : = i + 1; 
 for j: = m + 1 until k do 
 
 if T . = <J> then inorder (r . ,m) ; 
 
 end inorder (v,m); 
 : = 0; 
 
inovder (r,m); 
 end. 
 
 A search which visits the vertices of T in the same order in which they are 
 
 numbered by an m-inorder labeling is an m-inorder search. 
 
 The definition of m-inorder labeling may be extended to arbitrary 
 ordered trees, but this extension is not necessary in this paper and so the 
 present definition is framed in terms of k-ary trees. 
 
 The cases m = o and m = k are the usual pre-order and post-order 
 labelings of T respectively; the case k = 2 and m = 1 is the usual in-order 
 labeling of a binary tree. See [A] for standard definitions of these 
 labelings. 
 
 Finally, to formalize the remarks at the beginning of this paper, the 
 next definition is made. 
 
 1.8 Definition [Ranking Function] : Let (X,<) be a finite, non-empty ordered 
 set with |x| = N. The unique order isomorphism <£: (X,<) ■*■ {0, 1, ... , 
 N - 1} is the ranking function for X with respect to the total order <. 
 
§11. Binary Trees; Ranking by Pre-Order Search : A binary tree is, of course, 
 a k-ary tree with k = 2. 
 
 2.1 Definition [B(n), B(n)]: Let n be a non-negative integer. Then 
 
 B(n) = {binary trees with n vertices}; 
 and 
 
 B(n) = |B(n)|. 
 
 Clearly B(0) = B(l) = 1. For n _> 2, we have 
 
 n-1 
 B(n) = 2 b(v) B(n-v-l); (2.2) 
 
 v=0 
 
 this follows Definitions 1.1 and 1.4. A generating function argument may be 
 
 applied to Equation 2.2 to obtain 
 
 B(n) - Jfc ( 2 n n ) , (2.3) 
 
 see §2.3.4.4 of [K]. 
 
 A total order on the set of all binary trees may be defined as 
 follows : 
 
 2.4 Definition [Pre-order Ordering] : Let T and T be binary trees 
 
 Then 
 
 1 l < T 2 iff 
 
 (i) T E B(n 1 ), T 2 e B(n 2 > with i^ < n^ or 
 
 (ii) I , T 2 E B(n) and, defining T n> T^ and 1^, T 22 according to 
 
 Definition 1.1 (ii) , T < T^ or T u = T^ and T^ < T 22 - 
 
 2.5 Lemma : Definition 2.4 defines a total ordering on the set of all binary 
 trees. 
 
 Proof: Clearly, it suffices to show that Definition 2.4 defines a 
 total ordering on B(n) for each n. But this is certainly the case for n = 0, 
 
6 
 1; and for n _> 2 the result follows by induction on n, using Definition 2.4 
 (ii) , and noting that n + n = n - 1. q.e.d. 
 
 The way is now clear to define the ranking function on B(n) with 
 respect to the pre-order ordering. 
 
 2.6 Definition [Pre-order ranking on B(n)]: Let T e B(n) . If n > 1 define 
 
 T and T according to Definition 1.1(11), with T e B(n ), i = 1, 2. Then 
 
 '\ n = ° (2.7) 
 
 <p (T) = ( 2 B(v) B(n-v-l) + V 0\) B(nJ 
 ]v-0 n l X 2 
 
 I + *> (Tj n > 1 
 
 ^ n„ I — 
 
 2.8 Lemma: <p is the ranking function on B(n) with respect to the pre-order 
 n 
 
 ordering. 
 
 Proof: By the remarks in §1, it suffices to show that 
 
 * n (T) = |{t' e B(n): t' < T> | , 
 where < denotes the pre-order ordering on B(n) . The proof is by induction 
 on n; the case n =0 is obvious. 
 
 Let n > 1. Let T» < T, with T », T ' as in Definition 1.1 (ii) . 
 It follows from Definition 2.4 (ii) that T ' <_ T . 
 
 Case I: T^ e B(v), v < n. There are n - 1 choices for v; for 
 
 each v, there are B(v) choices for T '; and for each choice of T ' there 
 are B(n-v-l) choices for T ' . Thus there are a total of 
 
 v 1 
 
 2 B(v) B(n-v-l) 
 
 occurrences of Case I. 
 
 Case II: T^ e Bd^), T ' < T ;L . By the induction hypothesis there 
 
 are V (T ) choices for T ' ; and there are B(n.) choices T ' . Thus there are 
 n l J 1 2 2 
 
a total of 
 
 tf (T) B(n ) 
 n. 1 l 
 
 occurrences of Case II. 
 
 Case III: T ' = T . Then T ' e B(n 2 > and T ' < T . By the 
 
 induction hypothesis there are <£ (T~) 
 
 n 2 
 
 occurrences of Case III. 
 
 Cases I, II, and III are mutually exclusive and exhaust the 
 
 possiblities for T' < T in B(n) 
 
 q.e.d. 
 
 Equations 2.7 provide the basis for an algorithm which computes </> n (T) for 
 
 T e B (n) . Assume that the vertices of T are labeled with the integers 1, 
 
 ... , n. The algorithm uses five arrays: lohild [l:rc], rohild [l:n], 
 
 b [0:n], d[0 :n] , phi [0 :n] . For 1 <_ v < n 3 lohild [v] is the label of the 
 
 left child of v if that child exists, and otherwise; rahild [v] is defined 
 
 similarly, b [j] = B(j), <_j <_n. d [v] is the number of descendants of 
 
 v } i.e. d [v] = |T | where T y is the subtree of T rooted at V, 1 <_ V <_ n. 
 
 2.9 Algorithm : Input: a non-empty binary tree T represented by the arrays 
 
 lohild [l:n], vohild [l:n]. Output: <P ^T) as defined by Equations 2.7. 
 
 n 
 
 begin 
 
 procedure rank (v) ; 
 begin 
 
 if lohild [v]~\=o then rank {lohild [v]) ; 
 
 if rohild [v]~\=0 then rank (rohild [v]) ; 
 
 d [v) : = d [lohild [v]) +d [rohild [v]] + 1; 
 t: - Oj 
 
for i: =0 until d [lohild [v] - 1] do 
 
 U - t + b [i] * b [d[v]-i-l]; 
 
 phi [v]: = t + phi [lohild [v]] * b [vohild [v]] + phi [rohild [v]]; 
 end rank (v) ; 
 
 d [0]: ■ phi [0]: = 0; 
 compute b [0:n] ; 
 ran/c (r) ; 
 end. 
 
 Note that the method by which the contents of b [0'-n] are computed 
 is left unspecified; this will be dealt with shortly. 
 
 It is evident that Algorithm 2.9 is a pre-order search of the 
 binary tree T with some additional computations; thus arises the name of 
 the total order under discussion. The computations themselves are a 
 straight-forward implementation of Equations 2.7. 
 
 The complexity of this algorithm is determined in the following 
 
 theorem. 
 
 2 
 2.10 Theorem ; Algorithm 2.9 is of 0(n ) time complexity and 
 
 0(n) space complexity. 
 
 Proof: The contents of b[0:n] may be computed using the recur- 
 sion 
 
 B(0) = 1; B(n) = 2(2n+l) B(n)/(n+2), n >_ 1. 
 The time required is 0(n). 
 
 As noted above, the algorithm is a pre-order search of the binary 
 tree T 
 
with some additional computations; these computations will determine the 
 time complexity of the algorithm. Let t(n) be this complexity as a 
 function of n. 
 
 From Algorithm 2.9, t(n) satisfies the recursion 
 t(n) = t(n ) + t(n 2 ) + 0(n ). 
 
 Assume for the moment that t(n) = 0(n ), a _> 1; then t(n) is convex. See 
 
 [R], p. 60 for a definition of convex function. It follows that 
 
 n n 
 
 t(n ) < -±- t(n-l) + -~ tCO^; 
 1 — n-1 n-1 
 
 and 
 
 hence 
 
 and thus 
 
 n n 
 
 t(n ) < -±r t(n-l) + -~- t(0); 
 I — n-l n-1 
 
 t(n) < t(n-l) + 0(n-l) 
 
 t(n) < 0(n 2 ) 
 
 On the other hand, if T is the binary tree with n vertices 
 satisfying 
 
 rohild [v] =0, 1 <_ v <_ n, 
 
 2 
 Algorithm 2.9 requires 0(n ) time to compute y (T) . Thus the time bound 
 
 n 
 
 is established. 
 
 The space bound is obvious. 
 
 q.e.d. 
 An example will illustrate the action of Algorithm 2.9 
 
 2.13 Example : Let T be the five-vertex binary tree shown in 
 Figure 2.13 (i). Algorithm 2.9 calls rank (r) ; rank (r) calls rank (s) 
 
10 
 
 recursively, and rank (s) calls rank (t) recursively. Since lahild [t] 
 = rehild [t] =0 » no recursive calls are made, and the computations in 
 procedure rank are executed. The results of these computations are 
 
 d [t] = 1, 
 phi [t] = 0. 
 These results are shown in Figure 2.13 (ii) as the ordered pair beneath 
 vertex t. The completion of rank (t) allows rank (s) to be completed; 
 the following computation are performed: 
 
 d [s]: =0+1+1+= 2; 
 phi [ s ] : = ; 
 the results are recorded in Figure 2.13 (iii) . 
 
 (0,2) 
 
 (0,2) 
 
 (0,1) 
 
 
11 
 
 (0,2) < X (0.2) (0,2) 
 
 2.13 Figure ; Successive stages in the computation of the rank of T. 
 The completion of rank (s) allows rank (r) to call rank (u) , which in 
 turn calls rank (v) . The resulting computations up to the conclusion of 
 rank (u) are similar to those just described, and the results are shown 
 in Figure 2.13 (iv) and Figure 2.13 (v) . The completion of rank (u) 
 allows the computations in rank (r) to take place; these computations 
 are: 
 
 d [r]: =2+2+1=5; 
 phi [r]: = b [0]*b [4] + b [l]*b [3] 
 + phi [s]*b [2] + phi [u] 
 =14+5+0+0= 19. 
 Hence T is the rank 19 binary tree with 5 vertices. 
 
 Now the converse problem will be considered; that is, given 
 n _> and m with <_ m <_ B(n) - 1, construct the rank m binary tree with 
 n vertices. The next algorithm solves this problem. 
 
 Before the presentation of the algorithm, some comments are 
 in order. The algorithm below works with the same four arrays as 
 Algorithm 2.9, except that the zero entries of d and phi are not used in 
 this algorithm. It is readily shown by a simple induction that the binary 
 
12 
 
 tree produced by this algorithm, represented by the arrays lahild [l:n] 
 and vahild [l:n]» is labeled in preorder. 
 
 2.14 Algorithm: Input: n > 0, m satisfying _< m _< B(n) - 1. Output: 
 The rank m binary tree with n vertices, represented by the arrays lahild 
 [l:rc], vdhild [l:rc], with the vertices labeled in preorder. 
 begin 
 
 procedure unrank (v ,a) ; 
 
 begin 
 
 if V _> 1 then 
 
 if a > 1 then 
 
 begin 
 
 U = 
 
 for j: = step 1 while phi [v] - t ^b [j] *b[e-j-l] do 
 
 t: = t + b [j]*b [c-j-1]; 
 if j = then lohild [v]: ■ o 
 
 else lahild [v]: = i: = i + 1; 
 
 if lohild [v] > 1 then 
 
 begin 
 
 cf [lohild[v]]: = j; 
 
 phi [lchiZd[y]]: = (p/ii[y]-t) diy fc [jk 
 
 end; 
 
 unrank (lehild[v], d[lahild[v]]) ; 
 
13 
 
 if j = a - 1 then rahild [v]: = 
 
 else rahild [v]: = i: = i + l; 
 
 if rahild [v] _> 1 then 
 
 begin 
 
 d [rahild [v]]: = c-j-1; 
 
 pfci [rahild [v]]: = (pH [y]-t) mod i [j]; 
 end ; 
 
 unrank (rahild[v] , d[rahild[v]]) ; 
 end; 
 
 else lahild [v]: = rahild [v]i =0; 
 end unrank (v,c) ; 
 
 i: = 1; 
 
 pfct [1]: = m ; 
 
 d [1]: = n; 
 
 compute b [0:n] ; 
 unrank (l,d[l]); 
 end 
 
 The complexity of this algorithm is analyzed in the next 
 result. 
 
 2 
 2.15 Theorem : Algorithm 2.14 is 0(n ) time-bounded and 0(n) space- 
 bounded. 
 
 Proof: Let t(n") be the time bound. The procedure call 
 
14 
 
 unrank (l,n) results in 0(n ) computations plus two recursive calls of 
 unrank. Thus, the function t(n) satisfies the recursion 
 
 t(n) = t(n ) + t(n 2 ) + Ofc^); 
 
 t(n) < 0(n 2 ) 
 
 q.e.d, 
 
 and thus 
 
 as in Theorem 2.10. 
 
 Substituting m = B(n) - 1 results in 
 
 t(n) > 0(n 2 ), 
 and the time bound is established. 
 
 The space bound is obvious. 
 
 An example will serve to illustrate the operation of the 
 
 algorithm. 
 
 2.16 Example ; Apply Algorithm 2.14 to the numbers n = 5, m = 19. At the 
 outset, the situation is that depicted in Figure 2.17 (i) ; a root vertex 
 labeled 1 with d [l] = 5, phi [l] = 19. These latter values are given 
 in parentheses. The first procedure call is unrank (1,5). The loop on 
 j computes d [lahild[l]]; in this case the value is 2, which is non- 
 zero, so Ichild [l] is assigned the label 2, and phi [2] is assigned the 
 value (Figure 2.17 (ii)). Since d [2] > 1, unrank (2,2) is called 
 recursively. The loop on j computes d [lehild[2]] = 0; hence d [rahild[2]] 
 = 1 and this vertex is labeled 3(Figure 2.17 (iii)). The recursive call 
 unrank (3,1) has no effect except setting rahild [3] and Ichild [3] to 
 zero. The recursive calls are completed, so the next computation is to 
 assign rahild [l] the value 4, d [4] the value 2, and phi [4] the value 
 
15 
 
 zero (Figure 2.17 (iv). unrank (4,2) is called, and computations proceed 
 as they did for the call unrank (2,2) (Figure 2.17 (v)-(vi)). 
 
 1 
 (5,19) 
 
 2 
 (2,0) 
 
 (v) 
 
 (vi) 
 
16 
 
 §111. Preorder Ranking of k-ary Trees : The development in this section is 
 exactly parallel with that of §11; hence many of the details will be omitted. 
 
 3.1 Definition [S(k,n), S(k,n)]: Let n be a non-negative integer, k >_ 2. 
 Then 
 
 and 
 
 S(k,n) = {k-ary trees with n vertices}; 
 
 S(k,n) = |s(k,n) |. 
 
 S(k,0) = S(k,l) = 1. For n > 2, we have 
 
 S(k,n) = 2 S(k,v 1 ) S(k,v 2 ) ... S(k,v k >; 
 
 v,+v~+ . . . +v. = n - 1 
 12 k 
 
 (3.2) 
 this follows from Definitions 1.1 and 1.4. A generating function may be 
 constructed from Equation 3.2; and application of other results to this 
 generating function yields 
 
 s(k - n) -o^r(n) : (3 - 3) 
 
 see p. 584 of [K]. An independent derivation of Equation (3.3) will be 
 given in §V below. It should be noted for later reference that the sum 
 
 ma 
 
 tion on the right of Equation (3.2) has ( j terms. 
 
 3.4 Definition [Pre-Order Ordering] : Let T and T be k-ary trees with 
 
 n and n~ vertices respectively; let T , ... , T , T , ... T be defined 
 
 according to Definition 1.1 (ii) . Then T < T iff 
 (i) n^^ <n 2 ; or 
 (ii) for some j, 1 < j < lc - 1, T u - T^ 1^ = T^, 
 
 ••• T i .1-1 " T 2j-r andT ij <T 2J - 
 
 
17 
 
 3.5 Lemma : Definition 3. A defines a total ordering on the set of all k-ary 
 trees. 
 
 Proof: Analogous to the proof of Lemma 2.5. q.e.d. 
 
 As in §11, Definition 3.4 may be used to define a ranking function 
 on S(k,n) . 
 
 3.6 Definition [Pre-Order Ranking] : Let T e S(k,n). If n > 1, define T , 
 T , ... , T according to Definition 1.1 (ii) , with T. e S(k,n ), 1 < i _< k. 
 
 i. K J X 
 
 Then 
 
 *,, (T) = 1 
 k, n 
 
 n = 
 
 ^S(k,v 1 ) ... S(k,v 1 ) ... S(k,v k ) 
 
 v.+v-+ . . . +v, = n - 1 
 12 k 
 
 v <n 
 1 1 
 
 + * (T.) [S(k,vj ... S(k,v.) 
 
 k,n 1 *- 2 k 
 
 v 2+ v 3+ . . . +v k = n - n x - 1 
 
 v 2 < n 2 
 
 + ... 
 
 k,n . i-1 »- i k 
 
 (3.7) 
 
 i-1 
 
 v. +v.., + ... + v. =n- n. - ... -n. n -1 
 l l+l k 1 i-l 
 
 v < n 
 
 i i 
 
 + . . . 
 
 k 
 
 n > 1 
 
 3.8 Lemma: *A is the ranking function on S(k,n) with respect to the 
 
 pre-order ordering. 
 
18 
 Proof: Straight-forward generalization of the proof of Lemma 3.8. 
 
 q.e.d. 
 Equations 3.7 provide the basis for ranking and unranking algorithms 
 analogous to Algorithms 2.9 and 2.14. These algorithms will not be presented 
 explicitly since they are straight-forward generalizations of the above 
 mentioned algorithms, and also because they are rather tedious to state in 
 detail. Nevertheless, since these algorithms are so similar to Algorithm 
 2.9 and 2.14, their complexity may be determined as in Theorems 2.10 and 
 2.15. 
 
 3.9 Theorem : The ranking and unranking algorithms based on Equations 3.7 
 have time complexity 0(n ) and space complexity 0(kn). 
 
 Proof: The computation of S(k,v) requires 0(v) time; hence the 
 
 2 
 computation of S(k,0), ... S(k,n) requires a total of 0(n ) time. 
 
 Let t(n) be the time bound; suppose that t(n) = 0(n ), a >_ 1. 
 
 In Equations 3.7, denote by £ the first summation, and by 2 the coefficient 
 
 of iflc, n ± (T ± ). Then 2 q has at most ( T^ 2 )) = 0(n k_1 ) terms, and 1 ± 
 
 //n-n - ... - n -2\\ _. k-i-l N 
 
 ( ( 1 i <_ 0(n ) terms. 
 
 has at most 
 
 Thus 
 
 k 
 
 t(n) : 2 ( t (n ) + 0(n k_i )) 
 i=l 
 
 Since n is convex for a > 1, 
 
 hence 
 
 and thus 
 
 n n-n -1 
 
 t(n i> <S=rt(ii-l) ^t(O); 
 
 k u A 
 t(n) < t(n-l) + 2 0(n 1 ) 
 
 1=1 
 
 t(n) < 0(n k ) 
 
19 
 
 On the other hand, if T e S(k,n) has the property that for each v e V(T), 
 T = $ for k > 2, it is easy to see that the ranking algorithm requires 
 0(n ) time to compute the rank of this tree. Hence 
 
 t(n) > 0(n k ) 
 
 and the time bound is established. 
 
 The space bound for the ranking algorithm is clear. 
 
 The analysis of the unranking algorithm is simlar. 
 
 q.e.d. 
 
 Thus the complexity of the ranking and unranking algorithms are 
 exponential in k. In the next two sections, alternative ranking schemes 
 will be developed which avoid this difficulty. 
 
20 
 
 §IV. Lexicographic Ranking of Binary Trees : The discussion starts with a 
 
 definition. 
 
 4.1 Definition [Permutation]: Let n be a positive integer. A permutation 
 
 a of 1, 2, . . . , n is a finite sequence s s ... s satisfying 
 
 {s n , . . . , s } = {1, ... , n} . 
 1 n 
 
 The set of all permutations of 1, 2, ... n is denoted by S . 
 
 ~n 
 
 There is much more structure which can be associated with S , but 
 
 ~n 
 
 it will not be necessary for the present development. 
 
 4.2 Definition [a(j , ... , j )]: Let n and m be positive integers with 
 n _> m. Let {j , . . . , j } C {1, . . . , n>; let a e S fl . 0(3^, ... , j^) is 
 
 the finite sequence obtained by deleting j n , ... , j from a. 
 
 1 m 
 
 4.3 Definition [P(n)]: n be a positive integer. P(n) C S is defined 
 
 recursively as follows: 
 
 (i) P(l) = S ± ; 
 
 (ii) If n > 1, a e P(n) iff a(n) e P(n-l) and s . = n, s = n - 1 
 
 implies j _> k - 1. 
 
 The following theorem gives the relationship between P(n) and B(n) 
 
 4.4 Theorem : There is a 1-1 correspondence between P(n) and B(n), n >_ 1. 
 
 Proof: Let T e B(n); generate a permutation a £ S according to 
 
 ,.n 
 
 the following scheme: label the vertices of T in pre-order, and read off the 
 labels In in-order. It must be shown that a e P(n). The proof is by in- 
 duction on n. 
 
21 
 
 For n = 1, 2, the result is immediate. Let n > 2, T e B(n ), 
 T e B(n ) as in Definition 1.1, and assume that the result is true for 
 
 1, 2, ... , n - 1. 
 
 Let a e P(n ) be the permutation generated from T , and f e P(n_) 
 
 be the permutation generated from T ; if n = or n~ = 0, the correspond- 
 ing permutation is defined to be the empty sequence. Let a = s. s„ . . . s , 
 
 12 n. 
 
 r = t, t„ . . . t . Let s.' = s. + 1; let t.' = t. + n, + 1. Then it is 
 1 2 n 2 3 3 J J 1 
 
 clear that the permutation p generated from T is given by 
 
 p = s' s ' ... s ' 1 t' t ' ... t \ (4.5) 
 
 12 n. 1 2 n~ 
 
 It follows that s.'=n, t . ' = n - 1 is impossible, and since a e P(n ), 
 
 f e P(n_) , the second condition of Definition 4.3 (ii) must be satisfied. 
 
 Let p = r, r. ... r , with r. = n. Let v e V(T) be the vertex labeled n. 
 12 n 2 
 
 If T' e B(n-l) is the binary tree obtained by deleting v from T, the 
 
 permutation generated from T' is P(n), and by the induction hypothesis, 
 
 P(n) E P(n-l); hence the first condition of Definition 4.3 (ii) is satisfied. 
 
 Thus the proof that a e P(n) is complete. 
 
 So far, the existence of a 1-1 map from B(n) into P(n) has been 
 
 proven; it remains to show that this map is onto. This will be accomplished 
 
 by constructing an inverse to the map just defined. 
 
 Let a. a . . . a be a finite sequence of distinct positive integers 
 12 n 
 
 An unique binary tree T(a n a ... a ) e B(n) may be constructed as follows: 
 
 12 n 
 
 (I) If n = 1, T(a ) is the binary tree with one vertex; 
 
22 
 
 (ID 
 
 if n > 1, let a. = min{a 1 , ... , ah Then T(a.. , a ... a ) 
 
 1 n 1 2 in 
 
 is the binary tree formed by joining T(a a. ... a._ ) and T(a a -+o ••• 
 
 a ) to a root r as in Definition 1.1 (ii) ; if either sequence is empty, so 
 n 
 
 is the corresponding tree. 
 
 The claim is that p |-»- T(p) is the inverse of the map previously 
 constructed; the proof is by induction on n. 
 
 For n = 1, 2, the result is obvous. Suppose that n > 2, and that 
 the result holds for 1, 2, ... , n - 1. Let a e P(n..); f e P(n 2 ) , s., t. be 
 
 as before. Referring to Equation 4.5, it is easy to see that T(s ' ... s ') 
 
 1 n x 
 
 = T(o) and T(t' ... t ') = T(r); thus T(p) is the binary tree formed by 
 1 n~ 
 
 joining T(a) and T(t) to a new root; but by the induction hypothesis, T(a) = 
 T r T(T) = T 2 . Hence T(p) = T. 
 
 q.e.d. 
 
 This same result, using a different (although equivalent) definition 
 of P(n) is derived in Exercises 2.2.1-5 and 2.3.1-6 of [K] . This derivation 
 
 goes by way of stacks, while the above theorem obtains the result directly. 
 
 4.6 Example ; For n = 1, 2, P(n) = S . For n = 3, P(n) = S - {312}. 4321 
 
 E P(4) while 4312 ij: P(4). The permutation generated from the tree in Figure 
 4.7(1) is 32415; the permutation generated from the tree in Figure 4.7 (ii) 
 is 231546. 
 
 4.8 Definition [Lexicographic Ordering on B(n)]: Let n be a positive 
 integer; let T , T e B(n)J T is lexicographically less than T 2 iff the 
 
 permutation o t P(n) corresponding to T is lexicographically less than 
 
 
 o c P(n) corresponding to T . 
 
 
23 
 
 (i) 
 
 4.7 Figure 
 
24 
 
 The remainder of this section will be concerned with ranking 
 and unranking algorithms on P(n) with respect to the lexicographic ordering. 
 
 4.9 Definition [P(n,m), P(n,m)]: Let n be a positive , m a non-negative 
 
 integer; define 
 
 P(n,m) = {a e P(n) : s = n}; 
 
 and 
 
 P(n,m) = |P(n,m) | . 
 
 Clearly P(n,m) = unless 1 <_ m <_ n. 
 
 From this point on, the notion of concatenation of lists or 
 strings will be important; the symbol | will be used to denote the opera- 
 tion of concatenation of lists or strings. 
 
 4.10 Definition [Direct Insertion Order on S , P(n)]: Let n be a positive 
 
 ~n 
 
 integer. The direct insertion order is defined on S as follows: 
 
 ~n 
 
 (i) S is in direct insertion order; 
 
 (ii) Let L = (o , o , . . . , a, . N , ) be a listing of S 
 
 n-1 1 I (.n-lj • „n-J. 
 
 in direct insertion order. For 1 < i < (n-1)!, create a list L . by 
 
 — — . n,i 
 
 inserting the character n into each possible position in o. , starting at 
 
 the right and working leftwards. The listing of S in direct insertion 
 
 n 
 
 order is 
 
 L n,l II L n,2 II ••• II L n,(„-1):- 
 The definition of direct insertion order on P(n) is similar except that in 
 part (ii), if o e P(n-l,m), the insertion process halts with the insertion 
 
25 
 
 of n to the immediate left of s . 
 
 m 
 
 Figure 4.11 depicts the generation of S and P(n) by direct 
 
 ~n 
 
 insertion, for n = 1, 2, 3, 4. 
 
 Note that while lexicographic order and direct insertion order 
 differ on S for n = 3, 4, they coincide on P(n) for n = 1, 2, 3, 4. This 
 
 is not accidental. 
 
 4.12 Lemma : The lexicographic and direct insertion orders on P(n) coincide. 
 
 Proof: Induction on n; from Figure 4.11 the result is true for 
 
 n = 1, 2, 3, 4. 
 
 Suppose the result is true for P(n-l); let L . be the list 
 
 n,i 
 
 generated from a., 1 < i < B(n-l). Clearly each L . is in lexicopraphic 
 l — — n, l 
 
 order; so it need only be shown that the last element of L .is lexicographi- 
 
 n,i 
 
 cally less than the first element of L , ., 1 < i < B(n-l) - 1. 
 
 n,i+l, - - 
 
 Let a . ■ s . , 8 . _ . . . 8 . .. , with a. e P(n-l,m); and let a... = 
 i i,l i,2 i,n-l' i „. v l+l 
 
 s -n i s JM „ ... s P11 ., . Then the last element of L , is p = s, . ... 
 1+1,1 i+1,2 l+l, n-1 n,i i,l 
 
 s. , (n) s. ... s. .; and the first element of L ... is T = 
 i,m-l i,m l , n- 1 n, l+l 
 
 s ... s (n) . 
 1+1,1 i+l,n-l 
 
 First note that since it is assumed that i £ B(n-l) - 1, it must 
 
 be that 2 <_ m <_ n - 1, for the only element of P(n-l,l) is (n-1) (n-2) ... 
 
 (2) «>-°B(n-l)- 
 
 Suppose that T < p lexicographically in P(n). Since o < a ±+ ^ 
 
 lexicographically in P(n-l), it follows that B ± . = s i+1 j for l 1 J - m-1 ' 
 
26 
 
 n = 1 
 
 S 
 
 12 
 
 123 
 
 1234 
 
 21 
 
 132 
 
 1243 
 
 
 312 
 
 1423 
 
 
 213 
 
 4123 
 
 
 231 
 
 1324 
 
 
 321 
 
 1342 
 1432 
 4132 
 3124 
 3142 
 3412 
 4312 
 
 etc, 
 
 P(n) 
 
 12 
 
 123 
 
 1234 
 
 21 
 
 132 
 
 1243 
 
 
 213 
 
 1324 
 
 
 231 
 
 1342 
 
 
 321 
 
 1432 
 2134 
 2143 
 2314 
 2341 
 2431 
 3214 
 3241 
 3421 
 4321 
 
 4.11 Figure : Generation of S and P(n) by direct insertion, 
 
27 
 
 and s £ s < n. But since p is the lexicographically largest element 
 
 X f TO 1 ■ x. y 111 
 
 of L . it follows that s, = n - l; hence s... =n - 1. But o J and o\ , , 
 n,i, i,m i+l,m i i+1 
 
 are successive elements in the list of S . in direct insertion order: hence 
 
 >n-l ' 
 
 s, ■ 8. ., = n - 1 is impossible. 
 i,m i+l,m 
 
 q.e.d. 
 Before proceeding with the development of the ranking and unrank- 
 ing algorithms, it is worthwhile to evaluate P(n,m) for 1 _< m £ n. Con- 
 sidering the construction of P(n) form P(n-l) by direct insertion, it is 
 
 easy to see that for m >_ 1, n _> 2, 
 
 m 
 P(n,m) = 2 P(n-l,y). (A. 13) 
 
 M-l 
 
 As was remarked in the proof of Lemma 4.12, 
 
 P(n,l) - 1, n >_ 1. (4.14) 
 
 Equations (4.13) and (4.14) may be used to obtain the following 
 
 recursion with boundary conditions 
 
 P(n,m) = P(n,m-1) + P(n-l,m), n > 2, m _> 1; 
 
 (4.15) 
 
 P(n,l) - 1, n > 1; 
 P(n,m) =0 n < m. 
 
 4.16 Lemma : For 2 <_ m <_ n, 
 
 ?(n ^ . (n-nrf-1) ^jp (n+u)> (4.17) 
 
 •(n,m) =±J^ TT (n+P). 
 u=l 
 
 where the product is defined to be 1 for m = 2. 
 
 Proof: In the case m = 2, the formula reduces to P(n,2) : n - 1, 
 which can be verified from Equations (4.15). The proof is by induction on 
 
28 
 
 m and n. 
 
 Suppose that 3 <_ m <_ n, that P(n,m-1) = " -=t , ~| (n+y) , and that 
 
 n=l 
 
 m-2 
 P(n-l,m') - 
 
 (n-m'+2) -rr / . \ 
 
 (m-i): IV ( y) ' 
 
 y=l 
 
 2 < m' < m- 1. 
 Then 
 
 P(n,m) = P(n,m-1) + P(n-l,m) 
 
 m-3 s m-2 
 
 («•*) + -gEgyTT («*»-« 
 
 (n-m+2) 
 
 (m-2) ! ' ' 
 
 y=l y=l 
 
 / j.i\ m-3 , v m-3 
 
 y=l y=0 
 
 = (fm?2fr + n • 7m5iyr)Tr (n+y) 
 
 - ( is^I(s^L+°^ jf ami) 
 
 ( W)(n-m,l)^ ^ 
 
 !) (n-m+l)\ ^f 
 
 i-D ! / '' 
 
 y =1 
 
 _ (n-m+l) -rr- , N 
 y=l 
 
 q.e.d, 
 This derivation allows a proof of the next corollary without 
 reference to generating functions, Taylor's series, etc. 
 
 4.18: Corollary : B(n) = P(n) = rJjCn 1 ) 
 
29 
 
 Proof: It is easy to see that P(n) = P(n+l,n+l), and substituting 
 in Equation 4.17 yields the desired result. 
 
 q.e.d. 
 
 For a e P(n), denote by lexrank (a) the rank of a in the lexico- 
 graphic ordering of P(n). It will be seen in the next lemma chat the P(i,j) 
 are intimately involved in the computation of lexrank (a) . 
 
 4.19 Lemma: Let a = s 
 
 a satisfies 
 
 s ... s e P(n), let _< j < i < n, and suppose that 
 
 s £ = I, n - j + 1 < I ± n; 
 
 Vi = n " J 
 
 Let f - s, s_ ... 8 . , a ...... s . (n-j) (n-j+1) ... (n) . 
 
 1 2 n-i-1 n-i+1 n-j 
 
 Then lexrank (o) - lexvank (J) = P(i+l,j+2). 
 
 Proof: By induction on i,j. If j = 0, s * n, and clearly 
 lexrank (o) - lexrank { T ) = i = P(i+1,2). 
 
 Suppose that j > and i = j +1. Then 
 
 a ■ 8, ... a (n-j) s . (n-j+1) ... (n) ; 
 1 n-j-2 n-j 
 
 r - 8. ... a . s . (n-j) (n-j+1) ... (n) . 
 
 1 n-j-2 n-j 
 
 Let 
 
 » 
 
 a ■ 8, ... 8 s (n) (n-1) ... (n-j+1) (n-j). 
 1 n-j-2 n-j 
 
 Considering the insertion process by which a' and o are constructed 
 
 from s, . . . s . . s . e P(n-i-l), it is seen that 
 1 n-j-2 n-j 
 
 lexrank (a) = lexrank (a') + 1 
 
 Thus 
 
 lexrank (a) - lexrank (t ) = 1 + lexrank (a') 
 
 - lexrank (j ) ; 
 
30 
 
 but {p: T < p < a lexicographically} is order isomorphic to P(j+1). Hence 
 
 lexrank (a) - lexrank (r) - 1 + P(j+1) - 1 
 
 = P(j+1) 
 - P(j+2,j+2). 
 Now let j>0, i>j+l, and suppose inductively that the result 
 is true for i - 1 and j; and that the result is true for j - 1 and all i 1 
 satisfying j - 1 < i' < n 
 Let 
 
 = S l S 2 ••' Vj-1 (n - j) Vi+1 '•• Vj (n " j+1) '•• (n); 
 
 then 
 
 Let 
 
 T = S l S 2 •'• Vi-1 Vi+1 "• Vj (n " j) (n " j+1) *'• (n) ' 
 
 a ' = S l S 2 ••' Vi-1 Vi+1 (n) (n - 1} ••• (n " j) Vi+2 '" Vj ; 
 
 a " = s i S 2 ••• Vi-i Vi+i (n - j) Vi+2 ••• Vj (n " J+1) ■-• (n) * 
 
 as before, 
 
 lexrank (a) - lexrank (a 1 ) - 1; 
 thus 
 
 lexrank (a) - lexrank ( r ) = 1 + lexrank (a') - lexrank ( T ) 
 
 = 1 .+ lexrank (a') - lexrank (a M ) 
 + lexrank (a") - lexrank C ) 
 But 
 
 lexrank (a") - lexrank (?) - P(l,j-l-2) 
 by the induction hypothesis on i; and 
 
 j-l 
 by the induction hypothesis on j 
 
 lexrank (a') - lexrank (a") - 2 P(i,v+2) 
 
31 
 
 Hence 
 
 j-1 
 
 lexrank (a) - lexrank (t) = l + 2 P(i,v+2) -l- P(i,j+2) 
 
 J 
 
 = P(i+l,j+2) 
 by Equation 4.13. 
 
 q.e.d. 
 The result of Lemma 4.19 is exploited by the following algorithm, 
 which computes the lexicographic rank of a e P(n). In this algorithm a is 
 represented by a doubly linked list, although the representation and linked 
 list manipulations are suppressed in the description presented here; the 
 array p[l:«, l:n] is used to store the values of P(i,j): p[i 3 j] = P(i,j). 
 Discussion of the method of computing the p[i,j] is deferred until after 
 the description of the algorithm. 
 
 4.20 Algorithm : Input: a e P(n) , represented by a doubly linked list. 
 Output: The lexicographic rank of a in P(n). 
 
 begin 
 
 procedure lexrank (o,n,l); 
 
 begin 
 
 temp : = ; 
 
 for j: = I until n - 2 do 
 
 if s .~l = n - j then 
 
 for i: =1 until n - 1 do 
 
32 
 
 if s . = n - j then 
 _ n-% 
 
 begin 
 
 temp: = p [i+l,j+2] 
 
 + lexrank (c(n-j , ... , n) II (n-j) U ... II (n),n, j + 1); 
 
 i: = n; 
 j: = n - 1; 
 end; 
 
 Zearranfe: - temp; 
 end lexrank (a,n,Z); 
 aompute p[l:n, l:n]j 
 lexrank (a,n,0); 
 end. 
 
 2 
 4.21 Theorem : Algorithm 4.20 is 0(n ) time-bounded; the algorithm can be 
 
 implemented so that it is 0(n) space-bounded. 
 
 Proof: The procedure call lexrank (o,n,l) requires 0(n-l) steps 
 to execute the loops on i and q in the wost case; so the worst-case time- 
 complexity for lexrank is given by the recursion 
 
 t(lexrank (a,n,0)) <_ 0(n) + t(lexrank (o(n)H(n), n, 1)) 
 since computation of a (n-j, n ... n) II (n-j) II ... W ... II (n) is constant 
 time by linked-list operations. But the time required by lexrank (a(n) II 
 
 (n) , n, 1) is the same as the time required by lexrank (o(n), n-1,0). Hence 
 
 2 
 t(lexrank (a,n,0)) « 0(n ). 
 
 2 
 Computation ofp[l:n, l:n] by Equations 4.15 requires 0(n ) time. 
 
 It appears at first storing the P(i,j) in the array p[l:n,l:n] (as opposed 
 
33 
 
 o 
 to direct computation from Equation 4.17, which also leads to an 0(n ) time- 
 
 2 
 bound) requires 0(n ) storage. However, any particular column of n[l:n, 
 
 l:n] is accessed at most once during the execution of Algorithm A. 20; and 
 
 those columns which are accessed in ascending order on J. Furthermore, if 
 
 s t 
 the jth column of p[l:n,l:n] is known, the j + 1 " may be computed using 
 
 Equations 4.17. Hence no more than two complete columns of p[l:n,l:n] need 
 
 be kept in storage at any time; hence the space bound. 
 
 q.e.d. 
 
 The essential steps of Algorithm 4.20 are illustrated in the 
 
 following example. 
 
 4.22 Example : Compute the lexicographic rank of a = 35421 in P(5) . 
 According to Lemma 4.20, 
 
 lexrank (35421) = lexrank (34215) + P(4.2) 
 
 = lexrank (32145) + P(4,3) + P(4,2) 
 = lexrank (21345) + P(5,4) + P(4,3) + P(4,2) 
 = lexrank (12345) + P(5,5) + P(5,4) + P(4,3) 
 + P(4,2). 
 But lexrank (12345) = 0; and evaluation of the appropriate P(i,j) yields 
 lexrank (35421) =14+14+5+3 
 = 36 
 Lemma 4.20 also leads to an unranking algorithm. 
 
 4.23 Algorithm : Input: integers n > 1, <_ r <_ B(n) - 1. Output: the 
 rank r element of P(n), represented as a linked list. 
 
 begin 
 
 procedure lexreoover (r,n,j); 
 
 begin 
 
34 
 
 if j _> then 
 begin 
 
 find largest i such that P[i+l,j+2] _< r; 
 
 a: = s. . . . s . . (n-j) s . ... s . n ; 
 
 Zexreeouer [>-p[t+l, j+2] t n, j'-l): 
 end; 
 
 end Ze^rrecouer (r,n,j); 
 
 compute p [1 in , l:n]; 
 a: = 1; 
 
 Zearrecoyer (r,n,n-2); 
 end. 
 
 In this algorithm, as in Algorithm 4.20, the linked-list operations 
 
 have been suppressed. 
 
 2 
 4.24 Theorem : Algorithm 4.23 is 0(n ) time-bounded and 0(n) space bounded. 
 
 Proof: In the procedure call lexrecover (r,n>j)j the time required 
 
 to find the appropriate P(i,j) is at most 0(n-j); hence the time required 
 
 for lexrecover (r,n,j) is given by 
 
 t {lexrecover (r,n,j)) £ 0(n-j) 
 
 + t(lexrecover (r-P[i+l, j+2], n, j-1). 
 
 2 
 It follows that the call lexre cover (r,n,n-2) requires at most 0(n ) time. 
 
 On the other hand, it can be seen that lexrecover (B(n) - 1, n,n-2) requires 
 
 2 
 0(n ) time. 
 
 2 
 Computation of P[l:n, l:n] requires 0(n ) time using Equations 
 
 4.15. 
 
 The 0(n) space requirement is demonstrated in a fashion similar 
 
 
35 
 
 to the proof of Theorem A. 21; in this case, the columns of P[l:n, l:n] are 
 accessed in decreasing order of j; if the j column is known, the J - 1 
 can be computed using Equations 4.15. 
 
 q.e.d. 
 4.25 Example : Given n = 5, r = 36, compute the rank r element of P(n) in 
 lexicographic order. At the outset, set a = 1. The largest i such that 
 P(i+1,5) <_ 36 is 4: P(5,5) = 14. Hence 2 is inserted immediately to the 
 left of s , = s in a i.e. a = 21; r is decremented to 22. The largest 
 i such that P(i+1,4) £ 22 is 4* P(5,4) = 14. Hence 3 is inserted into 
 the first position in a, i.e. a = 321, and r is decremented to 8. At the 
 next step, j = 1 and i is found to be 3; so a becomes 3421 and r is de- 
 cremented to 3; at the last step, j = 0, and i is found to be 3; so a 
 becomes 35421 and r is decremented to 0. The algorithm halts at this 
 point. 
 
 In the next section, the ranking and unranking of k-ary trees 
 will be treated in a similar fashion. 
 
36 
 
 §V. Lexicographic Ranking of Full k-ary Trees , 
 
 Recall from Lemma 1.6 the correspondence between k-ary trees and full 
 k-ary trees; from this correspondence, it follows that to rank k-ary 
 trees on n vertices, it suffices to rank full k-ary trees on kn + 1 
 vertices. The general strategy will be to relate full k-ary trees on 
 kn + 1 vertices to a subset of B(nk+1), which subset will be ranked 
 in a manner similar to the lexicographic ranking of B(n) Ai §IV. 
 
 Using the standard definition of (ordered) tree and forest 
 (see §2.3.2 of [K]), the following definition is made. 
 
 5.1 Definit ion [Operations on Ordered Forests "!: Let F = (T , , ... , T ) 
 — , — j n 
 
 F' = (T * , ... , T ') be ordered forests; then FF 1 is the ordered forest 
 1 m 
 
 (T T , T,' T '); F is the ordered forest (T) , where T is 
 
 1 n 1 m 
 
 the tree obtained by joining the root of each T. to a new root r. In particular, 
 
 if F is the empty ordered forest, F is the ordered forest on one vertex. 
 
 Definition 5.1 allows a concise statement of the correspondence 
 
 between ordered forests on n vertices and elements of B(n). 
 
 5.2 Definition [Correspondence Between Binary Trees and Ordered Forests] ; 
 
 (i) The empty binary tree corresponds to the empty ordered 
 forest; 
 
 (ii) If T and T are binary trees corresponding to the ordered 
 forests F and F respectively, the binary tree T which has T and T_ 
 as its left and right subtrees corresponds to F F . 
 
 The correspondence in §2.3.2 of [K] has the binary tree T 
 corresponding to F F ; Definition 5.2 (ii) is preferable for the 
 present purposes. That the correspondence in Definition 5.2 is 1-1 
 follows from the fact that the correspondence in §2.3.2 of [K] is 1-1. 
 
5.3 Definition [U.]: Let k >_ 2 ; U e B(k) is the unique binary tree 
 k vertices such that no vertex of U has a right child. 
 
 5.4 Definition [F(nk+l,k)]: Let n > 0, k > 2. 
 
 37 
 
 on 
 
 (i) If n = 0, F(l,k) = B(l); 
 
 (ii) If n > 1, let n, + ... + n, = n - 1, let T. e F(nk+l,k), 
 — 1 k i _ i 
 
 1 _< i _< k, and let T have root r ; form a binary tree T e B(nk+1) as 
 
 follows: 
 
 (a) the root of T is r; r has no left child, and the right 
 child of r is r ; 
 
 (b) for 1 < i <_ k, the left child of r is r , if r 
 
 exists; the right subtree of r. is the right subtree of r. in T.. 
 
 i ° i l 
 
 Then T e F(nk+l,k). 
 
 (iii) F(nk+l,k) has no other elements. 
 5.5 Example : Figure 5.6 depicts the sets F(nk+l,k) for k = 2, 3, and 
 n = 0, 1, 2. 
 
 5.7 Lemma : Let n _> 0, k >^ 2. There is a 1-1 correspondence between 
 F(nk+l,k) and the set of full k-ary trees on nk + 1 vertices. 
 
 Proof: The 1-1 correspondence is the restriction to F(nk+l,k) 
 of the 1-1 correspondence in Defintion 5.2. The proof is by induction 
 on n. 
 
 The case n = follows immediately from Definition 5.2(ii) 
 applied to the binary tree on one vertex. 
 
 Suppose the result is true for 0, 1, ... , n - 1. Let 
 T E F(nk+l,k) be formed from T e F(n k+l,k), 1 <_ i £ k as in Definition 
 5.4. Let S. be the full k-ary tree on n.k+1 vertices corresponding to 
 
F(l,2) 
 
 38 
 
 F(3,2) 
 
 F(5,2) 
 
 F(l,3) 
 
 F(4,3) 
 
 F(7,3) 
 
 5.6 Figure: F(nk+l,k) for k = 2, 3, n = 0, 1, 2, 
 
39 
 
 T . It follows from Definition 5.2 that the ordered forest correspond- 
 ing to T is the tree S obtained by joining the root of each T to a new 
 root r; hence S is a full k-ary tree on nk + 1 vertices. The argument 
 is completely reversible. 
 
 q. e. d. 
 Thus, to rank the set of full k-ary trees on nk + 1 vertices, 
 it suffices to rank F(nk+l,k). This will be accomplished by consider- 
 ing the subset of P(nk+1) generated by F(nk+l,k) using the method of 
 Theorem 4.4. 
 
 5.8 Definition [P(nk+l;k)]: P(nk+l;k) C S , L , is the set of 
 
 *m ~ — ~nk.+l 
 
 permutations generated from F(nk+l,k) by the method of Theorem 4.4. 
 
 By what has already been said, P(l;k) = S ; the next result 
 characterizes P(nk+l;k) for n > 1. 
 
 5.9 Lemma: Let n>l, k>2, a e S , ,,. Then a e P(nk+l;k) iff 
 — — _nk+l „ 
 
 (i) a((n-l)k + 2, (n-1) k + 3, . . . , nk, nk + 1) E 
 
 P((n-l)k+l,k); 
 
 (ii) (nk+1) (nk) (nk-1) ... ((n-l)'k + 2) is a substring of a; 
 
 (iii) if s = nk + 1 and s , = (n-1) k + 1, then m > m' . 
 m m 
 
 Proof: By induction on n; it is easily seen that P(k+l;k) 
 
 consists of the single permutation 
 
 a = (1) (k+1) (k) ... (2), 
 
 which satisfies the conditions; and no other t e S, . .. satisfies these 
 
 >k+l 
 
 conditions. 
 
 Let n > 1, and suppose that the result is true for n-1. Let 
 T e F(nk+l,k), and label the vertices of T in pre-order. It follows 
 from Definition 5.4 that the vertices labeled (n-l)k +2, ... , nk + 1 
 form a subtree rooted at the vertex w labeled (n-l)k + 2, and this sub- 
 
40 
 
 
 tree is U . Let v be the parent of w; then label [v] _< (n-l)k + 1. 
 
 K 
 
 Since a descendant of v is labeled nk + 1, it must be that the vertex 
 
 labeled (n-l)k + 1 is a descendent of v; furthermore, this vertex must 
 
 equal v or lie in left subtree of v, since it can be seen that the 
 
 right subtree of v is precisely the U already mentioned. 
 
 If the right subtree of v is deleted, the result is an 
 
 element of F((n-l)k+l,k) labeled in pre-order. By the induction 
 
 hypothesis, the permutation generated from this tree is an element 
 
 a of P( (n-l)k+l;k) . By the structural properties of T discussed above, 
 
 it follows the permutation generated by T may be obtained from a by 
 
 inserting the sequence (nk+1) (nk) ... ((n-l)k+2) immediately to the 
 
 right of label [v] in a; but either label [v] = (n-l)k + 1 or (n-l)k + 1 
 
 lies to the left of label [v] in a; hence the permutation generated by T 
 
 satisfies (i), (ii) , and (iii) . 
 
 Let a e S . ., n > 2, satisfy (i) , (ii), (iii); let T e B(nk+1) 
 _ nk+1 , — 
 
 be the binary tree generated from o as in Theorem 4.4. By the induction 
 
 hypothesis, the binary tree T' generated from o ((n-l)k +2, ... , nk + 1) 
 
 is an element of F( (n-l)k+l,k) ; also, the subtree of T corresponding to (nk+1 
 
 (nk) ... ((n-l)k + 2) is U ; so it remains to be shown that this U, is the 
 
 k k 
 
 right subtree of some vertex v in T'. Let v be the parent of u, where 
 label[u] = (n-l)k + 2. Suppose u = lehild[v); now, label[v] <_ (n-l)k + 1, 
 and v is a vertex in a subtree U of T" ; if v is not the leaf of u\> it: is 
 obvious that u = rahild[v]\ hence v is the leaf of the subtree u . • Hence 
 label[v] = n'k + 1 for some n' < n; also, nk+1 occurs to the left of 
 n'k + 1 in a, from the construction of the inverse map in Theorem 4.4, 
 but by (iii), n'k + 1 occurs to the left of (n-l)k + 1; hence nk+1 occurs 
 to the left of (n-l)k + 1, which contradicts the assumption about a. It 
 
41 
 
 follows that T E F(nk+l,k). 
 
 q. e. d. 
 Lemma 5.9 leads to a lexicographic ranking scheme for P(nk+l;k), 
 as will be seen shortly; at this point, however, there will be a disgres- 
 sion in this exposition. 
 
 5.10 Definition: [P (nk+1 ,m;k) , P (nk+1 ,m;k) ] . Let n > 0, k>2, 
 I < ■ <_ ak + 1. P(nk+l,m;k) = foeP(nk+l;k) : s^ = nk+l} ; P(nk+l,m;k) = 
 |P(nk+l,m,k) | . 
 
 The digression will be the evaluation of P(nk+l,m;k); in a 
 manner similar to Lemma 4.16, this will lead to an enumeration of the 
 set of full k-ary trees on nk + 1 vertices. 
 
 It is clear that Lemma 5.9 is equivalent to the proposition 
 that for n > 1, P(nk+l;k) is obtained from P((n-l)k + l;k) by direct 
 insertion of the string (nk+1) (nk) ... ((n-l)k) +2) into all positions 
 of a such that 5.9 (i), (ii), and (iii) are satisfied, performing these 
 insertions for all a e P((n-l)k + l;k). It follows from this that 
 
 P(l,m;k) 
 
 m = 1 
 
 and for n _> 1 
 
 P(nk+l,m;k) = 
 
 ^ 
 
 m > 2; 
 
 m ^ n 
 
 (5.11) 
 
 m-1 
 
 2 P((n-l)k + l,u;k) (5.12) 
 u=n 
 
 n + 1 1 m 1 (n-l)k + 2 
 (n-l)k + 3 < m < nk + 1 
 
 Equation 5.12 is easily transformed to the following recursion, 
 
42 
 
 if the convention P( n k+l,0;k) = is adopted: 
 
 P(nk+l,m;k) = P(nk+l,m-l;k) + P((n-l)k+l,m-l;k) . (5.13) 
 The solution of Recursion 5.13 with boundary condition 5.11 will require 
 the following lemma. 
 
 5.14 Lemma : The following are identites: 
 (i) For integers a, b, > 0, £ >_ 
 
 | /a+£-X-l\ /b+X-l\ /a+b+£-l\ 
 i=0 \ l-X J \ X I \ I I 
 
 (ii) For integer p, real r, s, t, 
 
 2 /r-tA\ /s-t(p-A;\ r /r+s-tp\ 
 
 >0\ X I \ p-X / r-tX \ p / 
 
 X>0\ X / \ p-X / r-tX 
 
 r+s-tp> 
 
 P 
 
 (iii) For integer k, I, m, 
 
 M-] 
 \ 
 
 y. 1 /Xk\ /m-Xk \_ /m\ 
 
 -1 X < k -!> +1 \J LlJ" [J 
 
 Proof: (i) and (ii) are equations 12.16 of [F] and 1.2.6.26 of 
 [K], respectively. To obtain (iii) note that 
 
 v 1 /Xk\ /m-Xk \ j, 1 I Xk \ /m-Xk \ 
 
 x-i *<"-« + i [ J \ l+1 J * x-1 x Ix-J U+i-xJ 
 
 j. _J^_ /(X+l)k\ /m-(X+l)k' 
 ' X=0 X+1 \ X M W . 
 
 and the last summation is obtained from (ii) by substituting 
 
 t = -k; 
 r = k; 
 p = I; 
 s = m - U+l)k. 
 
43 
 
 q. e. d, 
 
 In particular, it should be noted that Equation 5.14 (ii) may 
 be proven without reference to generating functions; see [K] or [GK]. 
 5.15 Theorem: P(nk-H,m;k) is evaluated as follows: 
 
 (i) P(l,ra;k) 
 
 1 m - 1 
 J) otherwise; 
 
 (ii) P(k+l,m;k) = fl m = 2 
 
 1^0 otherwise. 
 
 For n > 2, let £ satisfy < £ < n - 3; then 
 
 O 
 
 1 < m < n + 1 
 
 /m-3\ y, 1 /Ak\ /m-Ak-3\ 
 U-J ' x-l X(k " 1)+1 \ J l-A-1 ] 
 
 £ (k-l)+n+2 < m < (£+1) (k-l)+ n +1 
 
 (iii) P(nk+l,m;k) = / /(n . 2 )k\ n " 3 
 
 /(n-2)k\_ ^ 1 /Ak\ /(n-A-2)k\ 
 I n-2 !~X=1 A(k " 1)+3 L J \ n-A-1 I 
 
 (n-2)k+4 < m < (n-l)k + 2 
 
 
 
 (n-l)k+3 < m < nk + 1 
 
 Proof: The first two equalities are obvious; the proof of the 
 case n _> 2 is by induction on n. 
 
 For the case n = 2 it is easily seen by construction that 
 
 ^0 1 <m< 2 
 P(2k+l,ra;k) - < 1 3 < ra £ k + 2 
 
 Lo k+3<.m<_2k+l; 
 these equalities are in the form of (iii) given that there is no solution 
 
44 
 
 to the inequalities on I. For the case n = 3, the result is 
 
 r 
 
 P(3k+l,m;k) = ( 
 
 1 <_ m <_ 3 
 
 4 <_ m <_ k + 3 
 k+4< m< 2k +2 
 
 v. 
 
 m - 3 
 k 
 
 
 which is also in the form of (iii) with I = 0. Assume that (iii) holds 
 for 2, 3, ... , n - 1. It is easy to see directly that in the range 
 1 <i<n, P(nk+l,m;k) = 0, and that P(nk+l,n+l;k) = 1. This gives the 
 first equality of (iii) . 
 
 In the second equality of (iii) the case I = follows from 
 the induction hypothesis on n, the first equality in (iii), Equation 5.13, 
 and Pascal's identity on binomial coefficients. Assume that £ ^. 1 and 
 that the second equality of (iii) holds for I - 1. Let m = £(k-l) + n + 2; 
 by the induction hypothesis on n, 
 
 P( (n-l)k+l,m-l;k) = 
 
 by the hypothesis on Jt, 
 
 P(nk+l,m-l;k) = 
 
 /m-4\ y, 1 /Xk\ /m-Ak-4\ 
 
 U-sJ ~X = *< k -D + I Ix / I n-X- 2 i : 
 
 /m-4\ y 1 /* k \ /ni-Ak-4\ 
 
 L- 2 i Vo *<X-D + 1 U ) \ n-X-J 
 
 /m-4\ s 1 /Xk\ /m-Xk-4\ 
 
 \n-2l "x-0 *< k -!> +1 lx ) I n-X-J, 
 
 since the second binomial coefficient in the X = I term of this summation 
 Is zero. By Equation 5.13 and Pascal's identity the result follows for 
 m = e(k-l) + n + 2. For fc(k-l) + n + 2 < m < (£+1) (k-1) + n + 1, the 
 result follows by induction on m using Equation 5.13 and Pascal's identity, 
 Hence the result holds for n + 2 <_ m <_ (n-3)k + 4 by induction on l. 
 
45 
 
 Suppose (n-3)k + 5 _< m _< (n-2)k + 3. Let m' = (n-3)k + 4, 
 t ■ m - m' . Then 
 
 From 5.14 (i) we have 
 
 /(n-3)k+l\ /(n-3)k\ /t\ /m-3\ n-2 ,(n-3)k+l-v\ /t-l+v\ 
 
 ( n . 2 )+ Cn-3 lij-Lj- ^ ( „-2-v M v )' 
 
 similarly, 
 
 /(n-X-3)k+l\ /(n-X-3)k\ /t\ /m-Xk-3\ n-X-1 /(n-X-3)k+l-v\ /t-l-v\ 
 
 \ n-X-1 / + \ n-X-2 / \1/ = \ n-X-1 /" v=2 \ n-X-l-v ' \ v 1 
 
 Thus, 
 
 — ■ a - 1 ^ a c;.; 3 ) 
 
 n-2 
 
 y /(n-3)k+l-v\ /t-l+v 
 " « ( n-2-v ) ( v 
 
 n-4 n-X-1 
 + 22 - 
 X=l v=2 X 
 
 _1 /Xk\ /(n-X-3)k+l-v\ /t-l+vN 
 
 Upon interchanging the order of summation, the last term becomes 
 
 1 /Xk\ /(n-X-k)k-l\ /t+1 
 
 ^XCk-D+1 
 
46 
 
 n-2 n-l-v 
 
 y v 1 / Xk\ /(n-X-3)k+l-v\ /t-l+v\ 
 
 v=3 X-l X(k " 1>+1 \x I \ n-X-l-v )(vJ' 
 
 Let 3 < v _< n - 2, let v + y = n - 2. Then the coefficient of / t_ \ 
 
 in Equation 5.16 is 
 
 y+l 
 
 /(n-3)(k-l)+yv M ' x 1 /Ak\ /(n-X-3) (k-l)+u-A v 
 
 " I y j X-l A(k " 1)+1 1a i ( y + l-A I 
 
 = 
 by 5.14 (iii). 
 
 The coefficient of j \ in Equation 5.16 is 
 
 /(n-3)k-l\ n ~ 4 1 (\k\ /(n-X-3)k-l\ 
 
 ' I n -4 ) X-l X(k " 1)+1 IJl n-X-3 i 
 
 (n-3)k\ /-l^ 
 
 n 
 
 (n-3)k + l , n _ 3 , v Q 
 
 again, by Equation 5.14 (iii). Now 
 
 t + l-m-m' +1 
 
 = m - (n-3)k - 3, 
 and by the standard convention for binomial coefficients 
 
 /-r 
 
 (")■ 
 
 = 1. 
 
 Thus 
 
 n-3 
 P 
 
 — a-^^oo. 
 
 and the result is established for I = n - 3. For (n-2)k + 4 <_ m < 
 (n-l)k + 2, P((n-l)k + 1, m - l;k) = 0, by the induction hypothesis on 
 n; the evaluation of P(nk+l,m;k) in this range follows from substituting 
 I ■ n - 3, m = (n-2)k + 3 in the previous formula and applying Recursion 
 5.13. The last equality follows directly from the definition of 
 
47 
 
 P(nk+l;k). 
 
 q. e. d, 
 5.17 Corollary : P(nk+l;k) = n(k * 1)+1 ("*) . 
 
 Proof: By the properties of P(nk+l;k), P(nk+l;k) = 
 P((n+l)k,m;k) for (n-l)k + 4 <_ m <_ nk + 2 . For m in this range 
 
 ^ 1 /*k\ /n-A-l)k\ 
 
 X=n-1 
 (by 5.14 (iii)) 
 
 rnk 
 
 1 /Ak\ /n-A-l)k\ 
 
 n(k-l)+l 
 
 \ n 
 
 q. e. d. 
 
 Thus Corollary 5.17 evaluates the set of full k-ary tress on nk + 1 
 
 vertices, without reference to generating functions. 
 
 Returning to the problem of ranking the elements of 
 P(nk+l;k) in lexicographic order, the first step is to obtain a result 
 analogous to Lemma 4.12. The direct insertion order on P(nk+l;k) has 
 already been informally defined while establishing Equations 5.11 and 
 5.12. 
 
 5.18 Lemma : On P(nk+l;k), the lexicographic order and direct insertion 
 order coincide. 
 
 Proof: By induction on n; the result is trivial for n = 0, 1 
 since P(l;k) = P(k+l;k) = 1. Let n > 1 and suppose the result holds for 
 n - 1. As in Lemma 4.12, it suffices to show that for a < x lexico- 
 graphically consecutive in P ( (n-l)k+l ;k) , o', the lexicogrpahically 
 largest element of P(nk+l;k) formed from o by direct insertion, is 
 
48 
 
 lexicographically less than t, the lexicographically least element of 
 P(nk+l;k) formed from t by direct insertion. 
 
 Let a >• 3 1 ... s (n _ 1)k + v t ■• t v ... , t (n _ 1)k + v 
 By the induction hypothesis and the properties of P((n-l)k+l;k) there is 
 
 an £ > 1 such that 
 
 s. = t . , 1 < i < £; 
 
 l i — — 
 
 I 
 Suppose that t' < a ? ; it follows that a' e P(nk+l,m;k) for m <_ I + 1. 
 
 By the definition of direct insertion order on P(nk+l;k), s n = 
 
 *~ m— 1 
 
 (n-l)k+l; hence t - = (n-l)k + 1. But this is impossible since 
 m— 1 
 
 P((n-l)k+l;k) is in direct insertion order. 
 
 q. e. d. 
 The final step in preparation for the ranking and unranking 
 algorithms on P(nk+l;k) is the establishment of a result analogous to Lemma 
 4.19. The result is somewhat surprising in that the coefficients are 
 not particularly related to the P(nk+l,m;k). 
 
 5.19 Definition : [C(i,j,k)] a Let k > 2, j > 0, i > (j+l)k - 1; let n > 
 max(n+2,i). Let a = s ... s e P(nk+l;k) satisfy 
 
 S (n-*-l)k+2 = <"-*> k+1 0< i< j -l; 
 let 
 
 S nk-i+l ■ (n "J )k + l « 
 Let t = t ... t k+] be obtained from a((n-j-l)k +2, ... , (n-j)k + 1) 
 
 by inserting the substring ((n-j)k + 1) ((n-j)k) ... (n-j-l)k + 2 so that 
 
 t (n-J-l)k + 2 = (n-j)k + 1. 
 
49 
 
 Define 
 
 C(i,j,k) = lexrank (a) - lexrank (x), where lexrank is computed 
 with respect to P(kn+l;k). if < i < (j+l)k - 1, define 
 
 C(i,j,k) = 0. 
 Note that for i = (j+l)k - 1, a = t and hence C(i,j,k) = 0. 
 
 The next few results establish some important properties of the 
 C(i,j,k). 
 5.20 Lemma : If i _> k » then C(i,0,k) = i - k + 1. 
 
 Proof: In this case, 
 
 = S l ••• S nk-i (nk+1) (nk) ••• «"-D k+2 > s „ k -i + l + k ••• s nk+ l, 
 
 and 
 
 1 * S l ••• S nk-i s nk-i + l + k ••• s nk + l (nk+1) (nk) — «n-l> k+2 >- 
 The result follows from the nature of the direct insertion procedure. 
 
 q. e. d. 
 5.21 Lemma : Let j _> 0, i > (j+l)k; 
 
 then 
 
 j 
 C(i,j,k) = 1 + v 5 Q C(i-j+v-l,v,k). 
 
 Proof: In this case, 
 
 a " S l '•• S nk-i ((-J) k+1 > '•• ((n-J-Dk+2) s nk _ 1+k+1 ... s nk+1 . 
 Let 
 
 a =s. ... s. , s, ,..., ... s. ,v lin e P( (n-j-l)k+l,k) ; 
 o 1 nk-i nk-i+k+1 (n-j)k+l J 
 
 form a 1 from a by inserting the substring ((n-j)k+l) ... ((n-j-l)k+2) 
 
 immediately to the right of s , ,.,.,, and for i - 1 > £- > , inserting 
 
 6 nk-i+k+1 — — 
 
 ((n-£)k+l) ... ((n-Jl-l)k+2) immediately to the right of ((n-£-l)k+l) . 
 
 Finally, let 
 
50 
 
 a" = s ... s s ((n-j)k+l) ... ((n-j-l)k+2) s , ... ., ... s _.,, 
 
 1 nk-i nk-i+k+1 J J nk-i+k+2 nk+1 
 
 Then 
 
 C(i,j,k) = 1 + lexrank (a') - lexrank (t) 
 
 = 1 + (lexrank (a') - lexrank (a")) 
 
 + (lexrank (a") - lexrank (t)). 
 But the last term is by definition C(i-l,j,k); and the first term is 
 
 j-l 
 
 2 C(i-j+v-l;v,k). 
 v=0 
 
 q. e. d. 
 5.22 Corollary : Let j > 1, i _> (j+l)k; then C(i,j,k) = C(i-l,j-l,k) 
 + C(i-l,j,k) # 
 
 Proof: By Lemma 5.22, 
 
 j 
 
 C(i,j,k) =1+2 c(i-j+v-l,v,k) 
 
 v=0 
 
 j-l 
 = C(i~l,j,k) +1+2 C(i-j+v-l,v,k) 
 
 v=0 
 
 j-l 
 = C(i-l,j,k) +1+2 C([i-l]-[j-l]+v-l,v,k) 
 
 v=0 
 
 = C(i-l,j,k) + C(i-l,j-l,k). 
 
 q. e. d. 
 The defintion of C(i,j,k) and the properties derived therefrom 
 may be summarized in the following recursion: 
 
 1 < i < j(k+l) - lj 
 
 C(i,j,k) /i-k+1 j - 0, i>k; (5.23) 
 
 C(i-1, j-l, k) + C(i-1, j, k) otherwise. 
 
51 
 
 Thus the C(i,j,k) satisfy Pascal's identity, but with different 
 boundary conditions. 
 
 5.24 Theorem : Let j >_ 0, 1 > (j+l)k - 1; 
 then 
 
 c<i.,.w - Q - ( k -i) Q . 
 
 Proof: By induction on i , j. The case j=0, i > k - 1 is the 
 left boundary condition of Recursion 5.23. 
 
 Suppose that j > and that the result is true for j - 1. 
 Let i = (j+1) k - 1. Then 
 
 ^(j+l)k-L _ (k _ 1} J(J+l>lt,lJ 
 m /(j+l)k-l\ _ (k _ 1) ((j+l)k-l) ... ((j+l)(k-l)+l) 
 
 j+i i j: 
 
 /(j+Dk-i\ 
 
 (j+l)k-i\ _ ((,i+i)k-i) ... ((j+i)(k-i)) 
 j+l ' (j+D! 
 
 = o 
 
 = C((j+l)k-l,j,k). 
 The rest follows from Pascal's identity. 
 
 q . e. d. 
 It is worth noting at this point that, although the C(i,j,k) 
 have been defined only for k >^ 2, if the result of Theorem 5.24 is 
 extended to the case k = 1, then 
 
 C(i,j,l) - / i ), j > 0, i > j. 
 
 l j+l / 
 
 Thus the C(i,j,k) extended to the case k = 1 are a generaliztion of ordinary 
 binomial coefficients, at least over their common range of definition. 
 
52 
 
 From their defintion, the C(i,j,k) will play the same role in 
 lexicographic ranking algorithm for P(kn+l;k) as did the P(i,j) for 
 lexicographic ranking of P(n). In this algorithm, the C(i,j,k) are stored 
 in the array ck[l:n*k, 0:n-2]; as before the details of computing this arraj 
 are omitted from the algorithm. The permutation a e P(nk+l;k) is represent- 
 ed by a doubly-linked list, but the representation and list operations are 
 suppressed. The permuation t e P(nk+l;k) is derived from a as in Definitioi 
 5.19. 
 
 5.25 Algorithm : Input: a e P(nk+l;k) represented as a doubly-linked list 
 Output: the lexicographic rank of a in P(nk+l;k). 
 begin 
 
 procedure klexrank (a,n,-d); 
 
 begin 
 
 temp: = 0; 
 
 for j: = t until n - 2 do 
 
 if 8 (n-j-l)*fc+2 n = (n -« 7 ' ) ** + l *2 
 
 for i:= (j+l)*k until n*k do 
 
 L f 8 n*fc-i+l = (n -<7>* fe 55? 
 
 begin 
 
 te/np: = ek[i t j,k] + klexrank (x,n, j+l); 
 
 i: ■ n*fe; 
 j: - »-2j 
 
 end; 
 
53 
 
 klexrank: = temp; 
 end lexrank (o,n,£); 
 
 compute ck[l:n*k;0:n-2] ; 
 lexrank (o,rc,0); 
 end. 
 
 The C(i,j,k) also lead to an unraking algorithm. 
 5.26 Algorithm : Input: integers n _> 0, _< r _< P(nk+l;k)-l. Output: 
 the rank r element of P(nk+l;k) represented as a linked list, 
 begin 
 
 procedure klexrecover (i",n,j); 
 
 begin 
 
 if j > then 
 begin 
 
 find largest i such that ck[i,j] <_r\ 
 
 ( lV • - s n* k -i (in -^ k+l) • ' ' «"-J-D*fc+2) s nitk _ i+1 . . .s (n _._ 1)ick+1 : 
 
 o: = s. 
 
 klexrecover (r-ck[i,j], n, j-1); 
 end; 
 
 end klexrecover (r,n,j); 
 
 compute ck[l:n*k, 0:n-2]; 
 o: = l(k+l) (k) ... 2; 
 w^.rr.^^gp (i»,n,n-2); 
 end . 
 
 5.27 Theorem : Algorithms 5.25 and 5.26 are 0((nk) ) time-bounded and 
 0(nk) space-bounded. 
 
 Proof: Similar to proofs of Theorems A. 21 and 4.24. 
 
54 
 
 §VI Final Remarks ; The notion of ranking combinatorial configurations was 
 
 first presented in [Ll; since that time, a considerable amount of work 
 
 has been done on the subject; see [CW], [FW], [Wl], [W2], [W3]. 
 
 The ranking algorithms in §IV and §V differ from the usual 
 
 strategy for ranking permutations and n-tuples. This strategy, a special 
 
 case of the general strategy defined in [W2], may be described as follows: 
 
 to rank s, ... s lexicographically, let A. = {t. ... t : t. = s. 
 1 n or y ' li njjj 
 
 1 < j < i - 1 and t. < s.}. Then the rank of s, ... s is simply 
 — — ii In 
 
 n 
 
 2 |A.|. 
 i-1 X 
 
 If a linear order is defined on P(n) as follows: 
 
 a < t in P(n) iff 
 (i) a e P(n,m), x e P(n,m') and m < m 1 ; or 
 
 (ii) a, t e P(n,m) and a(n) < T(n) in P(n-l), 
 
 then the general strategy of [W2] may be applied to produce ranking and 
 
 2 
 unranking algorithms; these algorithms are 0(n ) time and 0(n) space- 
 bounded. A similar remark applies to P(nk+l;k). 
 
55 
 
 REFERENCES 
 
 [ A] A. V. Aho, J. E. Hopcroft, J. D. Ullman The Design and Analysis of 
 Computer Algorithms , Addison-Wesley , Reading, MA, 1973. 
 
 [CW] E. Calabi and H. Wilf, On the Sequential and Random Selection of 
 
 Subspaces Over a Finite Field , J. Combinatorial Theory, to appear. 
 
 [ F] W. Feller, An Introduction to Probability Theory and Its Applications , 
 Volume I , Wiley, New York, 1957. 
 
 [FW] J. Fillmore and S. G. Williamson, Ranking Algorithms: The Symmetries 
 and Colorations of the n-Cube , SLAM Journal on Computing 5,2 
 (June 1976), pp. 297-304. 
 
 [GK] H. W. Gould and J. Kaucky; Evaluation of a Class of Binomial 
 
 Coefficient Summations , J. Combinatorial Theory 1 (1966), pp. 233-247. 
 
 [ K] D. E. Knuth, The Art of Computer Programming , Volume I , Addison- 
 Wesley, Reading, MA, 1973. 
 
 [ L] D. H. Lehmer, The Machine Tools of Combinatorics, in Applied 
 
 Combinatorial Mathematics , E. F. Beckenbach (ed.), Wiley, New York, 
 1964, pp. 5-31. 
 
 [ R] Rudin, W. , Real and Complex Analysis , McGraw-Hill, New York, 1966. 
 
 [Wl] H. S. Wilf, A Unified Setting for Sequencing, Ranking, and Selection 
 Algorithms for Combinatorial Objects , preprint, University of 
 Pennsylvania. 
 
 [W2] S. G. Williamson, On the Ordering, Ranking, and Random Generation 
 of Basic Combinatorial Sets, in Proceedings of the Table Ronde, 
 Combinatoire et Representation du Groupe Symmetrique, Strasbourg, 
 France, 26-30 April, 1976, to appear. 
 
 [W3] S. G. Williamson, Ranking Algorithms for Lists of Partitions , 
 SIAM Journal on Computing, 5,4 (December 1976), pp. 602-617. 
 
OCRAPHIC DATA 
 
 T 
 
 t jnj Subt ille 
 
 1. Report No. 
 
 UIUCDCS-R-77-850 
 
 3. Recipient's Acccs»ion No. 
 
 5. Report Date 
 
 February, 1977 
 
 On The Ordering, Enumeration and Ranking of k-ary Trees 
 
 6. 
 
 ho»(s) 
 
 Anthony E. Trojanowski 
 
 8. Performing Organization Repc. 
 No. 
 
 tixming Organization Name and Address 
 
 Department of Computer Science 
 
 University of Illinois at Urbana-Champaign 
 
 Urbana, IL 61801 
 
 10. Project/Task/Work Unit No. 
 
 11. Contract /Grant No. 
 
 MCS-73-03408 
 
 ■on soring Organization Name and Address 
 
 National Science Foundation 
 Washington, DC 
 
 13. Type of Report & Period 
 Covered 
 
 14. 
 
 pplementary Notes 
 
 
 The problem of ranking a finite set X may be defined as follows: 
 if |x| = N, define a linear order on X and find an order isomorphism 
 V0: X -»• {0, 1, ... , N - 1}. In this paper, X is the set of k-ary trees 
 on n vertices, k >^ 2, n _> 0. In addition to constructing ranking func- 
 tions with respect to two different linear orders on k-ary trees, an 
 investigation into some purely enumerative aspects of the problem is 
 included. One result of this investigation is a generalization of 
 binomial coefficients. 
 
 ry Words and Document Analysis. 17a. Descriptors 
 
 algorithm, binary tree, linear order, k-ary tree, ranking function, recursion 
 
 fentifiers Opcn-Ended Terms 
 
 I Fie Id /Group 
 
 '•liability Statement 
 
 •<Tl».l S | 10-701 
 
 19. Security (-lass fl his 
 Report ) 
 
 i:TS}f I ASSIFlt.LJ 
 
 20. set urity < l.i 
 
 Pace 
 
 UNCLASSIFIED 
 
 21. No. <>f ! 
 
 22. Pru e 
 
 USCOMM-DC 40JJ9-P7I 
 
APR 1 4 1977 
 
'979 
 
£3&i