A378302 Number of nondegenerate balanced Boolean functions of n variables.

0, 2, 2, 58, 12618, 601016690, 1832624137336299922, 23951146041928082853307218802404658090, 5768658823449206338089748357862286887548602533639737369730665340966207267034

Offset: 0

Author

Aniruddha Biswas, Nov 22 2024

Keywords

• nonn
• easy

Comments

A Boolean function is degenerate on some variable if its output does not depend on the variable, and it is said to be non-degenerate if it is not degenerate on any variable.

Links

• Aniruddha Biswas and Palash Sarkar, Counting unate and balanced monotone Boolean functions, arXiv:2304.14069 [math.CO], 2023.
• Aniruddha Biswas and Palash Sarkar, Counting Unate and Monotone Boolean Functions Under Restrictions of Balancedness and Non-Degeneracy, J. Int. Seq. (2025) Vol. 28, Art. No. 25.3.4. See pp. 4, 6.

Crossrefs

Cf. A037293, A000618.

Programs

Mathematica

a[n_]:=Sum[(-1)^(n-i)*Binomial[n,i]*Binomial[2^i,2^(i-1)],{i,n}]; Array[a,9,0] (* Stefano Spezia, Nov 24 2024 *)

Python

from math import comb
def A378302(n): return sum(-comb(n,i)*comb(1<Chai Wah Wu, Dec 11 2024

Formula

a(n) = Sum_{i=1..n} (-1)^(n-i) * binomial(n,i) * binomial(2^i,2^(i-1)).