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.
For disjoint covers see A000110. - Manfred Boergens, May 13 2024
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
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
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms and comments from Michael Somos
Entry revised by N. J. A. Sloane, Nov 23 2010
STATUS
approved