A212414 - OEIS

%I #26 Mar 14 2020 15:29:39

%S 2,12,118,3512,1292274,103071426292,516508833342349371374,

%T 10889035741470030826695916769153787968496,

%U 4168515212543383035248555460312764682619718126289830027967813561362272277233642

%N Number of conditionally dominated Boolean functions in n variables.

%C 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:

%C 1. f(x',0) != f(x',1) for some x', that is, the i-th input is relevant.

%C 2. There are binary values xi and y such that f(x',xi)=y for all x'.

%H Yona Raekow, <a href="/A212414/b212414.txt">Table of n, a(n) for n = 1..12</a>

%H Y. Raekow and K. Ziegler, A taxonomy of non-cooperatively computable functions, WEWoRC 2011 (<a href="http://www.uni-weimar.de/cms/fileadmin/medien/medsicherheit/WEWoRC2011/files/conference_record3.pdf">conference record</a>)

%F a(n) = Sum((-2)^(j+1)*C(n, j)*(2^(2^(n-j))-1), j=1..n)-2*n.

%F a(n) ~ n*2^(2^(n-1)). - _Charles R Greathouse IV_, May 15 2012

%o (Sage)

%o def A212414(n):

%o     result  = 0

%o     for i in range(1,n+1):

%o         result += binomial(n,i)*(-1)^(i+1)*2^(i+2^(n-i))

%o     result += (-1)^n-n-1

%o     result *= 2

%o     return result

%o (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

%K nonn

%O 1,1

%A _Yona Raekow_, May 15 2012