login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003181 Number of P-equivalence classes of nondegenerate Boolean functions of n variables.
(Formerly M0378)
12

%I M0378

%S 2,2,8,68,3904,37329264,25626412300941056,

%T 67516342973185974302549277749387264,

%U 2871827610052485009904013737758920847602293486924450772201235462734479360

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

%C Also the number of non-isomorphic sets of subsets of {1..n} with union {1..n}. - _Gus Wiseman_, Aug 05 2019

%D S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A003181/b003181.txt">Table of n, a(n) for n = 0..12</a>

%H S. Muroga, <a href="/A000371/a000371.pdf">Threshold Logic and Its Applications</a>, Wiley, NY, 1971 [Annotated scans of a few pages]

%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>

%F a(n) = A003180(n)-A003180(n-1), for n>=1. - _Christian Sievers_, Jul 22 2016

%F a(n) = 2 * A055621(n). - _Gus Wiseman_, Aug 05 2019

%e From _Gus Wiseman_, Aug 05 2019: (Start)

%e Non-isomorphic representatives of the a(0) = 2 through a(2) = 8 sets of subsets:

%e {} {{1}} {{1,2}}

%e {{}} {{},{1}} {{1},{2}}

%e {{},{1,2}}

%e {{2},{1,2}}

%e {{},{1},{2}}

%e {{},{2},{1,2}}

%e {{1},{2},{1,2}}

%e {{},{1},{2},{1,2}}

%e (End)

%p b:= proc(n, i, l) `if`(n=0, 2^(w-> add(mul(2^igcd(t, l[h]),

%p h=1..nops(l)), t=1..w)/w)(ilcm(l[])), `if`(i<1, 0,

%p add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i)))

%p end:

%p a:= n-> `if`(n=0, 2, b(n$2, [])-b(n-1$2, [])):

%p seq(a(n), n=0..8); # _Alois P. Heinz_, Aug 14 2019

%t 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 a[n_] := If[n == 0, 2, b[n, n, {}] - b[n - 1, n - 1, {}]];

%t a /@ Range[0, 8] (* _Jean-Fran├žois Alcover_, Apr 11 2020, after _Alois P. Heinz_ *)

%Y Cf. A000371, A001146, A003180, A003465, A055621, A007537, A326881.

%K nonn

%O 0,1

%A _N. J. A. Sloane_.

%E More terms from _Christian Sievers_, Jul 22 2016

%E Definition clarified by _Ivo Timoteo_, Mar 14 2017

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 August 1 05:51 EDT 2021. Contains 346384 sequences. (Running on oeis4.)