A003181 -id:A003181 - cp's OEIS frontend

A055621 Number of covers of an unlabeled n-set.

1, 1, 4, 34, 1952, 18664632, 12813206150470528, 33758171486592987151274638874693632, 1435913805026242504952006868879460423801146743462225386100617731367239680

Offset: 0

Vladeta Jovovic, Jun 04 2000

			There are 4 nonisomorphic covers of {1,2}, namely {{1},{2}}, {{1,2}}, {{1},{1,2}} and {{1},{2},{1,2}}.
From _Gus Wiseman_, Aug 14 2019: (Start)
Non-isomorphic representatives of the a(3) = 34 covers:
  {123}  {1}{23}    {1}{2}{3}      {1}{2}{3}{23}
         {13}{23}   {1}{3}{23}     {1}{2}{13}{23}
         {3}{123}   {2}{13}{23}    {1}{2}{3}{123}
         {23}{123}  {2}{3}{123}    {2}{3}{13}{23}
                    {3}{13}{23}    {1}{3}{23}{123}
                    {12}{13}{23}   {2}{3}{23}{123}
                    {1}{23}{123}   {3}{12}{13}{23}
                    {3}{23}{123}   {2}{13}{23}{123}
                    {13}{23}{123}  {3}{13}{23}{123}
                                   {12}{13}{23}{123}
.
  {1}{2}{3}{13}{23}     {1}{2}{3}{12}{13}{23}    {1}{2}{3}{12}{13}{23}{123}
  {1}{2}{3}{23}{123}    {1}{2}{3}{13}{23}{123}
  {2}{3}{12}{13}{23}    {2}{3}{12}{13}{23}{123}
  {1}{2}{13}{23}{123}
  {2}{3}{13}{23}{123}
  {3}{12}{13}{23}{123}
(End)

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 78 (2.3.39)

Alois P. Heinz, Table of n, a(n) for n = 0..12
Heller, Jürgen Identifiability in probabilistic knowledge structures. J. Math. Psychol. 77, 46-57 (2017).
Eric Weisstein's World of Mathematics, Cover

Unlabeled set-systems are A000612 (partial sums).
The version with empty edges allowed is A003181.
The labeled version is A003465.
The T_0 case is A319637.
The connected case is A323819.
The T_1 case is A326974.
Cf. A058891, A319559, A326946, A326973.

b:= proc(n, i, l) `if`(n=0, 2^(w-> add(mul(2^igcd(t, l[h]),
      h=1..nops(l)), t=1..w)/w)(ilcm(l[])), `if`(i<1, 0,
      add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i)))
    end:
a:= n-> `if`(n=0, 2, b(n$2, [])-b(n-1$2, []))/2:
seq(a(n), n=0..8);  # Alois P. Heinz, Aug 14 2019

b[n_, i_, l_] := 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}]]];
a[n_] := If[n==0, 2, b[n, n, {}] - b[n-1, n-1, {}]]/2;
a /@ Range[0, 8] (* Jean-François Alcover, Jan 31 2020, after Alois P. Heinz *)

a(n) = (A003180(n) - A003180(n-1))/2 = A000612(n) - A000612(n-1) for n>0.

Euler transform of A323819. - Gus Wiseman, Aug 14 2019

More terms from David Moews (dmoews(AT)xraysgi.ims.uconn.edu) Jul 04 2002

a(0) = 1 prepended by Gus Wiseman, Aug 14 2019

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

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

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

			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)

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

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

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

Cf. A003181, A055621.

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

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+ *)

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

More terms from Vladeta Jovovic, Sep 19 2006

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

A326939 Number of T_0 sets of subsets of {1..n} that cover all n vertices.

Original entry on oeis.org

2, 2, 8, 192, 63384, 4294003272, 18446743983526539408, 340282366920938462946865774750753349904, 115792089237316195423570985008687907841019819456486779364848020385134373080448

Offset: 0

Gus Wiseman, Aug 07 2019

nonn

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

			The a(0) = 2 through a(2) = 8 sets of subsets:
  {}    {{1}}     {{1},{2}}
  {{}}  {{},{1}}  {{1},{1,2}}
                  {{2},{1,2}}
                  {{},{1},{2}}
                  {{},{1},{1,2}}
                  {{},{2},{1,2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

The non-T_0 version is A000371.
The case without empty edges is A059201.
The non-covering version is A326941.
The unlabeled version is A326942.
The case closed under intersection is A326943.
Cf. A003180, A003181, A003465, A316978, A319564, A319637, A326940, A326947.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n]]],Union@@#==Range[n]&&UnsameQ@@dual[#]&]],{n,0,3}]

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

Inverse binomial transform of A326941.

A326943 Number of T_0 sets of subsets of {1..n} that cover all n vertices and are closed under intersection.

Original entry on oeis.org

2, 2, 6, 70, 4078, 2704780, 151890105214, 28175292217767880450

Offset: 0

Gus Wiseman, Aug 08 2019

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

			The a(0) = 2 through a(3) = 6 sets of subsets:
  {}    {{1}}     {{1},{1,2}}
  {{}}  {{},{1}}  {{2},{1,2}}
                  {{},{1},{2}}
                  {{},{1},{1,2}}
                  {{},{2},{1,2}}
                  {{},{1},{2},{1,2}}

The non-T_0 version is A326906.
The case without empty edges is A309615.
The non-covering version is A326945.
The version not closed under intersection is A326939.
Cf. A003180, A003181, A003465, A059052, A059201, A245567, A316978, A319564, A319637, A326940, A326941, A326942, A326947.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n]]],Union@@#==Range[n]&&UnsameQ@@dual[#]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}]

Inverse binomial transform of A326945.

a(n) = Sum_{k=0..n} Stirling1(n,k)*A326906(k). - Andrew Howroyd, Aug 14 2019

a(5)-a(7) from Andrew Howroyd, Aug 14 2019

A326951 Number of unlabeled sets of subsets of {1..n} where every covered vertex is the unique common element of some subset of the edges.

Original entry on oeis.org

2, 4, 8, 40, 2464

Offset: 0

Gus Wiseman, Aug 13 2019

Alternatively, these are unlabeled sets of subsets of {1..n} whose dual is a (strict) antichain, also called T_1 sets of subsets. The dual of a set of subsets has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. An antichain is a set of subsets where no edge is a subset of any other.

			Non-isomorphic representatives of the a(0) = 2 through a(2) = 8 sets of subsets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{},{1}}
                  {{1},{2}}
                  {{},{1},{2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

Unlabeled sets of subsets are A003180.
Unlabeled T_0 sets of subsets are A326949.
The labeled version is A326967.
The case without empty edges is A326972.
The covering case is A327011 (first differences).
Cf. A003181, A059052, A326960, A326965, A326969, A326974, A326976.

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

a(n) = Sum_{k = 0..n} A327011(k).

A326944 Number of T_0 sets of subsets of {1..n} that cover all n vertices, contain {}, and are closed under intersection.

Original entry on oeis.org

1, 1, 4, 58, 3846, 2685550, 151873991914, 28175291154649937052

Offset: 0

Gus Wiseman, Aug 08 2019

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

			The a(0) = 1 through a(2) = 4 sets of subsets:
  {{}}  {{},{1}}  {{},{1},{2}}
                  {{},{1},{1,2}}
                  {{},{2},{1,2}}
                  {{},{1},{2},{1,2}}

The version not closed under intersection is A059201.
The non-T_0 version is A326881.
The version where {} is not necessarily an edge is A326943.
Cf. A003181, A003465, A055621, A182507, A245567, A316978, A319564, A326906, A326939, A326941, A326945, A326947.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n]]],MemberQ[#,{}]&&Union@@#==Range[n]&&UnsameQ@@dual[#]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}]

a(n) = Sum_{k=0..n} Stirling1(n,k)*A326881(k). - Andrew Howroyd, Aug 14 2019

a(5)-a(7) from Andrew Howroyd, Aug 14 2019

A326960 Number of sets of subsets of {1..n} covering all n vertices whose dual is a (strict) antichain, also called covering T_1 sets of subsets.

Original entry on oeis.org

2, 2, 4, 72, 38040, 4020463392, 18438434825136728352, 340282363593610211921722192165556850240, 115792089237316195072053288318104625954343609704705784618785209431974668731584

Offset: 0

Gus Wiseman, Aug 13 2019

nonn

Same as A059052 except with a(1) = 2 instead of 4.
The dual of a set of subsets has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. An antichain is a set of subsets where no edge is a subset of any other.
Alternatively, these are sets of subsets of {1..n} covering all n vertices where every vertex is the unique common element of some subset of the edges.

			The a(0) = 2 through a(2) = 4 sets of subsets:
  {}    {{1}}     {{1},{2}}
  {{}}  {{},{1}}  {{},{1},{2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

Covering sets of subsets are A000371.
Covering T_0 sets of subsets are A326939.
The case without empty edges is A326961.
The non-covering version is A326967.
Cf. A003181, A059052, A059523, A319639, A326951, A326965, A326974, A326976, A326977, A326979.

Table[Length[Select[Subsets[Subsets[Range[n]]],Length[Union[Select[Intersection@@@Rest[Subsets[#]],Length[#]==1&]]]==n&]],{n,0,3}]

Binomial transform of A326967.

A326949 Number of unlabeled T_0 sets of subsets of {1..n}.

Original entry on oeis.org

2, 4, 10, 68, 3838, 37320356

Offset: 0

Gus Wiseman, Aug 08 2019

The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

			Non-isomorphic representatives of the a(0) = 2 through a(2) = 10 sets of sets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{},{1}}
                  {{1},{2}}
                  {{2},{1,2}}
                  {{},{1},{2}}
                  {{},{2},{1,2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

The non-T_0 version is A003180.
The labeled version is A326941.
The covering case is A326942 (first differences).
The case without empty edges is A326946.
Cf. A000371, A000612, A003181, A059052, A245567, A316978, A319559, A319564, A319637, A326939, A326940.

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

a(5) from Max Alekseyev, Oct 11 2023

A326942 Number of unlabeled T_0 sets of subsets of {1..n} that cover all n vertices.

Original entry on oeis.org

2, 2, 6, 58, 3770

Offset: 0

Gus Wiseman, Aug 07 2019

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

			Non-isomorphic representatives of the a(0) = 2 through a(2) = 6 sets of subsets:
  {}    {{1}}     {{1},{2}}
  {{}}  {{},{1}}  {{2},{1,2}}
                  {{},{1},{2}}
                  {{},{2},{1,2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

The non-T_0 version is A003181.
The case without empty edges is A319637.
The labeled version is A326939.
The non-covering version is A326949 (partial sums).
Cf. A000371, A003180, A055621, A059201, A316978, A319559, A319564, A326907, A326941, A326943, A326946.

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

A112535 Number of truth tables generated by 3CNF expressions of n variables.

Original entry on oeis.org

2, 4, 16, 256, 43146, 120510132, 4977694100656

Offset: 0

C. Bradford Barber (bradb(AT)shore.net), Dec 13 2005

For n=5, computing the number of 3CNF truth tables took 2^32 bytes and 2^38 iterations. Computing the same number for n=6 may require 2^64 bits and 2^71 iterations.

I calculated a(6) using a different method; a(7) looks a lot harder. - Don Knuth, Dec 10 2012

Knuth, Donald E., Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 148 and 220, Problem 191.

C. B. Barber, ttcnf 2005.1 (April 2005).
C. B. Barber, www.qhull.org/ttcnf.

Cf. A034472, A109457 (corresponding sequences for 1CNF and 2CNF), A112650, A000157, A000371, A000613, A000618, A003181.

a(6) from Don Knuth, Dec 10 2012

cp's OEIS Frontend

A055621 Number of covers of an unlabeled n-set.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A326939 Number of T_0 sets of subsets of {1..n} that cover all n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326943 Number of T_0 sets of subsets of {1..n} that cover all n vertices and are closed under intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A326951 Number of unlabeled sets of subsets of {1..n} where every covered vertex is the unique common element of some subset of the edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A326944 Number of T_0 sets of subsets of {1..n} that cover all n vertices, contain {}, and are closed under intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A326960 Number of sets of subsets of {1..n} covering all n vertices whose dual is a (strict) antichain, also called covering T_1 sets of subsets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326949 Number of unlabeled T_0 sets of subsets of {1..n}.

Views