%I M0819 N0310 N1026 #81 Sep 17 2023 21:36:38
%S 1,2,3,6,22,402,1228158,400507806843728,
%T 527471432057653004017274030725792,
%U 11218076601767519586965281984173341005925142853855481024470471657123840
%N a(-1)=1 by convention; for n >= 0, a(n) = number of irreducible Boolean functions of n variables.
%C Number of NP-equivalence classes of switching functions of n or fewer variables.
%C Number of inequivalent binary nonlinear codes of length n (and all sizes).
%C 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
%C Functions' truth tables are colorings of the vertices of n-dimensional hypercubes, where each axis is an input. Actions of reduction (by exchanging pairs of inputs and mapping NOT to them) correspond with invariance under the hypercube's symmetry group, so it is column k=2 of A361870. - _Nathan L. Skirrow_, Jun 24 2023
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 112.
%D M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 149.
%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 11.
%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).
%D I. Tomescu, Introducere in Combinatorica. Editura Tehnica, Bucharest, 1972, p. 129.
%H Marcus Ritt, <a href="/A000616/b000616.txt">Table of n, a(n) for n = -1..10</a>
%H 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 Steven R. Finch, <a href="https://doi.org/10.1017/9781316997741">Mathematical Constants II</a>, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
%H R. K. Guy, <a href="/A003320/a003320.pdf">Letter to N. J. A. Sloane, Mar 1974</a>.
%H M. A. Harrison, <a href="https://www.jstor.org/stable/2946322">The number of transitivity sets of Boolean functions</a>, J. Soc. Indust. Appl. Math., 11 (1963), 806-828.
%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 J. Sklansky, <a href="https://doi.org/10.1109/PGEC.1963.263627">General synthesis of tributary switching networks</a>, IEEE Trans. Elect. Computers, 12 (1963), 464-469.
%H I. Toda, <a href="https://doi.org/10.1109/TEC.1962.5219361">On the number of types of self-dual logical functions</a>, IEEE Trans. Electron. Comput., 11 (1962), 282-284.
%H I. Toda, <a href="/A001531/a001531.pdf">On the number of types of self-dual logical functions</a>. [Annotated scanned copy]
%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F Harrison gives a simple formula in terms of the cycle index of the appropriate group.
%F a(n) ~ 2^(2^n)/(n!*2^n), and converges from above. (See A361870 for proof.) - _Nathan L. Skirrow_, Jun 24 2023
%Y Row sums of A039754, column k=2 of A361870.
%Y Compare A003180 for equivalence under permutation of inputs without NOTs, A000231 for NOTs without permutation, A000618 for the number of NP-equivalence classes for exactly n variables.
%Y Cf. A102449, A109460, A109462.
%K nonn,easy,nice
%O -1,2
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_
%E Entry revised by _N. J. A. Sloane_, Aug 07 2006
%E Terms a(9) and a(10) (given in b-file) from _Marcus Ritt_, Aug 13 2013