A000370 Number of NPN-equivalence classes of Boolean functions of n or fewer variables.

1, 2, 4, 14, 222, 616126, 200253952527184, 263735716028826576482466871188128, 5609038300883759793482640992086670939164957990135057216103303119630336

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

Number of Boolean functions distinct under complementation/permutation.

References

• M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 153.
• M. A. Harrison, The Number of Transitivity Sets of Boolean Functions. Journal of the Society for Industrial and Applied Mathematics, Vol. 11, No. 3 (Sep., 1963), pp. 806-828
• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
• S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 16.
• 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

• Matthew House, Table of n, a(n) for n = 0..11
• M. A. Harrison, The number of equivalence classes of Boolean functions under groups containing negation, IEEE Trans. Electron. Comput. 12 (1963), 559-561.
• M. A. Harrison, The number of equivalence classes of Boolean functions under groups containing negation, IEEE Trans. Electron. Comput. 12 (1963), 559-561. [Annotated scanned copy]
• M. A. Harrison, On asymptotic estimates in switching and automata theory, J. ACM, v. 13, no. 1, Jan. 1966, pp. 151-157.
• S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971 [Annotated scans of a few pages]
• S. Muroga, T. Tsuboi and C. R. Baugh, Enumeration of threshold functions of eight variables, IEEE Trans. Computers, 19 (1970), 818-825. [Annotated scanned copy]
• Juling Zhang, Guowu Yang, William N. N. Hung, Tian Liu, Xiaoyu Song, Marek A. Perkowski, A Group Algebraic Approach to NPN Classification of Boolean Functions, Theory of Computing Systems (2018), 1-20.
• Index entries for sequences related to Boolean functions

Programs

Python

def partition_lin(n, d, depth=0):
  if d == depth:
    if n==0: yield ()
  else: yield from (item + (i,) for i in range(n+1) for item in partition_lin(n-i*(depth+1), d, depth=depth+1))
def get_num_equiv_bool_func(n, sc=False):
  import math, operator, functools
  from sympy import mobius
  def e(k): return sum((1<Gregory Morse, Dec 23 2024

Formula

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

a(n) = (A000610(n)+A000616(n)) / 2. - Gregory Morse, Dec 23 2024

Extensions

More terms from Vladeta Jovovic, Feb 23 2000