A037267 Number of Boolean functions on n inputs with representing polynomial of max degree n.

1, 2, 10, 186, 52666, 3693886906, 16614119932766961082, 316331220879010380597239019655387659706, 110023430413866989085481236650825620965529772963665402006849147440648610889146

Offset

0,2

Comments

For n >= 1, a(n) is the number of n-variable non-balanced Boolean functions. A Boolean function is non-balanced if it takes the values 0 and 1 not an equal number of times. - Thomas Scheuerle, Apr 17 2026

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 p. 2.

Index entries for sequences related to Boolean functions

Formula

a(n) = A001146(n) - A037293(n).

From Thomas Scheuerle, Apr 17 2026: (Start)

a(n) = A045621(2^n).

a(n) = 2^(2^n) - binomial(2^n, 2^(n-1)), for n > 0. (End)

Prog

(PARI) a(n) = 2^(2^n) - (2^n)!/(2^(n-1))!^2 \\ Thomas Scheuerle, Apr 17 2026

Crossrefs

Cf. A001146, A037293, A045621.

Sequence in context: A319607 A057119 A226563 * A177399 A194971 A155200

Adjacent sequences: A037264 A037265 A037266 * A037268 A037269 A037270

Keyword

nonn,easy

Author

John Tromp

Extensions

a(7)-a(8) from Thomas Scheuerle, Apr 17 2026

Status

approved