Number of boolean functions with equal numbers of $1$'s and $0$'s in the truth table

201 Views Asked by At

I need to find the number of boolean functions of $n$ boolean variables with equal numbers of $1$'s and $0$'s in their truth tables.

The book says the answer is $$\binom{2^n}{2^n-1}$$ but I don't get it.

We have $2^n/2=2^{n-1}$ ones (and the same number of zeroes) in a truth table for a boolean function of $n$ variables. Shouldn't the number of the functions in question be $$\binom{2^n}{2^{n-1}}$$ or am I wrong?

1

There are 1 best solutions below

0
On BEST ANSWER

Just check for $n=2$, where we can verify explicitly that there are six such functions, not four. Your expression is the correct one, and the one in the book is most likely a typo.