ENGINEERING RESEARCH INSTITUTE UNIVERSITY OF MICHIGAN ANN ARBOR THE FOLDED TREE ARTHUR Wo BURKS ROBERT Mc NAUGHTON CARL H, POLLMAR DON W. WARREN JESSE B. WRIGHT PAOLI, PENN~SYLVANIA Septembe 0, 19 Septembe~r 30,2 1954

/.'1,z;. i Iuc., j?/

TABLE OF CONTENTS Page PREFACE iii 1, INTRODUCTION 1 2. DEFINITION OF FOLDED TREE 2 3. LOADING SEQUENCES; ADMISSIBILITY 9 4.. THE SPLITTING TECHNIQUE 12 5. THE VALIDITY OF THE SPLITTING TECHNIQUE 17 6. THE ECONOMY OF THE FOLDED TREE 22 7. A GENERALIZATION OF THE FOLDED TREE 28 APPENDIX 31 BIBLIOGRAPHY 32 ii

PREFACE This report is, in part, a result of rewriting material contained in our two previous reports in the series having the general title, Language Conversion for Digital Computers. Those two reports are (1) General Introduction and Volume I, The Logical Realization of Transliterative Functions, by Arthur W. Burks, Carl H. Poll-mar, Don W. Warren, and Jesse B. Wright; and (2) Volume III, Minimal Switch Theory and the Folded Tree, by Arthur W. Burks, Carl H. Pollma'r, Don W. Warren, and Jesse B. Wright. The old material is presented in a new and improved form (Sections 1 through 5) and is augmented by novel results (Sections 6 and 7). The two earlier volumes contained discussions of both folded trees and minimality; the minimality results'have been extended and presented anew in a report, Complete Decoding Netst General Theory and Minimality, and it seemed worthwhile to perform a similar task for the results concerning folded trees, iii

THE FOLDED TREE* 1. INTRODUCTION The problem of constructing circuits which perform a certain function and have some formal properties contributing to engineering efficiency was considered by Shannon in [I]. (Roman numerals in brackets refer to the bibliography at the end of this paper.) Part of Shannon's problem (Part II of [I], pp. 81-89) was to formulate an arithmetic condition such that for any sequence of positive integers satisfying that condition a tree circuit can be constructed whose load distribution is given by that sequence. That condition is identical with our notion of "admissibility," defined in Section 3 of this paper. The present paper takes up this same problem, but is entirely selfcontained.. No reference to Shannon's paper is necessary either for definitions of concepts or for proofs of theorems, Our results go beyond those of Shannon, both in that we prove the necessity of the admissibility condition and also in that we give a constructive technique, helpful to a practical engineer, for constructing a folded tree with any given load. distribution satisfying the condition of admissibility, To obtain these results we must formulate a precise definition of the term "folded tree." Although Shannon does not give a precise definition of any corresponding concept, it is clear that our precisely defined concept applies to the circuits which he considers. We shall use some of the concepts of our previous paper [iH], but we define them anew here, so no acquaintance with that paper is presupposed. Our method, here as in III], is to discuss diagrams rather than circuits directly. The diagrams may be realized by circuits of various different kinds, e.g., relay transfer contact nets discussed in E]li and electronic digital computing circuits. The advantages of this approach are (1) that the range of application of results is wider, and (2) that the problems, being abstract, can be solved within pure mathematics. Our methods and * The writing of this paper and the research which it reports were done under the sponsorship of the Burroughs Corporation, Research Center, Paoli, Pennsylvania. The authors wish to thank Dr. Irving M. Copi for many helpful suggestions and also Dr. Frank Harary for his suggestions. 1

results are intimately connected with the field of mathematics known as the theory of linear graphs; but they are not an application of any previously known materials of that field, and consequently we presuppose no knowledge of it. Although our definitions and theorems concern diagrams, we shall frequently comment on their significance for physical circuits, 2 DEFINITION OF FOLDED TREE In this section we formulate a precise definition of the term "folded tree" and show that the diagrams covered by this term are suitable for representing some familiar circuits constructed out of standard devices, We shall be concerned with vertex diagrams which are arrangements of small circles and straight lines, such that (1) each circle has just three lines touching its circumference, one on its left and two on its right, (2) each end of each line may touch either a circle (as in Fig0 1) or the ends of any number of other lines (as in Fig. 10) or it may touch nothing (as in Fig. 1), and (3) no circles touch each other. (In this paper if a word is italicized in a sentence, then the word is defined in that sentence.) The circles are called vertices and the lines wires; the left-hand wire is called the vertex-input, the upper right-hand wire is called the upper vertex-output, and the' lower right-hand wire, the lower vertex-output. The usage here of "output" and "input" is nearer to that of [I] than to [II]. The first vertex diagram we introduce is an n-baoy tree, for which the following recursive definition is provided: 1, A 1-bay tree consists of just one vertex with its input and output wires; this vertex is the first (and only) bay of the 1-bay tree; 2. An (i + l)-ba tree results from an i-bay tree when, to each vertex-output u of a vertex in the ith bay, a new vertex is joined so that u is the vertex-input of the new vertex;: the new vertices constitute the (i + 1)th bay; 3. An n-bay tree has only the vertices and wires provided for in 1 and 2; no diagrams other than those so provided for are trees, The input of an n-bay tree is the vertex-input of the vertex of the first bay, An outpt of an n-,bay tree is a vertex-output of a vertex in the nth bay Note that the tree input is the only wire input is the y wire in the tree which is not a vertex-output, and that the tree outputs are the only wires 2

which are not vertex-inputs.:Note also that there are 2n outputs of an n-bay tree, The result of deleting the crosses (but no lines or circles) from Fig. 1 is a 4-bay tree. (Note that each bay in this figure is simply a vertical column of vertices, This will be true of all figures of trees in this paper, although the definition of "tree" does not require this.) Fig. 1 A wire is to be understood as being at any one moment in either of two states, state 1 or state 0, and a vertex as being in just one of two settings, an upper setting or a lower setting. The state of a vertexoutput is determined by the setting of the vertex and the state of the vertex-input: if the vertex-input is in state 1 and if the vertex is in the upper setting, then the upper vertex-output is in state 1 and the lower vertex-output in state O; if the vertex-input is in state 1 and the vertex in the lower setting, then the upper vertex-output is in state 0 and the lower vertex-output in state 1; if the vertex-inpu.t is in state 0, then regardless of the setting of the vertex the state of both vertexoutputs is 0. Before proceeding we will relate trees to the net diagrams of [II] and described two physical realizations of trees~ In the net diagram of Fig. 2 each square is a conjunction ("and") element whose output is in state 1 if and only if both its inputs are in state 1. A' vertex, together with its vertex-input and vertex-outputs, and the net of Fig, 2 represent the same type of circuit if exactly one of the input pair bb' is in state 1 at any one time. (The use of the word"input" in this connection is similar to the use in [II]; it differs significantly from the use of the word in the major part of this paper,) 5

C C Fig. 2 Wire a of Fig. 2 is the vertex-input, and wires c and d. are the vertex-outputs, and the vertex is in the upper setting just in case b is in state 1. Nets like the one of Fig. 2 may clearly be combined to form trees. A conjunction element may be realized by a crystal diode or vacuum tube circuit whose output voltage is high (state 1) whenever both circuit inputs are at high voltage, otherwise the circuit output voltage is low (state 0). Two such circuits, interconnected as in Fig. 2, constitute a physical interpretation of a vertex with its vertex input and two vertex-outputs. Wire c is in state 1 whenever a and b are both in state 1, and d is in state 1 whenever a and b' are both in state 1. A vertex may also be realized by a relay transfer element. A relay transfer element is a (mechanical) single-pole double-throw switch with the wire of the pole realizing the vertex-input and the wires from the output contacts realizing the vertex-outputs. The transfer element is controlled by a magnet and spring working in opposition, the two positions being represented by the two vertex settings, Thus, if current is flowing (state 1) in the vertex-input, it flows in the upper vertexoutput whenever the relay is not activated and in the lower vertex-output whenever the relay is activated. It should be noted that our vertex diagrams (trees and the diagrams of Section 6) are particularly suited to represent relay contact nets composed of transfer elements, namely, single-pole double-throw switches, electro-magnetically controlled. In such electrical nets the wires to the device (magnet) which controls the settingsof the transfer contacts are not connected into the contact net itself That our vertex diagrams do not show the wires which determine the vertex settings is intended to represent that feature. In contrast the wires b,b0 of an electronic circuit of the sort represented by Fig, 2 are, in general, like a, c, and d, connected to other components of the circuit. Electronic circuits can thereby realize nets which are more complex than vertex diagrams. Hence, the class of circuits represented by vertex diagrams

(in the broad sense of Section 6) is narrower than the class of circuits represented by diagrams constructed from conjunction elements. It turns out, for example, that in a certain sense of "cost" the tree is probably a minimal diagram in the first class, while it is not at all minimal in the second class (see Section 6). To put the point alternatively, a generally efficient way to do complete decoding with relays is by means of a tree, but that is not generally an efficient way to do complete decoding with vacuum tubes or crystal diodes,. chain of an n-bay tree is a sequence X1,.., + l, where X1 is the tree input and where, for i 2n, if Xi is a vertex-input of some vertex, then Xi + 1 is that vertex and, if Xi is a vertex, then Xi + 1 is one of its vertex-output's, It follows that,Xn + 1 is a tree output. In Fig. 1 the ve.rtices and wires marked with crosses constitute a chain. It is obvious that each tree output is a member of one and only one chain. In an n-bay tree the settings of the vertices and the state of the tree input vary independently of each other, but or-e these are determined the state of each wire is determined, If the tree input is in state 0, then every wire is in state 0, regardless of the settings of the vertices, If the tree input is in state 1, then there will be a chain whose every wire is in state 1 and such that every wire not on the chain is in state 0. What chain it is will depend on the settings of the vertices, since the state of each vertex-output is determined by the setting of the vertex and the state of its vertex-input. We are interested in trees in which the settings of the vertices do not vary completely independently of each other, but whose vertices are partioned irztoanumber of classes, all the vertices of each class being in the same setting at any one time. In such trees we indicate the class to which each vertex belongs by affixing the same label to every vertex of a given class, vertices which belong to different classes being given different labels. We call such a tree a "labeled —tree," and define Ft as follows. An n-bay labeled-tree is formed from an n-bay tree by marking each vertex with exactly one label from a set of m labels, and using each of the m labels to mark at least one vertex; m can be less than, equal to, or greater than n. We require, of course, that all vertices having the same label be in the same setting. Fig. 3 is a 3-bay labeled-tree in which m = n. An n-bay folded tree is an n-bay labeled-tree in which there are exactly n labels (i.e., m = n) and, for every chain and for each label, there is at least one vertex with that label in the chain, It follows that there is exactly one vertex in each chain with a given label, since there are n labels and n vertices in a chain. A remark on the appropriateness of the term "folded" in this connection will be made in the Appendix. Note that Fig. 4 is a folded tree, but Fig. 3 is not. 5

Fig. 3 Fig 4 Folded trees are important among labeled-trees because they can function as "complete decoding nets" in the sense giveYiiin [II],o We must explain what this means and why it is soo A circuit represented by a labeled-tree performs its function when the tree! input is Fn state 1 (e.g., after all the transfer contactsof a relay contact net are set, an electrical signal introduced at the tree input will, emerge at the desired output). We define a tree state of a labeled-tree t~ be a definite assignment of its vertex settings such that all vertices with the same label are set the same, and such that the tree input is in state 1. It is clear that there are 2m different tree states for a labeled —tree having m distinct labels, We say that an n-bay labeled-tree is coet decding if and only if the number of labels m is equal to n, and for each tree state there is at least one tree output which is in state 1 in that tree state and state O in every other tree state, It follows that there is only one tree output in state 1 in any tree state of a complete decoding n-bay. labeled-tree, since it has exactly 2n tree states and 2n tree outputs. 6 nearly identical concept of complete decoding is discussed in Section 3 of [Il].) Theorem 1T A necessary and sufficient condition;for a Labeled-tree to be complete decoding is that it be a folded tree Proof of necessity~. Consider an n-bay labeled-tree which is complete decoding. Consider any tree state S and the tree output Q which is in state 1 only in S. There is only one chain C which includes a Qr Suppose that, for some label -si there is no vertex in C labeled _Pi1o Now let S' be a different tree state which coincides with S except for the settings of the vertices labeled hi Q would be in state 1 in c' as well as in S, contrary to the assumption that the tree is complete decodingd Hence, every tree state stadetermines one chain such that for each tre utut'i tae i ay teestteo acopltedeclig -6y

label there is at least one vertex with that label in the chain, Different tree states determine different chains; and since there are 2n different tree states, there must be 2n different chains, each of which has the property that for each label there is at least one vertex with that label in the chain. But these are all the chains that there are, since an n-bay labeled-tree contains exactly 2n chains. Hence, any complete decoding labeled-tree is a folded tree. Proof of sufficiency: Consider any n-bay folded tree, Every tree output Q is on a chain C containing, for each label Pi, one and only one vertex labeled Pi. Hence, there is a tree state S in which all the wires of C (including Q) are in state 14 Also, for any different tree state S', there will be at least one vertex of C in a different setting and so Q will be in state 0 in S', Therefore, (1) each tree output will be in state 1 in one and only one tree state. FurthermoreL (2) any two tree outputs will be in state 1 in different tree states, which can be proved as follows. If Q1 and Q_2 are different tree outputs on chains C1 and C, respectively, then let i be the number of the latest bay in which C1 and X have a vertex V in common. Suppose that V is labeled'k, and suppose (without loss of generality) that C1 includes the upper vertex-output of V. C2 must then include the lower vertex-output of V. In order for Q1 to be in state 1, V will hate to be in;,,the upper setting, and, in order for Q2 to be in state 1, V will have to be in the lower setting, Hence, Q1 and Q2 are in state 1 in different tree states, Since there are as many tree states as tree outputs it follows from (1) and (2) that the tree is complete decoding. This completes our proof 6f Theorem 1. An -bay standard tree is an n-bay labeled-tree in which any two vertices have the same label if and only if they are in the same bay, Fig, 5. is a 3-bay standard tree. P 3 -. Fig. 5. 7

(If we interpret the vertices as in Fig,, 2, an n-bay standard tree is essentially the same as the 2-n tree defined in Section 4 of [ IIJ) Consider now two electrical devices, T1 realizing a 6-bay standard tree and T2 realizing a 6-bay folded tree in which the number of vertices labeled P1, -.., Pe, respectively, is 1, 129 12, 12, 13, 13. Both perform the same decoding function but the latter has a more nearly equal distribution of labels, Since all of the vertices with the same label are set in the same way at any one time, this means that the load distribution on the wires controlling the settingsof the vertices is more nearly equal in T2 than in T1. (The sequence 1, 12, 12, 12, 13, 13 will later be referred to as the "loading sequence" of the tree realized by T2. ) If the devices are constructed of relays (and for reasons indicated earlier in this section the tree is more important for relay contact nets than for electronic digital computing circuits), a further factor needs to be considered. This factor is the number of contacts that each available coil controls, One transfer contact can realize one vertex, but two contacts of the same relay cannot realize vertices with different labels,. If one had available relays with eight transfer contacts each, T2 with load distribution - 12 12, 12, 2,- 13, 13 would require eleven relays, while the (standard tree) circuit T1 would require only ten relays0 On the other hand, a (folded tree) circuit with load distribution 1, 8, 8, 15, 15, 16 would require only nine relays, Depending upon what physical equipment is available, different load distributions for a folded tree offer greater or less advantaged It is therefore of practical interest to know what different load distr ibutions are possible for folded trees. We are thus led to consider the interesting problem of determining how the Pi's can,: in general, be distributed among the 2n-1 vertices of a folded tree, More precisely, given a sequence of n integers a l,.., a n, is there an n-bay folded tree having, for each i, ai vertices labeled Pi? A condition for a sequence of positive integers to have a folded tree corresponding to it was stated in [I] and there proved to be sufficieent: That condition is the property of "admissibility" as defined in the following section. All the sequences discussed in the preceding examples have this property; 1, 2, 5, 6, 20, 29 is a sequence' that does not, In Section 3 of this paper we prove admisbibility to be as necessary condition also; and in Sections 4 and 5 we present and justify a method of construction which when applied to any admissible sequence of positive integers results in a folded tree corresponding to that sequence, thus providing a proof of sufficiency different from Shannon's earlier proof which was not constructive, 8

3. LOADING SEQUENCES; ADMISSIBILITY In this section we define an arithmetic condition on sequences of non-negative integers, which we shall call the condition of "adnissibility," and show it to be a necessary condition for a sequence to represent a distribution of labels among the vertices of a folded tree. To define "admissibility" we must first introduce some additional notions. Let V(i],), 1 - j' 2, be the jth vertex in the ith bay. Inasmuch as the bays are vertical in our figures, V(i1) is the top vertex of the ith bay, V(i,2) the vertex next to the top, etc. It is clear that the vertex-outputs of V(i,j) are.the vertex-inputs of V( i+l,2j-l) and V(i+l,2J). Now let us consider all the chains which include V(i,j). These all have a common vertex in each of the first i bays. That part of the labeled-tree which includes V(i,*) and all vertices from the last n-i bays which are on chains containing V(i,j), together with all vertex-inputs and vertex-outputs of those vertices, is itself a labeled-tree and is called a minor tree. We refer to it as T(i,j) since it is determined by V(i,j). T(1,1l) is, of course, the original labeled-tree itself. Note Fig. 6 in which T(2,2) is circled. We assume without any loss of generality that the m labels of T(1,1) are P1, P2..,Pjn. The index of m in!T2 I) is the number of vertices labeled ~ in T(i_-) which we denote by ak(i J). The loading sequence S(i,1) of T(li) is the sequence -a(ii),,..,,(i,j). Note that ak(i4) is sometimes 0. S(1,1>) is then the load.ing sequence of the original labeled-tree T(l 1). Fig. 6 9

In Fig. 6.. S(2,2) is 2, 2, 1, 2, while S(1,1) is 3, 5, 3, 4. Note that T( i,) ),'V~(ij)g SLij), and _(i,i) are functionally dependent upon the labeled-tree under consideration as well as upon i and j, even though that, functional dependence is not explicit in -our notation. Where S is a finite sequence of non-negative integers al, o-., am, we define M(S) to be the sequence rearranged in monotonic non-decreasing order, zeros deleted. Thus, if S is 3, 7, 5, 0, 2, 1, 0, 5, M(S) is 1, 2, 3, 5, 5, 7. A sequence S of m integers satisfies the unit condition if there is a 1 in the sequence. S satisifes the total sum condition if the sum of the terms of S is 2P-1, where p is the number of nonzero terms* S satisfies the partial sum condition if, fo~ each k = p, the sum of the first k terms of M(S) is 2 2 -1 A sequence S is admissible if it satisfies all of these three conditions. Thus',, 5, 0, 1, 0, 5, 4 is an admissible sequence in which m = 7 and p = 4; and 1, 9, 5, 10, 6 is an admissible sequence in which m= = 5 Theorem 2; A minor tree T(i,J) of an n-bay folded tree is an (n-i +l)-bay folded tree. Proof': Obviously T(i,J) has n-i+l bays. All the chains off T(l,l) containing V(i,a) have the vertices of the first i bays in common. These are labeled with exactly i of the labels. Now each chain must contain each of the remaining n-i labels in the last n-i bays. But these chains (with the vertices of the first. i-1 bays deleted) are the chains of T(ij). Hence, T(i,j) is'a folded tree. Theorem 3: In an n-bay folded tree S(i,j) has i-1 zeros and n-i+l non-zero terms. The proof is immediate from Theorem 2. Theorem 4: In a folded tree, if V(i,j) is labeled Pk, then ak(i.j) - 1. Proof: Since.V(i,_j) is labeled Go, no other vertex in any chain containing V(ij,) is labeled Pk. For suppose that V(i',j ), i' i, on a chain C with V(i,j) is also labeled Lk. Then C has n-2 other vertices which must (in order to satisfy the folded tree condition) be labeled with n-1 other labels which is impossible. 10

Theorem 5:~ In a folded tree S(i,j) satisfies the unit conditon. Proof: This follows directly from Theorem 4. Theorem 6: In a folded tree S(i,) satisfies the total sum condition. n-i+ 1 Proofo This follows from theorem 3 since there are 2 -1 vertices in T(i,2). Theorem 7: In an n-bay folded tree k(i+l,2j-l) = 0 if and only if ak(+1l,2j) = 0. Proof: T(i,j) by Theorem 2 is a folded tree and, therefore, each Pk which labels any vertex of T(i,j) has to label at least one vertex in each chain of T(i,i). Every such chain contains V(i,j). Beyond V(i,j) each chain of T(i,j) lies wholly within T(i+1,2j-l) or T(i+1,21). Hence any label occurs in T(i+l,2j-1) if and only if it occurs in T(i+l,2j), from which Theorem 7 follows directly. Theorem 8: In an n-bay folded tree S(i,A) satisfies the partial sum condition. Proof: The proof is by induction, beginning at the nth bay of the tree n-1 and going to the left. We'first show (1) that, for every 2, the theorem holds for S(n,j). We then show (2) that, if it holds for S(i+l,j) for every j - 2- it holds for S(i,j) for every j A 2i-1. (1) is true by Theorem 3 for S(n,j) has only one non-zero term. We prove (2) by showing that, if it holds for S(i+1,2j-1) and S(i+l,2j), then it holds for S(i,j). Suppose V(i,j) is labeled Pq. Let M(S(ni,j)) be aq(ij) agi(ii,)), g( ),.., gn-~(i,J), where, of course, aq(i,j) = 1 By hypothesis S(i+1,2j-l) and S(i+l,2j) satisfy the partial sum condition; in other words, for each k ~ n-i, the sum of the first k terms of M(S(i+l,2j-1)) or M(S(i+l,2j))'- 2k-l Now, if such a condition holds for a monotonic non-decreasing sequence, it holds for the sequence in any order. Furthermore, since, for k ~ q, nk(i,J) = ak(i+l,2j-l) + (i+1,2j1), with the aid of Theorem 7 it is easy to see that the non-zero terms of S(i+1,2I-1) are ~g1(i+l,2j-l),.. gnji(k+l,2l) and the non-zero terms of S(i+l,2j) are agl(i+l,2j),...( +gnj(i+1,2j). Hence for 11

each k n- i, (i+1,2j-1) - 2 -1 and agx(i+l12i) 2k -1. Hence, (i,2j-) + gx(i+l,2j)) -2. Clearly, x=l1 k k 2aqCi~~.) +> X(i,) = 1 +Z(agx(i+l,22.1- 1) + a (i+l,2j)); hence for any k - n-i, i 2k+ -1, which means k+1 that the sum of the first k+l terms of M(S(i,s)) is 2+-1, proving that S(ij) satisfies the partial sum condition. Theorem 9: The loading sequence S(1,1) of an n-bay folded tree is an admissible sequence of n non-zero terms. This result follows immediately from Theorems 3, 5, 6, and 8, putting i = j = 1. 4. THE'SPLITTING TECKNIQUE In this section we provide an effective method of constructing a folded tree with a given admissible loading sequence of positive integers., The proof that this method will produce a folded tree is given in the next section, The procedure consists in taking the loading sequence proposed for the folded tree T(1,1), selecting the unit term for V(1,1), and dividing the remaining terms so as to yield two admissible sequences, one for T(2,1) and the other for T(2,2)o This procedure, called the "splitting technique", is then repeated for each of those two sequences to provide admissible sequences for T(3,1), T(3,2), T(3,3), and T(3,4), The process is iterated until T(n,2n-1) is reached, It will be proved in the next section that each vertex isthus provided with a label and that,for each k, the proper number of vertices will be labeled It must be admitted that there are alternative splitting techniques which applied to the same admissible sequence give different folded trees. Our splitting technique, for example, applied to the admissible sequence 1, 4, 5, 5 gives a folded tree having three different labels in its last bay, but there is also a folded tree with the same loading sequence which has only two different labels in its last bay (see Fig. 7). 12

Fig. 7 In this section and in Section 5 we let S'(i.j), which is a_(iQW), a~(i,A), A..., a(i,j), be the sequence obtained by repeated applications of the splitting technique from S'(ll), which is an arbitrary admissible sequence without zero terms. The symbols S'(i,j) and S(ij) are to be clearly distinguished even though in some cases they refer to the same sequence of numbers. S1(i~j) is the sequence derived by our splitting technique from a given admissible sequence S'(ll), whereas S(i.,) is the loading sequence of T(ij), a minor tree of a given labeled-tree. Let us suppose that S'(i_~) is a given admissible sequence. We describe now the splitting technique which determines S'(i+l,2j-l) and S'(i+l,2j)o For every k, if alji,j) = 1 or 0, then let a'(i+!,2j-1) = a~(i+l,2i) = O Let M(S' (il,)) be 1,dL~ oalm dips (It will turn out that n = n-i.) We then determine sequences b1,.. - b } and. ci,.... p, such that if dx is a(ji9), b L and a are to be a(i+,2j-1) and a'k(i_+l,2), respectively'. The recursive procedure for determining bx and C is as follows (1) put c1 = 1 and b1 = d.ll; (2) if bk = 1 (i.e., if d. = 2), proceed to (3), otherwise first put b = 1 and c2 = d2-l; (13) (for each xX x = 3, and, for x = 2 if d1 = 2) assuming that bl, o., b and cl, *.ga cx_ have been determined, put P4 P2 13

and an F dx+ 1+ - Ax %x [ ~2 J where x-1 y=l Here [~], for any real number ~, is the integral part of, i.e., the greatest integer not greater than, The reader can readily verify that for each x, bx + x = dAx In actual calculation the work is even simpler than it appears from the formal statement of the procedure. The idea behind the splitting technique is simply to provide for the 1 in each sequence, and., for each d.x, to find a bx and c such that b + = -, in such a way that x fb YT is as nearly equal as possible to c.y y=l We also require that x y=l be never less than x fib y=l except where dl > 2 and x = 2. Thus, all terms except possibly the first three will be split as evenly as possible so that Ax for x > 3 is either O or 1. For x > 3, then, if dx is even, b = x -= /2; if dx is odd and Ax is 1, then x - (d +1l)/2 and a = (X-l)/2; if dx is odd and Ax is O, then b = — l)/, 14

and.x = (dx+l)/2- Furthermore, Ax does not have to be recalculated each time for x > 3; for if d x is even, then Ax+1 = AxI and if d is odd) then A is 1 if Ax is 0 and 0 if A is i. -x x+ t x The following table carries through a calculation from S'(i,j) to S'(i+1,2j-1) and S'(i+l,2j). S'(i,j) 0 3 0 1 8 14 d-sequence 3 5 14 b-sequence 2 1 5 7 c-sequence 1 4 3 7 S' (i+1,2j-1) 0 2 0 0 5 7 1 S'(i_+l,2j) 0 1 0 0 3 7 4 It is simple to rearrange the terms of the b and c sequences in forming the sequences S'(i+1,21-l) and S'(i+1l,2j) in accordance with the rule that where d is a_(ij) bx and. i are +_(il, 2j-1) and a_(i+1,2jL), respectively. To illustrate the case where dl = 2, consider the M(S'(i,j)) sequence 1, 2, 5, 9, 14. Here the b-sequence is 1, 2, 5, 7 and the c-sequence is 1, 3, 4, 7* Since we have shown how an admissible S'(i-,i) is split into S'(i+l,2j-1) and S'(i_+l,2j), it is easy to see that given S' (1l1) all the S'(i,) can be calculated, provided all the applications of the splitting technique yield admissible sequences. Once all these have been calculated, a folded tree whose S(i,) is S'(i,j) can easily be constructed. If there are n terms in S'(1,1), then, of course, we want an n-bay folded tree. An n-bay tree is constructed and each vertex V(i,j) is labeled Pk where a(i,J) is unity. (In the next section we prove that a vertex will be assigned one and only one label by this procedure.) We will now provide an example showing the use of this procedure in constructing a 5-bay folded tree with the given admissible loading sequence, 1, 7, 7, 8, 8, which is one of the most evenly balanced loading sequences possible for a 5-bay folded tree. We omit the d-sequence, as well as the b-sequence and c-sequence, in each step. 15

Since S'(1,1) is 1, 7, 7, 8, 8, S'(2,1) is O, 6, 1, 4, 4, and S'1(2,2) is 0, 1, 6, 4, 4; S'(3,1) is 0, 3, O, 3, 1, and S'(3,2) is 0, 3 0, 1, 3; S'(3,3) is 0, 0, 3, 3, 1, and S_'(3,4) is O, 0, 3, 1] 3; S'(4,1) is 0, 2, 0, 1, 0, and S'(4,2) is O, 1, 0, 2, 0; S'(4,3) is 0, 2, 0, 0, 1, and S'(4,4) is 0, 1, 0, 0, 2; S'(4,5) is 0, 0, 2, 1, O, and S'(4,6) is 0O,, 1, 2, 0; S'(4,7) is O, 0, 2, O, 1, and SI(4,8) is O, 0, 1, 0, 2S For each i,J we label V(ii) Pk where the kth term of S' (i,) is unity. It is not necessary to compute S'(5,j) for any'I, since every V(5,j) can be labeled with that label which has not already appeared in the chain containing that V(54,). The result is Fig. 8, 1 6 Fig. 8 16

Ma THE VALIDIDiTY OF THE SPLITTING TECHNTQUE In this section we show that, given any admissible n-term sequence S'(ll) containing no zeros, theprocedure specified in Section 4 always results in a folded tree whose loading sequence S(L,1) = S' (1,31) Thus we have a constructive proof that the admissibility of any sequence of positive integers is a sufficient condition for it to be the loading sequence of a folded tree. The most difficult part of the proof is to show that the splitting technique is admissibility-preserving, i.e,} to show that the sequences S'(i+l,,2-l) and S'(i+1,2j) which result from St(ij,) by the splitting technique are admissible if S' (itj) is admissible. (We do not give a complete proof here but rely on the results obtained in []VI We shall, however, present enough of the proof to give an intuitive understanding of the argument,) Theorem 10 If S'(i,ij) is an admissible sequence with at least two non-zero terms, then the two sequences which result from applying the splitting technique to it satisfy the unit condition. Proof (here and in the following proofs we use the r:alan developed in Section 4): Since S' (i,) has at least two non-zero terms, dl must exist. d-1 > 1 since M(S'( i,)) satisfies the partial sum condition, If d = 2, then bl = cl = If dl > 2, then S'(i4J) cannot have exactly two non-zero terms, otherwise S' (ij) would not satisfy the total sum condition; hence, d also exists and cl _ l= 1 Theorem 11o Both of the sequences which result from applying the splitting technique to an admissible sequence satisfy the total sum condition, Proof: We need two lemmas, Lemma 1 If 4 ~ x p + l1 then A = 0 or 1; if dl = 2, then this is so for x = 1,2,3 as well, The proof is by induction, and can be found on p. 35 of [IVJ] (Lemma 1). (Note that t"dT"t of this paper corresponds to "ai" of [IV],) 17

Lemma 2. Ap + 1 = 0. Proof: We show first that Ap + 1 = 0 or 1 By Lemma 1 the only possible exceptions to this would be where dl > 2 and p = 1 or 2. If P = 1, then d1 = 2, inorderthat M(S'(i,j)) satisfy the total sum condition. If p = 2, then dl + d;a = 6 by the total sum condition. If dl.> 2, then d1 = d2= 3, since the d-sequence is monotonic non-decreasing. Here cl = b2 = 1 and bl = c2 = 2 so that A3 = 0, Having shown that in every case Ap + 1 0 O or 1, we must now show that the -value is actually 0* As mentioned in the preceding section, for each x- cx + bx= d-; hence, P P P x=l x=l x=But, since:iM(S'(i,J)) satisfies the total sum condition, P X, = 2P+1-J. x=l which is even. But Ap+1 is precisely the difference between p x=l anid Ib.x x=l If Ap+l were 1, then their sum would have to be odd. Hence, A = 0. The theorem now follows directly, Since Lemma 2 entails that Xp x=l1 18

and p x=l are equal, it follows that P P P _x B= 2>x = 2>x = 2P -2 x= x=2 Hence, P P >b = = 2P-1..... x=l x=l and Theorem 11 is proved.. Theorem 12: If b1,..., bp and cl,..., are the sequences which result from the application of the splitting technique to an admissible sequence S'(i,j), then for every x such that 1 = x X ~ Er -Y y=l and x 2X-1 y=l This is proved as Lemma 3 on p. 34 of [IV ]. (The "derived order", as the term is used in [PiV], is the order bl, b,. *, b and cl, c2,..., Cp as opposed to the monotonic order.) Roughly, Theorem 12 follows because M(S' (i,)) satisfies the partial sum condition and the x-th term of the b-sequence and the xth term of the c-sequence are usually obtained from the (x+l)st term of M(S'(i,J)) in such a way that x y=l 19

is nearly equal to x y=l Thus Zby y=l is approximately x y=l Since l, dl, o.., d are the first x + 1 terms of M(S'(iJ)) and,since S'(i,j) satisfies the partial sum condition, x i + d' 2X+l 1 and hence 1/2>dy d 2X-l y=l Theorem 13: If S'(i,]) is admissible, then S'(i+l,2J-1) and S'(i+1,2:) satisfy the partial sum condition. This is proved as Theorem 3 on p. 40 of [LIV]. In order to prove Theorem 13 one must extend the result of Theorem 12; for the b-sequence and c-sequence are not always in monotonic non-decreasing order, and a sequence satisfying the summation condition of Theorem 12 may no longer satisfy it when monotonized. Fortunately, it can be proved that after the third term the b-sequence and c-sequence are each, in the terminology of [IV], quasi-monotonic, i.e., for any x and x', if 4 - x < x' x p, then _ = b, + 1 and Rx a x, + 1. It is rather easy to show by virtue of this fact and Theorem 12 that, for each x, x ~ 2-1 y=l 20

where bo,..., bp is monotonic after the third term and results from bl,..., bp by interchanging the appropriate terms after b3; similarly for the c-sequence. (Cf. the theorem on p. 18 on [IV].o) The extension of this result to the case where the first three terms are rearranged to make the entire sequence monotonic is made in the proof in [IV]. Theorem 14:- For every i < n, if S'(i,j) has n terms including exactly i-l: zero terms and is admissible, and if S'(i+l,2j-l) and S'(i+1,2j) are obtained from S'(i,j) by the splitting technique, then S'(i+l,2j-1) and S'(i+l, 2j) are admissible and each contains exactly i zeros. Proof: That these are admissible follows from Theorems 10, 11, and 13. S'(i+1,2j-1) differs from b,..., bp in at most the presence of zeros and the otder of terms, which does not affect admissibility; similarly for S'(i+l,2j) and cl,..., Cp. To prove that they each have i zeros, it suffices to prove that there is one and only one unit term in S (i,j). That there is one follows from the fact that S' (i,) satisfies the unit condition. That there is only one follows from the faCt that S (ij) satisifes the partial sum condition; for if there were at least two, then the sun of the first two terms of M(S'(i,j)) would be 2 < 22-1. Theorem 15: Given S'(l,l) as an admissible n-term sequence without zeros, the procedure specified in Section 4 results in an n-bay folded tree whose S(1,1) = S'(1,1). Proof: From Theorem 14 it follows that for any j < 2n-1 the sequence S'(n,j) has n-1 zeros and is admissible. Its one non-zero term, say, ak, must be unity by the total sum condition, and so V(n,j) is labeled Pk. Therefore, (1) S'(n,j) is:S(nj) and T(n >) is a folded tree. We now go on to prove that (2) for any i and j, if S (i+1l,2-1) is S(i+1,2j-l) and S'(i+1,2)) is S(i+l,92), and if T(i*+1,2j-1) and T(i+l,2j) are folded trees, then S'(l,j) is S(l,) and T(ij) is a folded tree, There is a set 21

of n-i distinct labels such that each chain of T(i+l,2j-l) contains exactly one vertex labeled with each member of the set. The myth,..., _mith terms of S(i+l,2j-l), which is S'(i+l,2j-1), arel exc:tly those terms which are non-zero terms. There is a similar set for T( i+l,2). Now this set is identical to the set for T(i+l,2j-1), since for any q the qth term of S'(i+l,2j-1l) will be made zero by the splitting technique if and only if the qth term of S'(i+l,2j) is made zero. If V(i,j) is labeled _k, then k is not one of the m,..., mn_i; this is so because the kth term of S'(i,j) is one and, therefore, the kth term of S'(i+l,2j-l) and the kth term of S'(i+l1,2j) are each zer6. From this it follows that every chain of T(i,j) has exactly one vertex labeled with each member of the set -k lml P_ -miP since a chain of T(i,j) is either a chain of T(i+l,2j-1) or a chain of T(i+l,2_j)- with V(i,ji) and its vertex input added. Hence T(i,j) is a folded tree. Now each term of S'(i,j), except a(i,j) = 1, is equal to the sum of the corresponding terms of S'(i+1,2j-1) and S'(i+l, 2j); (i_+1,2j-1) = a_(i+l,2j) = 0. (This follows from the specification of the splitting technique.) Since the vertices of T(i,j) are those of T(i+l,2j-1) and T(i+l,2J)I together with V(i,j), it follows, from the fact that S'(i+l,2j-l) is S(i+1,2j-l) and S'(i+l,21) is S(i+1,2J), that S'(i,j) is S(i,j). From (1) and (2) it follows immediately by induction that S'(1,1) is S(1,1) and T(l,l) is a folded tree. 6. THE ECONOMY OF THE FOLDED TREE The question arises as to whether circuits represented by folded trees are the most "economical" ones which can function as complete decoding circuits. As we have indicated earlier (Section 2) the answer is in the negative so far as electronic digital computing circuits are concerned (see also Section 5 of [Ll). However, folded tree relay transfer contact nets are probably the most economical (in a sense to-be defined) of all complete decoding relay transfer contact nets. To formulate this proposition precisely we must delimit the class of diagrams whose realizations are all such complete decoding relay transfer contact nets. Our definition of vertex diagram at the beginning of Section 2 was motivated by two considerations: (1) that a relay transfer:contact is well represented by a vertex with a single vertex-input and two vertexoutputs, and (2) that in a relay transfer contact net the relay 22

transfer contacts can be arbitrarily connected., Hence any relay transfer contact net can be represented by some vertex diagram, In this section we go on to define ann-label -complete decoding vertex diagram in such a way that every transfer contact net which performs a comp'lete decoding function is represented by a diagram of this kind. Our belief that folded tree relay transfer contact nets are probably the most economical of all complete decoding relay transfer contact nets can now be more precisely stated as the conjecture: The n —bay folded tree has the minimal number of vertices of any n-label complete decoding vertex diagram, The objection may be made that the minimality of the number of vertices of a complete decoding vertex diagram is not a sufficient condition for its realization by relays to be minimal in cost, for the cost of a relay transfer contact net depends not only on the number of transfer contacts in it but also on the number of relay coils required to operate it o To particularize this objection, consider the problem of constructing a complete decoding net using only relays with eight transfer contacts each; here the number of relays required is a better indication of the cost of the net than the number of transfer contacts it contains, There is a certain force to this objection. However, it is to a large extent mitigated by our previous folding results. For if an n-bay standard tree circuit has a minimal number of contacts, we can in practice use that folded tree circuit which of all n-bay folded trees has the least number of relay coils. For an example see the last part of Section 2. When relays with different numbers of contacts are available at costs which are not directly proportional to the number of contactsthey contain, then a different. folding can be employed to minimize the total cost of the circuit, We have: not proved our minimality conjecture, but in this section we present a partial result in that direction. To this end we will introduce a certain subclass of the class of n-label complete decoding vertex diagrams, namely, the subclass of all n-label progressive diagrams. We shall prove that the n-bay folded tree has the minimal number of vertices of an n-label progressive diagram, It seems, intuitively, that an n-label complete decoding vertex diagram which is not an n-label progressive diagram should have at least as many vertices as an n-bay folded tree, and it is on this ground that we make our conjecture, We now proceed to carry out the program sketched above, Since all the vertex diagrams considered in previous sections were trees, we first present an example of a vertex diagram that is not a tree (Fig, 9), (Note the use of the loop in the wire W of Fig. 9 to indicate that the wire W does not touch the wire V.) 23

Fig. 9 Some of the concepts already introduced in connection with trees must be generalized to apply to arbitrary vertex diagrams, First, we require a more general method of describing the way states of wires are determined. To accomplish this we define the notion of the connection of two wires. We say that two wires are directly connected when they touch each other. A vertex is directly connected to a wire whenever the wire is either its vertex-input, or its-tipr (lower) vertex-output when the vertex is in the upper (lower) setting, Two wires W and W' are connected if there is a sequence of wires and vertices [Xl, oo _. (n 4 1) such that W is X1, W' is Xna and suceh that.. for each i < n, Xi is directly connected to Xi+l. By taking n we see that any wire is always connected to itself. The sequence X1, *W.}'n is a connection of W and W'. Thus, whether two wires in a diagram are connected usually depends upon the settings of some of the vertices of the diagram. An n-label complete decoding vertex diagram wilth designated diagram input and diagram outputs) is a vertex diagram in which the following hold. 1. Each vertex' V has exactly one label from a set of n distinct labels. 2. For each label there is at least one vertex with that label, 3. There is exactly one wire K' designated as the diagram inp ut. 4. A diagram state isadefinite assignment of the vertex settings such that (a) all the vertices with the same label are set the same, and (b) a wire is in state 1 if and only if it is connected to the diagram input,

5. For each diagram state, there is at least one wire which is in state 1 in that diagram state and in state 0 in every other diagram state, and for each diagram state one such wire is designated (arbitrarily, if there is more than one) as a diagram output of the diagram. The diagram input is in state 1 in any diagram state since it is always connected to itself. Since there are n labels for the vertices, there are 2n diagram states, and, therefore, 2 diagram outputs. For any diagram output, (Q), let S(Q) be the diagram state in which Q is in state 1. Sometimes in these diagrams a vertex may have the state of its vertex-input depend on the state of one of its vertex-outputs. For example, consider the uppermost vertex of Fig. 10. When it is in its lower setting, the state of its vertex input Q2 depends upon the state of its lower vertex output. For this reason the terms "vertex-input" and "vertex-output" are not as appropriate for the more general class of vertex diagrams as they are for the class of trees. Obviously, trees are vertex diagrams, and by Theorem 1 n-bay folded trees are complete decoding n-label vertex diagrams. For an arbitrary connection X1,..,_, if Xk is directly connected to _ for m > k + 1, then Xk+l. m-1 are superfluous; the sequence with them deleted is still a connection. It is easy to see, therefore, that in a diagram state, 5, if there is a connection between W and W', then there is a connection between them in S without any superfluous vertices or wires. A chain of a diagram output Q is a sequence X1,...,_% of wires and vertices which in S(Q) is a connection of the input K and Q without any superfluous elements. Obviously, the chain as defined in Section 2 is a chain in this sense. If X1},..}.*>m is a chain C (where X1 is the diagram input K and m is a diagram output), then for any i,J such that i < j we say that Xi is earlier than X. in C. If Xi is a vertex, then X- and Xi+ are wires l the vertex, one being the vertex-input of Xi and the other being one of the vertex-outputs of Xi; we say that Xi_1 is the early wire and Xi+l the late wire of the vertex Xi in the chain C. If the early wire of a vertex in a chain is the vertex-input, then we say the vertex is oriented forward in the chain; if the early wire is a vertexoutput, then the vertex is oriented backward. For example, the vertices labeled P2 in the chains of Q1 and Q2 in Fig. 10 are backward, whereas the vertex labeled P2 in the chains of Q3 and Q4 is forward in both those chains. The vertex labeled P1 is forward in all chains. 25

Fig, 10 A progressive diagram is a complete decoding vertex diagram in which each output Q has at least one chain in which all vertices are forward. The folded tree is a progressive diagram while Fig. 10 is a complete decoding vertex diagram which is not progressive. An output Q of a progressive diagram may have more than one chain in which all vertices are forward. It is convenient to pick out for each output Q of a progressive diagram one such chain and refer to it as C(Q), or the selected chain of'the output~ Where Q and Q, are two distinct diagram outputs of a complete decoding vertex diagram, we define V(Q,Q'T) to be the latest vertex V in C(Q) whose early wire is in state 1 in S(Q' ) and whose late wire is in state 0 in S(Q')e Such a vertex must exist since the diagram input K is in state 1 in S(Q') but Q is in state 0 in S(Q'); the latest wire of C(Q) which is in state 1 in S(Q') must be the early, wire of a vertex in C(Q>). For example, in Fig, 11 V(Q1,Q_4) is the vertex labeled P1 in C(Q1) and V(Q49Q1) is the vertex labeled P2 in C(Q4)o This example shows, incidentallay that V(Q,Q_') and V(QQ) are not always identical. p2 Q1 Q3 Fig. 11 26

Whenever A is any set of outputs of a progressive diagram we let D(A) be the set of just those vertices V(Q,,Q') where Q and Q' are both in A. If A has only one output Q, then D(A) is the null set, since there is no V(Q,Q). For any set A and any output Q not in A, A+Q} is the set whose members are Q and all the members of A. Theorem 168 If A is a set of one or more outputs of a progressive diagram, and if Q is an output not in A, then there is a vertex in D(A+L]") which is not in D(A). Proof: Let V be the latest vertex V(Q,41') in C(Q) where Q' is in A. We shall prove that V is not in D(A), from which Theorem 16 follows directly since V must be in -DA+Q_). We shall use the reductio ad absurdum method. Suppose that V is in D(A). Then there are diagram outputs Q" and Q""' in A such that V is V(Q"Q_)l'). Let x be the early wire of V in C(Q) and y the late wire. Since the diagram is progressive and since V is in C0(Q), x is the vertex-input and y is a vertex:output of V. Let z be the other vertexoutput of V. Since V is V(t",I"'t) x is in C(Q"t) and either y or z is in C(Qt ) Case I. y is in C(QQ"). Then' is in state 1 in S(Q"). The latest wire in C(Q) which is in state 1 in S(Q"), then, can be no earlier than y, and hence V(Q,Q") is later than V in C(Q), contrary to the original stipulation that V be the latest such vertex in C(Q). Case II. z is in C(Q")e Since V is VQV",Q" t'), x must be in state 1 in S(Q"' ), and z in state 0. This means that the setting of the vertex V in S(QT ) must be such that y is in state 1 in S(QT'') Reasoning as in Case I, then we can show that V(Q,Q"') is later than V in C(Q), which is likewise contradictory. This completes the proof of Theorem 16. Theorem LI7: In a progressive diagram, if A is a set of k outputs then there are at least k-l vertices in D(A). Proof: Let A2,..,Ak be a sequence of subsets of A such that k is A, i has exactly i members, and, if 2 = i - k-l, &j is a proper subset of Ai+- Thus, Ai+1 has just one member besides those of - i. There is at least one vertex in D(A); and by Theorem 16 D(Ai+l) has at least one more vertex than D(Ai). Hence, D(Ak) has at least k-1 vertices, 27

Theorem -18: In the class of n-label progressive diagrams the n-bay folded tree has a minimal number of vertices. Proof: In an n-label complete decoding vertex diagram there are 2 outputs. If A is the set of all these outputs, the D(A) must have at least 2n-1 vertices. Hence, the diagram must have at least 2 -1 vertices which is the number of vertices in the n-bay folded tree. 7, A GENERALIZATION OF THE FOLDED TREE In this section we shall consider generalized folded trees containing vertices all of which have the same arbitrary number of vertex outputs and possible settings. A vertex with m vertex-outputs is called an m-order vertex and its m settings are the first setting, the second setting, oong the mth setting, The ith vertex output is the ith right-hand wire from the top. (See Fig. 12,) A generalized n-bay folded tree containing vertices of order m, called an n-bay m-order folded tree, obviously contains x- = ( x=l vertices.d Thus an n -bay folded tree as previously defined has order 2. The definition of "complete decoding" is the same as that given in Section 2, and the generalization of Theorem 1 goes through quite easily. 28

It is not difficult to see what sort of physical realization an m-order vertex can have, either in relay circuits or in electronic digital computing circuits. In relay circuits the m-order vertex represents a single-pole m-throw switch, eog,, a stepping switch, In electronic digital computing circuits the m-order vertex can represent an arrangement of m conjunction elements generalized from the arrangement of Fig. 2. As in Section 2 we ask the question, for a given loading sequence, al},,,, a, is there an n-bay m-order folded. tree having a, vertices labeled P19 a.., and a vertices labeled P? We have a generalized condition of "admissibility" which we can prove to be necessary and which we conjecture to be sufficient if the sequence contains no zerosd Our generalized condition of admissibility involves four conditions, as compared with only three in Section 35 A sequence satisfies the unit condition if there is a 1 somewhere in the sequence, It satisfies the total sum condition if the sum of all the terms is equal to p mP-l)/(mi-) =(m" = where p is tne number of non-zero terms, A sequence S satisfies the partial sum condition if, for each k: p, the sum of the first k terms of M(S) is greater than or equal to k k x=l It satisfies the congr.ence condition if, for each term k ak l(mod m-l), i.eo, ak- i is divisible by m-l, A sequence is admissible if it satisfies all four conditions, Note that admissibility as defined in Section 5 is a special case (mn 2) of this more general notiorn of admissibility, for any sequence of integers-satisfies -the congmrence condition when m = 2, Theorem 19: The loading sequence S(1,1) of an n-bay m-order folded tree is an admissible sequence of n non-zero terms, Proof: Obviously, S(1,l) must satisfy the unit condition and the total sum condition, The reader can reread Theorem 8 and its proof and see that it very easily generalizes from the case (m= 2) to prove that S(l,1) satisifes the partial sum condition for any _ m To demonstrate that S(ll) satisfies the congruence condition we consider any n-bay m-order folded tree having ak(l,l) vertices labeled Pko Suppose that 29

for each h - n there are kn vertices labeled P in the hth bay. There are mn chains and each chain must have exactly one vertex labeled — k. n-h+ i But a vertex in the hth bay is on exactly m chains. Hence (1) the number of chains is equal to n X n-h1 n i mn h=l By elementary number theory we know that for any non-negative integer x' n-h+x_, m - l(mod m-l). Thus, for each h, khn l - kh(mod m-l). Hence (2) n n n-h+l_ - kh(mod m-l). h=l h=l From (1) and (2), since mn - l(mod m-l), it follows that n ak(l,l)) = Ikh - l(mod m-l). h=l This completes our proof of Theorem 19.

APPENDIX Interchange and the Folded Tree The phrase "folded tree" is appropriate because a folded tree can be obtained from the standard tree of Section 2 by the technique of "folding." That technique, perhaps better described as "interchange," can be defined as follows. An n-bay labeled-tree T' (1,1) results from an n —bay labeled-tree T'(1,1) by an interchange of P and P in the minor tree T(i9j) when all the vertices labeled ih In T(ij,) are labeled Pk in T'(iJ) and vice versa, all other vertices of T'(11l) being labeled the same as in T(1,1). By referring to the definition of "folded tree", it is not difficult to see (1) that if T'(,1) is obtained from T(1,l) by interchange, then T'(1,1) is a folded tree if and only if T(L,1) is. It can also be shown (2) that for any n-bay'folded trees T(ll) and. T1 (i,1) having the same set of labels, T' (1,1) can be obtained from T(ll) by a sequence of interchanges. For suppose T1(1,1), T2(1-1),.o., is a sequence of distinct n-bay labeled-trees where T1(l,l) is T(1,1) and where T (1-,1) is obtained from T1x(l,1) by the following process. Having ordered all the vertices of T (1l,l) in the sequence V(ll)) Vx(2,1)O_(2,2),V_3yl)Vx(32),...J we consider the first vertex V (ij) which haS a label different from the corresponding vertex V'(i,) of T'(ll)0 Suppose that P. and Xk are the labels of Vx(is) and V'(ij), respectively " Then xe+l(l~l) results from I (1,1)'by interchange of P and P in It is easily seen that k must label at least two vertices in iT (ij), so the interchange can always be made if 7(l,1) is not iden-ical with T'(l1,1). Obviously, then the label of l'i) and the labels of all vertices of Tx (11) which precede V +l in the ordering of vertices mentioned above are the same as the labels of the corresponding vertices of T'(ll1). it is not difficult to see that the sequence T(1l,1), 2(l,l1),.. has a last member q(1,1) which must be T'(11). Since a standard tree is a folded tree, it follows from (1) and (2) thata necessary and sufficient condition that an n-bay labeledtree with labels Pl, -..., P be a folded tree is that it be obtainable from the n-bay standard tree by a sequence of interchanges. Everything asserted in this appendix is true also of trees all of whose vertices are of order m > 2. 31

BIBLIOGRAPHY [I] Shannon, C E.,, "The Synthesis of Two-Terminal Switching Circuits," Bell System Technical Journal, Vol. 28, pp. 59-98, January, 1949. [I~] Burks, A. W., R. McNaughton, C. H. Pollmar, D. W. Warren, and J. B. Wright, Cmlete Decoding Nets: General Theory and Minimality, ERI-1828-1-T, Ann Arbor, July 15, 1954 (Burroughs Corporation, Research Center, Paoli, Pennsylvania). To be published. [III] Keister, W., A. E. Ritchie, and S, H. Washburn, The Design of Switching Circuits, New York, 1951.: [IV] Burks, A, W., C. H. Pollmar, D. W. Warren, and J. B. Wright, "Minimal Switch Theory and the Folded Tree," Vol. III, Lan uage Conversion For Digital Computers, ERI Project M828, Ann Arbor, 1 March 1953, (Copies may be obtained by writing Mr. George W. Patterson, Burroughs Corporation, Research Center, Paoli, Pennsylvania, ) 32