This site is supported by donations to The OEIS Foundation.



Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000616 a(-1)=1 by convention; for n >= 0, a(n) = number of irreducible Boolean functions of n variables.
(Formerly M0819 N0310 N1026)
1, 2, 3, 6, 22, 402, 1228158, 400507806843728, 527471432057653004017274030725792, 11218076601767519586965281984173341005925142853855481024470471657123840 (list; graph; refs; listen; history; text; internal format)



Number of NP-equivalence classes of switching functions of n or fewer variables.

Number of inequivalent binary nonlinear codes of length n (and all sizes).

a(n+1) = number of NPN-equivalence classes of canalizing functions (see A102449) with n variables. NPN-equivalence allows complementing the function value as well as the individual variables. E.g., the 6 inequivalent canalizing functions when n=3 are 0, x, x AND y, x AND y AND z, x AND (y OR z), x AND (y XOR z). - Don Knuth, Aug 24 2005, Aug 06 2006


F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 112.

M. A. Harrison, The number of transitivity sets of Boolean functions, J. Soc. Indust. Appl. Math., 11 (1963), 806-828.

M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 149.

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 11.

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).

I. Tomescu, Introducere in Combinatorica. Editura Tehnica, Bucharest, 1972, p. 129.


Marcus Ritt, Table of n, a(n) for n = -1..10

B. Elspas, Self-complementary symmetry types of Boolean functions,  IEEE Transactions on Electronic Computers 2, no. EC-9 (1960): 264-266. [Annotated scanned copy]

Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.

R. K. Guy, Letter to N. J. A. Sloane, Mar 1974

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]

J. Sklansky, General synthesis of tributary switching networks, IEEE Trans. Elect. Computers, 12 (1963), 464-469.

I. Toda, On the number of types of self-dual logical functions, IEEE Trans. Electron. Comput., 11 (1962), 282-284.

I. Toda, On the number of types of self-dual logical functions (annotated scanned copy)

Index entries for sequences related to Boolean functions


Harrison gives a simple formula in terms of the cycle index of the appropriate group.


Row sums of A039754.

Cf. A102449, A109460, A109462.

Sequence in context: A173249 A303584 A261014 * A233217 A261963 A183179

Adjacent sequences:  A000613 A000614 A000615 * A000617 A000618 A000619




N. J. A. Sloane


More terms from Vladeta Jovovic

Entry revised by N. J. A. Sloane, Aug 07 2006

Terms a(9) and a(10) (given in b-file) from Marcus Ritt, Aug 13 2013



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 12 09:36 EST 2019. Contains 329953 sequences. (Running on oeis4.)