

A102449


Number of canalizing Boolean functions with n input variables.


3




OFFSET

0,1


COMMENTS

A canalizing function is one in which at least one of the input variables is able to determine the value of the output of the function regardless of the other variables. For example, f(x1,x2,x3) = x1 + x2*x3, where + is disjunction and * is conjunction, is a canalizing function, since setting x1 = 1 guarantees that the function is 1 regardless of the value of x2 or x3. On the other hand, the function f(x1, x2) = x1 + x2, where + is addition modulo 2, is not a canalizing function, since the values of both variables always need to be known in order to determine the function output.


REFERENCES

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.


LINKS



FORMULA

a(n) = 2((1)^n  n) + Sum_{k=1..n} (1)^(k+1)*binomial(n, k)*2^(k+1)*2^(2^(nk)).


CROSSREFS



KEYWORD

nonn


AUTHOR

Ilya Shmulevich (is(AT)ieee.org), Feb 23 2005


STATUS

approved



