A397075 Number of NPN-equivalence classes of Boolean functions of n variables whose degree is equal to n.

1, 2, 8, 164, 529523

Offset

1,2

Comments

The degree deg(f) of a Boolean function f is the degree of its unique multilinear polynomial representation over the reals. (This is the real degree, which in general exceeds the GF(2)/ANF degree; for example, the parity of n variables has real degree n but ANF degree 1, so the two notions give different sequences, and this entry uses the real degree.) We count the NPN-equivalence classes (functions up to negation of input variables, permutation of input variables, and negation of the output) of n-variable Boolean functions of full degree, deg(f) = n.

a(5) = 529523 was obtained from a complete census of all 616126 NPN classes of Boolean functions on at most 5 variables.

Links

Table of n, a(n) for n=1..5.

Crossrefs

Cf. A000370 (number of NPN-equivalence classes of Boolean functions of n or fewer variables), A397074 (sensitivity), A397076 (deterministic decision-tree complexity).

Sequence in context: A012540 A346164 A175538 * A009606 A009682 A076548

Adjacent sequences: A397072 A397073 A397074 * A397076 A397077 A397078

Keyword

nonn,hard,more,new

Author

Alex Towell, Jun 15 2026

Status

approved