login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003180 Number of equivalence classes of Boolean functions of n variables under action of symmetric group.
(Formerly M1265 N1405)
30

%I M1265 N1405 #90 Aug 22 2022 04:01:30

%S 2,4,12,80,3984,37333248,25626412338274304,

%T 67516342973185974328175690087661568,

%U 2871827610052485009904013737758920847669809829897636746529411152822140928

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

%C 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 Also number of nonisomorphic sets of subsets of an n-set.

%C Also the number of unlabeled hypergraphs on n nodes [Qian]. - _N. J. A. Sloane_, May 12 2014

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

%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 5.

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

%H Vladeta Jovovic, <a href="/A003180/b003180.txt">Table of n, a(n) for n = 0..11</a>

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

%H 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 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 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 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>

%F 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 a(n) = 2 * A000612(n).

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

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

%e {} {} {}

%e {{}} {{}} {{}}

%e {{1}} {{1}}

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

%e {{},{1}}

%e {{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 with(numtheory):with(combinat):

%p for n from 1 to 10 do

%p 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 for i from 1 to nops(q) do a(q[i][1]):=q[i][2]: od:

%p 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 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 s:=s+2^(ss/ord)/c:

%p od:

%p printf(`%d `,n):

%p printf("%d ",s):

%p od: # _Vladeta Jovovic_, Sep 19 2006

%t 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 a /@ Range[0, 11] (* _Jean-François Alcover_, Feb 19 2020, after _Alois P. Heinz_ in A000612 *)

%t 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 a[0] = 2;

%t a[n_] := Sum[fix[s]/Product[j^s[j] s[j]!, {j, Keys[s]}], {s, Counts /@ IntegerPartitions[n]}];

%t Table[a[n], {n, 0, 8}]

%t (* _Andrey Zabolotskiy_, Mar 24 2020, after _Christian G. Bower_'s formula; requires Mathematica 10+ *)

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

%Y Cf. A003181, A055621.

%K nonn,nice

%O 0,1

%A _N. J. A. Sloane_

%E More terms from _Vladeta Jovovic_, Sep 19 2006

%E Edited with formula by _Christian G. Bower_, Jan 08 2004

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 10:55 EDT 2024. Contains 371241 sequences. (Running on oeis4.)