A212414 Number of conditionally dominated Boolean functions in n variables.

2, 12, 118, 3512, 1292274, 103071426292, 516508833342349371374, 10889035741470030826695916769153787968496, 4168515212543383035248555460312764682619718126289830027967813561362272277233642

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

Sequence in context: A132692 A009546 A009748 * A305051 A274305 A317013

Adjacent sequences: A212411 A212412 A212413 * A212415 A212416 A212417

Keyword

nonn

Author

Yona Raekow, May 15 2012

Status

approved