A378302 Number of nondegenerate balanced Boolean functions of n variables.

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

Offset

0,2

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

Table of n, a(n) for n=0..8.

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.

Formula

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

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 *)

Prog

(Python)
from math import comb
def A378302(n): return sum(-comb(n, i)*comb(1<<n-i, 1<<n-i-1) if i&1 else comb(n, i)*comb(1<<n-i, 1<<n-i-1) for i in range(n)) # Chai Wah Wu, Dec 11 2024

Crossrefs

Cf. A037293, A000618.

Sequence in context: A239151 A379866 A368867 * A286377 A187024 A274477

Adjacent sequences: A378299 A378300 A378301 * A378303 A378304 A378305

Keyword

nonn,easy

Author

Aniruddha Biswas, Nov 22 2024

Status

approved