cp's OEIS Frontend

A003181 Number of P-equivalence classes of nondegenerate Boolean functions of n variables.

%I A003181 M0378 #41 Oct 21 2023 01:08:35
%S A003181 2,2,8,68,3904,37329264,25626412300941056,
%T A003181 67516342973185974302549277749387264,
%U A003181 2871827610052485009904013737758920847602293486924450772201235462734479360
%N A003181 Number of P-equivalence classes of nondegenerate Boolean functions of n variables.
%C A003181 Also the number of non-isomorphic sets of subsets of {1..n} with union {1..n}. - _Gus Wiseman_, Aug 05 2019
%D A003181 S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.
%D A003181 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003181 Alois P. Heinz, <a href="/A003181/b003181.txt">Table of n, a(n) for n = 0..12</a>
%H A003181 S. Muroga, <a href="/A000371/a000371.pdf">Threshold Logic and Its Applications</a>, Wiley, NY, 1971. [Annotated scans of a few pages]
%H A003181 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F A003181 a(n) = A003180(n) - A003180(n-1), for n >= 1. - _Christian Sievers_, Jul 22 2016
%F A003181 a(n) = 2 * A055621(n). - _Gus Wiseman_, Aug 05 2019
%e A003181 From _Gus Wiseman_, Aug 05 2019: (Start)
%e A003181 Non-isomorphic representatives of the a(0) = 2 through a(2) = 8 sets of subsets:
%e A003181   {}    {{1}}     {{1,2}}
%e A003181   {{}}  {{},{1}}  {{1},{2}}
%e A003181                   {{},{1,2}}
%e A003181                   {{2},{1,2}}
%e A003181                   {{},{1},{2}}
%e A003181                   {{},{2},{1,2}}
%e A003181                   {{1},{2},{1,2}}
%e A003181                   {{},{1},{2},{1,2}}
%e A003181 (End)
%p A003181 b:= proc(n, i, l) `if`(n=0, 2^(w-> add(mul(2^igcd(t, l[h]),
%p A003181       h=1..nops(l)), t=1..w)/w)(ilcm(l[])), `if`(i<1, 0,
%p A003181       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i)))
%p A003181     end:
%p A003181 a:= n-> `if`(n=0, 2, b(n$2, [])-b(n-1$2, [])):
%p A003181 seq(a(n), n=0..8);  # _Alois P. Heinz_, Aug 14 2019
%t A003181 b[n_, i_, l_] := If[n == 0, 2^Function[w, Sum[Product[2^GCD[t, l[[h]]], {h, 1, Length[l]}], {t, 1, w}]/w][If[l == {}, 1, LCM @@ l]], If[i < 1, 0, Sum[b[n - i*j, i - 1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]]];
%t A003181 a[n_] := If[n == 0, 2, b[n, n, {}] - b[n - 1, n - 1, {}]];
%t A003181 a /@ Range[0, 8] (* _Jean-François Alcover_, Apr 11 2020, after _Alois P. Heinz_ *)
%Y A003181 Cf. A000371, A001146, A003180, A003465, A055621, A007537, A326881.
%K A003181 nonn
%O A003181 0,1
%A A003181 _N. J. A. Sloane_
%E A003181 More terms from _Christian Sievers_, Jul 22 2016
%E A003181 Definition clarified by _Ivo Timoteo_, Mar 14 2017