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

2.1k Views Asked by At

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.