A007537 -id:A007537 - cp's OEIS frontend

A003465 Number of ways to cover an n-set.

1, 1, 5, 109, 32297, 2147321017, 9223372023970362989, 170141183460469231667123699502996689125, 57896044618658097711785492504343953925273862865136528166133547991141168899281

Offset: 0

N. J. A. Sloane

Let S be an n-element set, and let P be the set of all nonempty subsets of S. Then a(n) = number of subsets of P whose union is S.
Including the empty set doubles the entries, and we get A000371.
For disjoint covers see A000110. - Manfred Boergens, May 13 2024
For disjoint covers which may include one empty set see A186021. - Manfred Boergens, Mar 09 2025

			Let n=2, S={a,b}, P={a,b,ab}. There are five subsets of P whose union is S: {ab}, {a,b}, {a,ab}, {b,ab}, {a,b,ab}. - _Marc LeBrun_, Nov 10 2010

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
C. G. Wagner, Covers of finite sets, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 515-520.

Alois P. Heinz, Table of n, a(n) for n = 0..11
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.
Martin Klazar, Extremal problems for ordered hypergraphs, arXiv:math/0305048 [math.CO], 2003.
Liwen Ma, Classification of coverings in the finite approximation spaces, Inf. Sci. 276 (2014) 31-41
A. J. Macula, Covers of a finite set, Math. Mag., 67 (1994), 141-144.
S. Spasovski and A. M. Bogdanova, Optimization of the Polynomial Greedy Solution for the Set Covering Problem, 2013, 10th Conference for Informatics and Information Technology (CIIT 2013).
Eric Weisstein's World of Mathematics, Cover.
Yoad Winter and Remko Scha, Plurals, draft chapter for the Wiley-Blackwell Handbook of Contemporary Semantics - second edition, edited by Shalom Lappin and Chris Fox, 2014.
Ping Zhou, Covering rough sets based on neighborhoods: an approach without using neighborhoods, Int. J. Approx. Reas. 52 (2011) 461-472, Section 3

Cf. A007537, A000371, A055154 (row sums), A369950 (diagonal for n>=1), A055621 (unlabeled case).
Column sums of A326914 and of A326962.
Cf. A000110, A186021.

a:= n-> add((-1)^k * binomial(n, k)*2^(2^(n-k))/2, k=0..n):
seq(a(n), n=0..11);  # Alois P. Heinz, Aug 24 2014

Table[Sum[(-1)^j Binomial[n,j] 2^(2^(n-j)-1),{j,0,n}],{n,0,10}] (* Geoffrey Critzer, Jun 26 2013 *)

{a(n) = sum(k=0, n, (-1)^k * n!/k!/(n-k)! * 2^(2^(n-k))) / 2} /* Michael Somos, Jun 14 1999 */

a(n) = Sum_{k>=0} (-1)^k * binomial(n, k) * 2^(2^(n-k)) / 2. - Michael Somos, Jun 14 1999
E.g.f.: (1/2)*Sum_{n>=0} exp((2^n-1)*x)*log(2)^n/n!. - Vladeta Jovovic, May 30 2004
a(n) ~ 2^(2^n - 1). - Vaclav Kotesovec, Jul 02 2016

More terms and comments from Michael Somos

Entry revised by N. J. A. Sloane, Nov 23 2010

A003181 Number of P-equivalence classes of nondegenerate Boolean functions of n variables.

Original entry on oeis.org

2, 2, 8, 68, 3904, 37329264, 25626412300941056, 67516342973185974302549277749387264, 2871827610052485009904013737758920847602293486924450772201235462734479360

Offset: 0

N. J. A. Sloane

nonn

Also the number of non-isomorphic sets of subsets of {1..n} with union {1..n}. - Gus Wiseman, Aug 05 2019

			From _Gus Wiseman_, Aug 05 2019: (Start)
Non-isomorphic representatives of the a(0) = 2 through a(2) = 8 sets of subsets:
  {}    {{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)

S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..12
S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971. [Annotated scans of a few pages]
Index entries for sequences related to Boolean functions

Cf. A000371, A001146, A003180, A003465, A055621, A007537, A326881.

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, [])):
seq(a(n), n=0..8);  # Alois P. Heinz, Aug 14 2019

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, {}]];
a /@ Range[0, 8] (* Jean-François Alcover, Apr 11 2020, after Alois P. Heinz *)

a(n) = A003180(n) - A003180(n-1), for n >= 1. - Christian Sievers, Jul 22 2016

a(n) = 2 * A055621(n). - Gus Wiseman, Aug 05 2019

More terms from Christian Sievers, Jul 22 2016

Definition clarified by Ivo Timoteo, Mar 14 2017

A055152 Proper covers of an unlabeled n-set.

Original entry on oeis.org

0, 1, 14, 956, 9331320, 6406603065901952, 16879085743296493569230716352778240, 717956902513121252476003434439730211883694285987816199468264943161704448

Offset: 1

Vladeta Jovovic, Jun 14 2000

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

See A007537 for labeled case. Cf. A055621.

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->  (b(n$2, [])-2*b(n-1$2, []))/4:
seq(a(n), n=1..8);  # Alois P. Heinz, Aug 14 2019

b[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[n_] := (b[n] - 2 b[n - 1])/4;
a /@ Range[8] (* Jean-François Alcover, Feb 19 2020, after Alois P. Heinz in A000612 *)

a(n) = (A003180(n) - 2*A003180(n-1))/4.

Apparently a(n) = A002857(n) - A000612(n-1). - R. J. Mathar, Apr 22 2007

More terms from David Wasserman, Mar 21 2002

A095421 Triangle read by rows: T(n,m) = number of m-block proper covers (without empty blocks and without multiple blocks) of a labeled n-set (n>=2, 2<=m<=2^n-2).

Original entry on oeis.org

1, 6, 17, 15, 6, 1, 25, 230, 861, 1918, 2975, 3428, 3003, 2002, 1001, 364, 91, 14, 1, 90, 2125, 20930, 127701, 568820, 2003635, 5820750, 14282125, 30030000, 54620475, 86490950, 119759325, 145422600, 155117515, 145422675, 119759850, 86493225

Offset: 2

Goran Kilibarda, Vladeta Jovovic, Jun 04 2004

			1;
6,17,15,6,1;
25,230,861,1918,2975,3428,3003,2002,1001,364,91,14,1;
...

G. C. Greubel, Table of n, a(n) for the first 10 rows, flattened
Eric Weisstein's World of Mathematics, Proper Cover.

Cf. A007537(row sums), A055154, A055127, A055152, A095422, A095423.

T[n_, m_] := Sum[(-1)^(n - i)*Binomial[n, i]*Binomial[2^i - 1, m], {i, 1, n}] - Binomial[2^n - 2, m - 1]; Table[T[n, m], {n, 2, 10}, {m, 2, 2^n - 2}] // Flatten (* G. C. Greubel, Oct 07 2017 *)

for(n=2,6, for(m=2, 2^n -2, print1(sum(j=1,n, (-1)^(n-j)* binomial(n, j)*binomial(2^j -1, m)), ", "))) \\ G. C. Greubel, Oct 07 2017

T(n, m) = Sum((-1)^(n-i)*binomial(n, i)*binomial(2^i-1, m), i=1..n) - binomial(2^n-2, m-1).

A095423 Number of proper T_0-covers of an n-set.

Original entry on oeis.org

0, 1, 42, 15654, 1073421588, 4611685989440629944, 85070591730234615704434641716516893512, 28948022309329048855892746252171976959574390130279817915318273546782086570304

Offset: 1

Goran Kilibarda, Vladeta Jovovic, Jun 04 2004

The next term has 154 decimal digits.

Row sums of A095422, A095421.

a(n)=sum(k=0,n, (2*stirling(n+1, k+1, 1) - stirling(n, k,1 )) * 2^(2^k-2) );
vector(10,n,a(n)) /* show terms */

a(n) = Sum(Stirling1(n, k)*A007537(k), k=1..n).

a(n) = Sum((2*Stirling1(n+1, k+1)-Stirling1(n, k))*2^(2^k-2), k=0..n).

A055127 Triangle T(n,k) of numbers of proper k-covers of an unlabeled n-set, k=1..2^n-2.

Original entry on oeis.org

0, 1, 0, 2, 5, 4, 2, 1, 0, 4, 19, 58, 113, 168, 193, 171, 119, 68, 29, 10, 3, 1, 0, 6, 53, 325, 1551, 6007, 19533, 54119, 128936, 266085, 478223, 751487, 1035609, 1254303, 1336855, 1254307, 1035622, 751526, 478320, 266272, 129226, 54484, 19898, 6297

Offset: 2

Vladeta Jovovic, Jun 14 2000

			[0, 1], [0, 2, 5, 4, 2, 1], [0, 4, 19, 58, 113, 168, 193, 171, 119, 68, 29, 10, 3, 1], ...; There are 113 proper 5-covers of an unlabeled 4-set.

Eric Weisstein's World of Mathematics, Proper covers

Cf. A052265, A055080, A007537. Row sums give A055152.

cp's OEIS Frontend

A003465 Number of ways to cover an n-set.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A003181 Number of P-equivalence classes of nondegenerate Boolean functions of n variables.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A055152 Proper covers of an unlabeled n-set.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A095421 Triangle read by rows: T(n,m) = number of m-block proper covers (without empty blocks and without multiple blocks) of a labeled n-set (n>=2, 2<=m<=2^n-2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A095423 Number of proper T_0-covers of an n-set.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A055127 Triangle T(n,k) of numbers of proper k-covers of an unlabeled n-set, k=1..2^n-2.

Views

Author

Keywords

Examples

Links

Crossrefs