# Number of non degenerate boolean functions

I got in my lecture the formula that describe the number of nondegenerate Boolean functions of $n$ variables (or how many boolean functions have no fictitious variables), but we don't have proof for it and I don't understand where did it get from.

Here is it $$\sum_{0\le k\le n} (-1)^k \binom{n}{k} 2^{2^{n-k}}.\qquad$$

I would be greatly appreciated if someone explained it. Thanks.

-
can you define what is a non-degenerate boolean funtion? –  Mohan Jan 19 '13 at 7:59
Boolean function that have no fictitious(dummy) variables - for example if we have f=(0011) and we have 2 variables X and Y, the second variable is dummy because it values, doesn't change the function....sorry for my English –  Nicole Grefder Jan 19 '13 at 8:04
Have someone any ideas? –  Nicole Grefder Jan 19 '13 at 8:26
Same question as this one –  David Moews Jan 19 '13 at 8:38
ops...I didn't see it...Thanks –  Nicole Grefder Jan 19 '13 at 8:42

First, count all possible boolean functions. You need to assign values for $2^n$ possibilities and each value can be $0$ or $1$. So there are a total of $2^{2^n}$ boolean functions.
Now let us try to subtract number of functions with a degenerate variable. The degenerate variable can be picked in $\binom{n}{1}$ ways and the we now need to assign values for $2^{n-1}$ variable combinations. So this gives $\binom{n}{1}2^{2^{n-1}}$ ways.
But consider the cases where there are two degenerate variables. They are being counted twice in the above list. So we add the corresponding number to compensate for that. But there is multiple counting of functions with $3$ degenerate variables and we should subtract that and so on.
Repeating this process, and noting that for $k$ degenerate variables, the corresponding count is $\binom{n}{k} 2^{2^{n-k}}$, you get the required result.