cp's OEIS Frontend

A003180 Number of equivalence classes of Boolean functions of n variables under action of symmetric group.

%I A003180 M1265 N1405 #90 Aug 22 2022 04:01:30
%S A003180 2,4,12,80,3984,37333248,25626412338274304,
%T A003180 67516342973185974328175690087661568,
%U A003180 2871827610052485009904013737758920847669809829897636746529411152822140928
%N A003180 Number of equivalence classes of Boolean functions of n variables under action of symmetric group.
%C A003180 A003180(n-1) is the number of equivalence classes of Boolean functions of n variables from Post class F(8,inf) under action of symmetric group.
%C A003180 Also number of nonisomorphic sets of subsets of an n-set.
%C A003180 Also the number of unlabeled hypergraphs on n nodes [Qian]. - _N. J. A. Sloane_, May 12 2014
%C A003180 The number of unlabeled hypergraphs with empty hyperedges allowed on n nodes. Compare with A000612 where empty hyperedges are not allowed. - _Michael Somos_, Feb 15 2019
%C A003180 In the 1995 Encyclopedia of Integer Sequences this sequence appears twice, as both M1265 and M3458 (one entry began at n=0, the other at n=1).
%D A003180 M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 147.
%D A003180 D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
%D A003180 S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 5.
%D A003180 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A003180 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003180 Vladeta Jovovic, <a href="/A003180/b003180.txt">Table of n, a(n) for n = 0..11</a>
%H A003180 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 A003180 Toru Ishihara, <a href="https://doi.org/10.1006/eujc.2001.0498">Enumeration of hypergraphs</a>, European Journal of Combinatorics, Volume 22, Issue 4, May 2001.
%H A003180 S. Muroga, <a href="/A000371/a000371.pdf">Threshold Logic and Its Applications</a>, Wiley, NY, 1971. [Annotated scans of a few pages]
%H A003180 Jianguo Qian, <a href="https://doi.org/10.1016/j.disc.2014.03.005">Enumeration of unlabeled uniform hypergraphs</a>, Discrete Math. 326 (2014), 66--74. MR3188989. See Table 1, p. 71. - _N. J. A. Sloane_, May 12 2014
%H A003180 Marko Riedel, <a href="https://math.stackexchange.com/questions/2732440/">Cycle indices for the enumeration of non-isomorphic hypergraphs</a>, Mathematics Stack Exchange, 2018.
%H A003180 Marko Riedel, <a href="/A003180/a003180_4.maple.txt">Implementation of the Ishihara algorithm for cycle indices of the action of the symmetric group S_n on sets of subsets of an n-set.</a>
%H A003180 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F A003180 a(n) = Sum_{1*s_1+2*s_2+...=n} (fixA[s_1, s_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...)) where fixA[s_1, s_2, ...] = 2^Sum_{i>=1} ( Sum_{d|i} ( mu(i/d)*( 2^Sum_{j>=1} ( gcd(j, d)*s_j))))/i.
%F A003180 a(n) = 2 * A000612(n).
%e A003180 From _Gus Wiseman_, Aug 05 2019: (Start)
%e A003180 Non-isomorphic representatives of the a(0) = 2 through a(2) = 12 sets of subsets:
%e A003180   {}    {}        {}
%e A003180   {{}}  {{}}      {{}}
%e A003180         {{1}}     {{1}}
%e A003180         {{},{1}}  {{1,2}}
%e A003180                   {{},{1}}
%e A003180                   {{1},{2}}
%e A003180                   {{},{1,2}}
%e A003180                   {{2},{1,2}}
%e A003180                   {{},{1},{2}}
%e A003180                   {{},{2},{1,2}}
%e A003180                   {{1},{2},{1,2}}
%e A003180                   {{},{1},{2},{1,2}}
%e A003180 (End)
%p A003180 with(numtheory):with(combinat):
%p A003180 for n from 1 to 10 do
%p A003180 p:=partition(n): s:=0: for k from 1 to nops(p) do q:=convert(p[k],multiset): for i from 0 to n do a(i):=0: od:
%p A003180   for i from 1 to nops(q) do a(q[i][1]):=q[i][2]: od:
%p A003180   c:=1: ord:=1: for i from 1 to n do c:=c*a(i)!*i^a(i):ord:=lcm(ord,i): od: ss:=0:
%p A003180   for i from 1 to ord do if ord mod i=0 then ss:=ss+phi(ord/i)*2^add(gcd(j,i)*a(j),j=1..n): fi: od:
%p A003180   s:=s+2^(ss/ord)/c:
%p A003180 od:
%p A003180 printf(`%d `,n):
%p A003180 printf("%d ",s):
%p A003180 od: # _Vladeta Jovovic_, Sep 19 2006
%t A003180 a[n_] := Sum[1/Function[p, Product[Function[c, j^c*c!][Coefficient[p, x, j]], {j, 1, Exponent[p, x]}]][Total[x^l]]*2^(Function[w, Sum[Product[ 2^GCD[t, l[[i]]], {i, 1, Length[l]}], {t, 1, w}]/w][If[l == {}, 1, LCM @@ l]]), {l, IntegerPartitions[n]}];
%t A003180 a /@ Range[0, 11] (* _Jean-François Alcover_, Feb 19 2020, after _Alois P. Heinz_ in A000612 *)
%t A003180 fix[s_] := 2^Sum[Sum[MoebiusMu[i/d] 2^Sum[GCD[j, d] s[j], {j, Keys[s]}], {d, Divisors[i]}]/i, {i, LCM @@ Keys[s]}];
%t A003180 a[0] = 2;
%t A003180 a[n_] := Sum[fix[s]/Product[j^s[j] s[j]!, {j, Keys[s]}], {s, Counts /@ IntegerPartitions[n]}];
%t A003180 Table[a[n], {n, 0, 8}]
%t A003180 (* _Andrey Zabolotskiy_, Mar 24 2020, after _Christian G. Bower_'s formula; requires Mathematica 10+ *)
%Y A003180 Twice A000612. Cf. A001146. Row sums of A052265.
%Y A003180 Cf. A003181, A055621.
%K A003180 nonn,nice
%O A003180 0,1
%A A003180 _N. J. A. Sloane_
%E A003180 More terms from _Vladeta Jovovic_, Sep 19 2006
%E A003180 Edited with formula by _Christian G. Bower_, Jan 08 2004