1 2 3 6 47 23 11 Journal of Integer Sequences Vol 28 2025 Article 25 3 4 Counting Unate and Monotone Boolean Functions Under Restrictions of Balancedness and Non Degeneracy Aniruddha Biswas and Palash Sarkar Indian Statistical Institute 203 B T Road Kolkata 700108 India aniruddhabiswas535 gmail com palash isical ac in Abstract We consider the problem of counting the numbers of functions in various sub classes of unate and monotone Boolean functions under the restrictions of balancedness and non degeneracy Further we also consider the problem of counting the numbers of inequivalent and NPN inequivalent functions in these sub classes 1 Introduction For a positive integer n an n variable Boolean function f is a map f 0 1 n 0 1 A Boolean function f is said to be monotone increasing resp decreasing in the i th variable if f x1 xi 1 0 xi 1 xn f x1 xi 1 1 xi 1 xn resp f x1 xi 1 0 xi 1 xn f x1 xi 1 1 xi 1 xn for all possible x1 xi 1 xi 1 xn 0 1 The function f is said to be locally monotone or unate if for each i 1 n it is either monotone increasing or monotone decreasing in the i th variable The function 1 f is said to be monotone increasing or simply monotone if for each i 1 n it is monotone increasing in the i th variable A Boolean function is degenerate on some variable if its output does not depend on the variable and it is said to be non degenerate if it is not degenerate on any of the variables A Boolean function is said to be balanced if it takes the values 0 and 1 equal number of times 2n 1 cid 1 see A037293 The number of n variable balanced Boolean functions is cid 0 2n The number of n variable monotone Boolean functions denoted as D n is said to be the n th Dedekind number after Dedekind 7 who posed the problem of counting the number of n variable monotone Boolean functions in 1897 The value of D n is known for n 9 see 16 7 5 18 4 19 8 11 10 and A000372 Kisielewicz 12 gave a closed form summation formula for D n However Korshunov 13 pointed out that using the formula to compute D n has the same complexity as direct enumeration of all n variable monotone Boolean functions The inverse binomial transform of D n gives the number of n variable non degenerate monotone Boolean functions and hence the latter quantities are also known for n 9 see A006126 Two Boolean functions on the same number of variables are said to be equivalent if one can be obtained from the other by a permutation of variables Two Boolean functions on the same number of variables are said to be NPN equivalent if one can be obtained from the other by a combination of the following operations a permutation of the variables negation of a subset of the variables and negation of the output Both of the above two notions of equivalence partition the set of all n variable Boolean functions into equivalence classes The number of equivalence classes is also said to be the number of inequivalent functions under the appropriate notion of equivalence It is of interest to count the number of inequiv alent Boolean functions satisfying some prescribed properties For example the number of inequivalent n variable monotone Boolean functions is known for n up to 9 see A003182 Stephen and Yusun 17 and Pawelski 14 Another example is the number of n variable NPN inequivalent unate functions see A003183 and Baugh 2 The focus of the present work is on counting unate and monotone Boolean functions under various restrictions For n 5 it is possible to enumerate all n variable Boolean functions Consequently the problem of counting various sub classes of n variable Boolean functions become a reasonably simple problem Non triviality of counting Boolean functions arises for n 6 The problem of counting unate functions reduces to the problem of counting monotone Boolean functions This follows from the work of Baumann and Strass 3 We were unaware of the work of Baumann and Strass when we obtained the relation between the numbers of unate and monotone Boolean functions Since the numbers of n variable monotone Boolean functions are known for n 9 these values provide the numbers of n variable unate functions for n 9 The numbers of n variable unate functions are available from A245079 We updated A245079 by providing the value for n 9 and correcting the values for n 7 and n 8 We show that the problem of counting balanced unate functions reduces to the problem of counting balanced monotone Boolean functions The number of n variable balanced mono 2 tone Boolean functions is known for n 7 see A341633 and Church 6 Consequently we obtain the numbers of n variable balanced unate functions for n 7 We further extend these results to obtain the numbers of non degenerate balanced monotone Boolean functions non degenerate unate functions and non degenerate balanced unate functions Unlike the situation for counting functions the problem of counting the number of in equivalent unate functions does not reduce to the problem of counting the number of inequiv alent monotone Boolean functions So to count the number of inequivalent unate functions we used a method to generate all n variable unate functions and applied a ltering to the obtained set This allowed us to obtain the numbers of inequivalent n variable unate and balanced unate functions for n 6 Moreover we obtain the numbers of inequivalent n variable balanced monotone Boolean functions non degenerate balanced monotone Boolean functions non degenerate unate functions and non degenerate balanced unate functions for n 6 The results that we present for monotone Boolean functions and unate functions are summarized in Table 1 For each entry of the table we provide the corresponding sequence number of the On Line Encyclopedia of Integer Sequences OEIS 16 The word New in the column entitled Comment indicates that the sequence was added to OEIS based on the present paper while the word Updated indicates that the existing entry was updated based on the present paper 1 1 Outline of the paper In Section 2 we describe the preliminaries and prove the mathematical results required to obtain the various counts In Section 3 we address the problem of counting various sub classes of monotone Boolean functions and unate functions and in Section 4 we take up the problem of counting the numbers of inequivalent unate and monotone Boolean functions possessing a combination of several properties Finally Section 5 discusses some possible future research problems 2 Mathematical results We x some terminology and the notation The