A003465 Number of ways to cover an n-set.

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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.

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

Examples

			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
		

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

Crossrefs

Cf. A007537, A000371, A055154 (row sums), A369950 (diagonal for n>=1), A055621 (unlabeled case).

Column sums of A326914 and of A326962.

Cf. A000110, A186021.

Programs

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

PARI

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

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

Extensions

More terms and comments from Michael Somos

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