On the Number of Equivalence Classes of Boolean and Invertible Boolean Functions
Miodrag Živković, Marko Carić · IEEE Transactions on Information Theory · 2020
The number Unof equivalence classes of Boolean functions of n variables and the number Vnof equivalence classes of vectorial Boolean functions of n variables under the action of four groups of transformations are considered. The four groups are the group Sn' of permutations of variables, the group Gnof permutations and complementations, the linear group GL(n, 2) and the affine group AGL(n, 2). Harrison obtained cycle indexes for these groups and the expressions for Unand Vnin terms of the corresponding cycle index. He also tabulated the numbers Un, Vnand the cycle indexes for n≤6 for Sn' and Gn, and for n≤5 for GL(n, 2) and AGL(n, 2). This bound was only recently slightly exceeded. Fripertinger implemented computation of cycle indexes for GL(n, q) and AGL(n, q); if q = 2 this implementation works for about n 5≤21. By introducing appropriate precomputed tables, we reduced the cycle index computation to evaluation of a sum over partitions of n for all the four groups. Using this more efficient procedure, we obtained values of Un, Vnand the explicit cycle index expressions for larger values of n.