Number of 'unique' one bit binary functions with N-bit inputs

Question

Consider the set of binary functions that takes an N-bit input -> 1 bit output. There are 2^(2^N) elements in this set.

Now potentially reduce this set by restricting to only considering functions which have a dependence on every input bit (ie. there is no bit such that inverting the bit on the input never effects the output: there is no bit such that f(x XOR bit)=f(x) for all x).

And finally, also define two functions to be equivalent if they differ only by a permutation of the input bits.

How large is this equivalence class?

I've worked out the first few by hand and found for N=0 there are 2 unique functions, N=1 results in 2 unique functions, N=2 results in 8. Beyond this I made a computer program which found N=3 gives 68, N=4 gives 3904.

I have a feeling that even if one cannot give a simple closed formula, that there is some kind of recursive definition that can give the results. But I'm not sure how to set it up without accidentally double counting.

Answer 1

The symmetric group $S_n$ operates on the set of boolean functions that depend on every input by permuting the inputs. Functions are in the same orbit of this operation exactly when you call them equivalent. The equivalence classes have different sizes, what you really want to know is how many of them there are. Generally, the number of orbits of a group operation can be calculated using Burnside's Lemma. To use it in our case, you need to know the number of "non-degenerate" boolean functions that do not change under a particular operation. Unfortunately, finding these numbers also seems quite difficult, even though it is possible to affirm your result for $n=3$ this way.

However, we have better luck if we interchange the two steps you do in the definition of what you want to count. Let's first count the number of equivalence classes of boolean functions of $n$ input bits without assuming all are needed. Using the same idea as above, I was able to write a GAP function that does some group computations and get enough values to find this numbers as OEIS-A003180.

They give a formula using only number theory: $$ a_n = \sum_{1s_1+2s_2+\dots=n} \frac{\operatorname{fixA}[ s_1, s_2, \dots]}{1^{s_1}s_1!\,2^{s_2}s_2!\cdots} $$ (the sum is over all partitions of $n$, corresponding to looking at conjugacy classes of the symmetric group) where $$\operatorname{fixA}[s_1, s_2, \dots] = 2^{\sum_{i\ge1} \sum_{d\mid i} \mu(i/d) 2^{\sum_{j\ge1} \gcd(j, d)s_j}/i}. $$ (Yes, there is a sum in a supersuperscript! Zoom in, you will eventually be able to read it. You may also look at the ASCII version at OEIS.) Here $\mu$ is the Möbius function. For $j$, we only need the $k$ for which $s_k$ is nonzero, and for $i$ we only need the divisors of the lcm of these $k$.

Here is GAP code for that function $a$:

tp := p -> List([1..p[1]], i -> Number(p, x -> x=i)); # transform partition
fixA := s -> 2^Sum(DivisorsInt(Lcm(Filtered([1..Length(s)], n -> s[n]<>0))),
                   i -> Sum(DivisorsInt(i),
                            d -> MoebiusMu(i/d)*2^Sum([1..Length(s)],
                                                      j -> Gcd(j,d)*s[j]))/i);
a := n -> Sum(List(Partitions(n), tp),
              s -> fixA(s)/Product([1..Length(s)], k -> k^s[k]*Factorial(s[k])));

Now for the number $b_n$ of equivalence classes of functions that don't ignore any input, observe that each class of functions of $n$ inputs that ignore at least one input corresponds to exactly one equivalence class of functions of $n-1$ inputs, so we have simply $$ b_n=a_n-a_{n-1} \quad\text{for $n\ge1$}. $$

I have extended the entry for OEIS-A003181 as a result of answering this question.