|
%I M1287 N0494 #44 Aug 17 2023 01:54:36
%S 1,2,4,14,222,616126,200253952527184,
%T 263735716028826576482466871188128,
%U 5609038300883759793482640992086670939164957990135057216103303119630336
%N Number of NPN-equivalence classes of Boolean functions of n or fewer variables.
%C Number of Boolean functions distinct under complementation/permutation.
%D M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 153.
%D D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
%D S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 16.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H M. A. Harrison, <a href="http://dx.doi.org/10.1109/PGEC.1963.263656">The number of equivalence classes of Boolean functions under groups containing negation</a>, IEEE Trans. Electron. Comput. 12 (1963), 559-561.
%H M. A. Harrison, <a href="/A000370/a000370.pdf">The number of equivalence classes of Boolean functions under groups containing negation</a>, IEEE Trans. Electron. Comput. 12 (1963), 559-561. [Annotated scanned copy]
%H M. A. Harrison, <a href="https://doi.org/10.1145/321312.321325">On asymptotic estimates in switching and automata theory</a>, J. ACM, v. 13, no. 1, Jan. 1966, pp. 151-157.
%H S. Muroga, <a href="/A000371/a000371.pdf">Threshold Logic and Its Applications</a>, Wiley, NY, 1971 [Annotated scans of a few pages]
%H S. Muroga, T. Tsuboi and C. R. Baugh, <a href="/A002077/a002077.pdf">Enumeration of threshold functions of eight variables</a>, IEEE Trans. Computers, 19 (1970), 818-825. [Annotated scanned copy]
%H Juling Zhang, Guowu Yang, William N. N. Hung, Tian Liu, Xiaoyu Song, Marek A. Perkowski, <a href="https://doi.org/10.1007/s00224-018-9903-0">A Group Algebraic Approach to NPN Classification of Boolean Functions</a>, Theory of Computing Systems (2018), 1-20.
%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F a(n) is asymptotic to 2^{2^n} / ( n! * 2^{n+1} ) as n -> oo. This follows from a theorem of Michael Harrison. See Theorem 3 in Harrison (JACM, 1966). - Eric Bach, Aug 07 2017
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_, Feb 23 2000
|
