OFFSET
1,1
COMMENTS
Conditionally dominated Boolean functions arise in the setting of non-cooperatively computable Boolean functions f: {0,1}^n -> {0,1}; x=(x1,x2,...,xn)-> f(x). Let x' denote x omitting xi and (x',xi) the string that results from inserting xi in x' at the i-th position. A Boolean function f is conditionally dominated if the following two conditions hold:
1. f(x',0) != f(x',1) for some x', that is, the i-th input is relevant.
2. There are binary values xi and y such that f(x',xi)=y for all x'.
LINKS
Yona Raekow, Table of n, a(n) for n = 1..12
Y. Raekow and K. Ziegler, A taxonomy of non-cooperatively computable functions, WEWoRC 2011 (conference record)
FORMULA
a(n) = Sum((-2)^(j+1)*C(n, j)*(2^(2^(n-j))-1), j=1..n)-2*n.
a(n) ~ n*2^(2^(n-1)). - Charles R Greathouse IV, May 15 2012
PROG
(Sage)
def A212414(n):
result = 0
for i in range(1, n+1):
result += binomial(n, i)*(-1)^(i+1)*2^(i+2^(n-i))
result += (-1)^n-n-1
result *= 2
return result
(PARI) a(n)=sum(j=1, n, (-2)^(j+1)*binomial(n, j)*(1<<2^(n-j)-1))-2*n \\ Charles R Greathouse IV, May 15 2012
CROSSREFS
KEYWORD
nonn
AUTHOR
Yona Raekow, May 15 2012
STATUS
approved