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

2, 4, 12, 80, 3984, 37333248, 25626412338274304, 67516342973185974328175690087661568, 2871827610052485009904013737758920847669809829897636746529411152822140928

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

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.

Also number of nonisomorphic sets of subsets of an n-set.

Also the number of unlabeled hypergraphs on n nodes [Qian]. - N. J. A. Sloane, May 12 2014

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

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

Examples

			From _Gus Wiseman_, Aug 05 2019: (Start)
Non-isomorphic representatives of the a(0) = 2 through a(2) = 12 sets of subsets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{1,2}}
                  {{},{1}}
                  {{1},{2}}
                  {{},{1,2}}
                  {{2},{1,2}}
                  {{},{1},{2}}
                  {{},{2},{1,2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}
(End)
		

References

• M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 147.
• 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 5.
• 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).

Links

• Vladeta Jovovic, Table of n, a(n) for n = 0..11
• Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
• Toru Ishihara, Enumeration of hypergraphs, European Journal of Combinatorics, Volume 22, Issue 4, May 2001.
• S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971. [Annotated scans of a few pages]
• Jianguo Qian, Enumeration of unlabeled uniform hypergraphs, Discrete Math. 326 (2014), 66--74. MR3188989. See Table 1, p. 71. - _N. J. A. Sloane_, May 12 2014
• Marko Riedel, Cycle indices for the enumeration of non-isomorphic hypergraphs, Mathematics Stack Exchange, 2018.
• Marko Riedel, 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.
• Index entries for sequences related to Boolean functions

Crossrefs

Twice A000612. Cf. A001146. Row sums of A052265.

Cf. A003181, A055621.

Programs

Maple

with(numtheory):with(combinat):
for n from 1 to 10 do
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:
  for i from 1 to nops(q) do a(q[i][1]):=q[i][2]: od:
  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:
  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:
  s:=s+2^(ss/ord)/c:
od:
printf(`%d `,n):
printf("%d ",s):
od: # Vladeta Jovovic, Sep 19 2006

Mathematica

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]}];
a /@ Range[0, 11] (* Jean-François Alcover, Feb 19 2020, after Alois P. Heinz in A000612 *)
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]}];
a[0] = 2;
a[n_] := Sum[fix[s]/Product[j^s[j] s[j]!, {j, Keys[s]}], {s, Counts /@ IntegerPartitions[n]}];
Table[a[n], {n, 0, 8}]
(* Andrey Zabolotskiy, Mar 24 2020, after Christian G. Bower's formula; requires Mathematica 10+ *)

Formula

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.

a(n) = 2 * A000612(n).

Extensions

More terms from Vladeta Jovovic, Sep 19 2006

Edited with formula by Christian G. Bower, Jan 08 2004