cp's OEIS Frontend

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

%I A000721 M1721 N0683 #62 Dec 16 2024 14:35:16
%S A000721 1,2,6,74,169112,39785643746726,37126652766640082937217814348006,
%T A000721 558874591495497577231218517843968898077072559983411918227348931497772
%N A000721 Number of NP-equivalence classes of balanced Boolean functions of n variables.
%C A000721 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
%D A000721 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000721 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000721 Herman Jamke, <a href="/A000721/b000721.txt">Table of n, a(n) for n = 1..10</a>
%H A000721 B. Elspas, <a href="https://doi.org/10.1109/TEC.1960.5219832">Self-complementary symmetry types of Boolean functions</a>, IEEE Trans. Electron. Computers, 9 (1960), 264-266.
%H A000721 B. Elspas, <a href="/A000610/a000610.pdf">Self-complementary symmetry types of Boolean functions</a>,  IEEE Transactions on Electronic Computers 2, no. EC-9 (1960): 264-266. [Annotated scanned copy]
%H A000721 E. M. Palmer and R. W. Robinson, <a href="http://projecteuclid.org/euclid.pjm/1102711113">Enumeration of self-dual configurations</a>, Pacific J. Math., 110 (1984), 203-221. [From Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 21 2010]
%H A000721 D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/tokhniot/oGraphEnumeration2">First 7 terms of the sequence of weight-enumerators enumerating equivalence classes of Boolean functions under permutation of variable and negation </a>. [From Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 21 2010]
%H A000721 D. Zeilberger, <a href="/A000721/a000721.txt">First 7 terms of the sequence of weight-enumerators enumerating equivalence classes of Boolean functions under permutation of variable and negation</a> [Local copy]
%H A000721 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F A000721 a(n) is asymptotic to binomial(2^n, 2^(n-1)) / ( n! * 2^n ) as n -> oo. - _Aniruddha Biswas_, Dec 16 2024
%e A000721 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
%Y A000721 Cf. A037293, A000370.
%K A000721 nonn,nice,easy
%O A000721 1,2
%A A000721 _N. J. A. Sloane_
%E A000721 More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 21 2010, Sep 05 2010