A003465 Number of ways to cover an n-set. (Formerly M4024)

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

Offset

0,3

Comments

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.

References

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.

Links

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.

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

Formula

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

Example

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

Maple

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

Mathematica

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

Prog

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

Crossrefs

Cf. A007537, A000371, A055154 (row sums), A055621 (unlabeled case).

Column sums of A326914 and of A326962.

Sequence in context: A188457 A245106 A244004 * A177680 A281762 A265082

Adjacent sequences: A003462 A003463 A003464 * A003466 A003467 A003468

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

More terms and comments from Michael Somos

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

Status

approved