A000721 Number of NP-equivalence classes of balanced Boolean functions of n variables.

1, 2, 6, 74, 169112, 39785643746726, 37126652766640082937217814348006, 558874591495497577231218517843968898077072559983411918227348931497772

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

These are distinct groups of Boolean functions of n variables that output an equal number of 0s and 1s across all possible inputs (balanced), and cannot be transformed into each other by negating or permuting inputs. - Aniruddha Biswas, Nov 12 2024

Examples

			For n = 2 the a(2) = 2. Solutions are f(x,y)=x and f(x,y)=x⊕y; are two 2-variable NP-inequivalent balanced Boolean functions. - _Aniruddha Biswas_, Nov 12 2024
		

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Herman Jamke, Table of n, a(n) for n = 1..10
• B. Elspas, Self-complementary symmetry types of Boolean functions, IEEE Trans. Electron. Computers, 9 (1960), 264-266.
• B. Elspas, Self-complementary symmetry types of Boolean functions, IEEE Transactions on Electronic Computers 2, no. EC-9 (1960): 264-266. [Annotated scanned copy]
• E. M. Palmer and R. W. Robinson, Enumeration of self-dual configurations, Pacific J. Math., 110 (1984), 203-221. [From Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 21 2010]
• D. Zeilberger, First 7 terms of the sequence of weight-enumerators enumerating equivalence classes of Boolean functions under permutation of variable and negation . [From Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 21 2010]
• D. Zeilberger, First 7 terms of the sequence of weight-enumerators enumerating equivalence classes of Boolean functions under permutation of variable and negation [Local copy]
• Index entries for sequences related to Boolean functions

Crossrefs

Cf. A037293, A000370.

Formula

a(n) is asymptotic to binomial(2^n, 2^(n-1)) / ( n! * 2^n ) as n -> oo. - Aniruddha Biswas, Dec 16 2024

Extensions

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 21 2010, Sep 05 2010