THE UNIVERSITY OF MICHIGAN COLLEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Technical Note THE NUMBER OF CLASSES OF INVERTIBLE BOOLEAN FUNCTIONS Michael A. Harrison ORA Project 04879 under contract with: UNITED STATES AIR FORCE AERONAUTICAL SYSTEMS DIVISION CONTRACT NO. AF 33(657)-7811 WRIGHT-PATTERSON AIR FORCE BASE, OHIO administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR July 1962

SUMMARY In a recent paper, C. S. Lorens4 has focused attention on invertible Boolean functions. Lorens has counted the number of classes of such functions by considering the same group acting on both the domain and range of such functions. In this work, we give an algorithm for obtaining Lorens' results and extend his work to allow different groups on the domain and range. iii

I. INTRODUCTION The work of C. S. Lorens4 has focused attention on the invertible Boolean functions. Since Boolean functions are also ordinary functions, a function f is invertible (i.e., has an inverse) if and only if f is one-toone and onto. That is we are considering one-to-one onto mappings of {0,13 into (0,1. These are just the 2n! permutations of [0,1] Lorens has counted the number of classes of such functions when one allows the same group to operate on the domain and on the range. These results will be generalized in this paper. Three different groups will be considered as.transformation groups on,n Boolean functions. I will denote the group of all 2n complementations of the variables; ) will denote the group of all n! permutations of the n variables, and n denotes the least group containing both and. > n 2 On gn The order of is of course n!2 in order to carry out our calculations 2 we shall use a combinatorial result due to De Bruijn. II. DE BRUIJN' S THEOREM Consider a class of functions from a finite domain D to a finite range R. Let t and - denote permutation groups acting on D and R respectively. Two functions fl and f2 are called equivalent if and only if there exist elements oa 6 ~ and E a such that fl(d) = pf2(a(d)) for all d C D. This equivalence relation decomposes the family of all functions into equivalence 1

classes. We desire the number of sUch classes. The statement of the pertinent theorem will require the cycle index polynomial of a group. Let t be a permutation group of order g and degree s. Let fl,...,fs be s indeterminates and let gj l,, s be the number of permutations of O having jk cycles of length k for k = 1,2,...,s. Naturally LiJi = s (1) i=l Then the cycle index of C; is defined as Z = g. j fl if22.. fs where the sum is taken over all partitions of s which satisfy (1). It is now possible to state the theorem of De Bruijn which we shall use. Theorem 2.1. The number of classes of one-to-one functions is h (^' 1,.., ( + zl, 1+ 2z2,...,1 + sz) evaluated at zl = z =.. = z = 0. It is clear that before proceeding we shall need to know the cycle indices for, and C. Ashenhurst first calculated the cycle index 2 Qn n for while Slepian5 first counted the classes under CC. The explicit l^2 t n polynomials are given in Reference 3 and the result is quoted below without proof. 2

Theorem 2.2. 1 f 2n n 2n-1) Z-.n - n ( n + (2 - l)f2 1 *2 n 2~k'=~l~~. - n'. J~ n:v i X (T fde(d)) 1 n: n! e(d) gkk fd n n d d n = n'2 (j) k i di Jkek d12i k=l where the last two cycle indices are summed over all partitions of n such that n j iji = n. The functions e(d) and g(d) along with the cross operation (x) i=l are defined in Reference 3. III. APPLICATIONS The following lemma will facilitate our calculations. Lemma 3.1. A term of the form a zi b zi (l+kl zk) = z =s = ab Xk kp mp if ii = kl,...,i = ks p=l yields 0 otherwise. 5

Proof. Notice that unless the cycle structure of the term involving the differential operator is the same as the term involving the variables, the result will be zero. If i1 = kl,...,is = ks, then ml = Jl,...,ms = js and the result follows from the rules of differentiation. — n We will first apply this lemma to the case where L acts on both the domain and the range. -n Theorem 3.2. The number of classes with L acting on both the range and the domain is given by n (2n, + (2n _ 1)2(2n-1')22 2n The calculations for the other cases have been carried out and are summarized below. It would require a computer to evaluate the results for n = 5 and most computers would require at least triple precision arithmetic to accomplish this. These answers agree with those of Lorens except in the case n = 4 with the symmetric group on both the range and the domain. Since we are dealing with invertible functions, the results with (O acting on the domain and - acting on the range are exactly the same as with and'interchanged. 4

n L- ~ ~~2 n n Number of Invertible on Range on Range f on Range Functions and Domain and Domain and Domain 1 2 1 2 1 2 24 6 7 2 3 40,320 924 1,172 52 4 20,922,789,888,000 81,738,720,000 36,325,278,240 142,090,700 rn ~n on Domain on Domain on Domain n 2 2 n n Range n on Range Hn on Range 1 1 1 1 2 3 3 2 3 840 196 154 4 54,486,432,000 2,271,124,800 2,270,394,624 5

IV. ACKNOWLEDGMENT I wish to thank Dr. B. Elspas for pointing out the work of Lorens and suggesting this problem. 6

REFERENCES 1. Ashenhurst, R. L., "The application of counting techniques," Proceedings of the Association for Computing Machinery, Pittsburgh Meeting (1952), pp. 293-305. 2. De Bruijn, N. G., "Generalization of Polya's fundamental theorem in enumerative combinatorial analysis," Koninklijke Nederlandse Akademie Van Wetenschappen, Series A, Vol. LXII, No. 2 (1959), pp. 59-69. 3. Harrison, M. A., The Number of Transitivity Sets of Boolean Functions, The University of Michigan Technical Note 04879-3-T, June 1962. 4. Lorens, C. S., Invertible Boolean Functions, Space-General Corporation Research Memorandum No. 21, January 1962. 5. Slepian, D., "On the number of symmetry types of Boolean functions of n variables, Canadian Journal of Mathematics, Vol. 5 (1953), pp. 185-193. 7

UNIVERSITY OF MICHIGAN 3 9015 03026 9735111111111 3 9015 03026 9735