|
|
A003180
|
|
Number of equivalence classes of Boolean functions of n variables under action of symmetric group.
(Formerly M1265 N1405)
|
|
30
|
|
|
|
OFFSET
|
0,1
|
|
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).
|
|
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
|
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
|
|
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.
|
|
EXAMPLE
|
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)
|
|
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):
|
|
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]}];
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}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|